说实话，本人半路出家从事web开发，计算机方面的许多知识都算是小白，算法这种东东，以前是完全没有什么概念。
后来学习JS的时候总感觉编写程序很不靠谱，所以有段时间就猛补了一下数据结构啊算法啊，设计模式啊撒的。
感觉还是很有效果的。。。
这两天没什么事，就把算法重新温习了一下，下面有写好的程序，希望对算法有研究的同志们多多指点，看哪里有问题，要改正或改进的地方。
如果是对算法本身的原理理解有误，也望不要吝惜你的笔墨。。。。。
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>排序</title> </head> <body> <mce:script type="text/javascript"><!-- /******************************生成乱序数组****************************/ var list = []; for(var i = 0; i < 999; i++) { list.push(parseInt(Math.random() * 10000)); } /*****************************快速排序*******************************/ function quickSort(arr) { (function(arr, s, e) { var f = arguments.callee; if(s < e) { var i = s; var j = e; var key = arr[s]; while(i < j) { if(arr[j] >= key) { j--; } else { arr[i] = arr[j]; i++; while(i < j) { if(arr[i] > key) { arr[j] = arr[i]; break; } else { i++; } } } } arr[i] = key; f(arr, s, i - 1); f(arr, i + 1, e); } })(arr, 0, arr.length - 1); } /*****************************直接插入排序****************************/ function insertSort(arr) { var len = arr.length; var i, j, key; for(i = 0; i < len; i++) { j = i + 1; key = arr[j]; if(key < arr[i]) { while(key < arr[i]) { arr[i + 1] = arr[i]; i--; } arr[i + 1] = key; } i = j - 1; } } /********************************希尔排序(直接插入排序变种方法)**********************************/ function sellSort(arr) { var len = arr.length; var s = (len % 2) == 0? len : len + 1; var k = 0; while(s >= 1) { k = len - s + 1; /******************直接插入***********************/ var i, j, key; for(i = 0; i < k; i++) { j = i + 1; key = arr[j]; if(key < arr[i]) { while(key < arr[i]) { arr[i + 1] = arr[i]; i--; } arr[i + 1] = key; } i = j - 1; } /******************直接插入***********************/ s = s / 2; } } /********************************冒泡排序**********************************/ function bubbleSort(arr) { var len = arr.length; var key, flag; while(true) { flag = false; for(var j = 0; j < len; j++) { if(arr[j] > arr[j + 1]) { key = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = key; flag =true; } } if(!flag) { break; } } } /********************************直接选择排序**********************************/ function selectSort(arr) { var len = arr.length; var j, key; for(var i = 0; i < len; i++) { j = i + 1; while(j < len) { if(arr[j] < arr[i]) { key = arr[i]; arr[i] = arr[j]; arr[j] = key; } j++; } } } /********************************堆排序************************************/ function heapSort(arr) { var len = arr.length; var wi = len - 1; var key; while(wi > 0) { heap(arr, 0, wi); key = arr[wi]; arr[wi] = arr[0]; arr[0] = key; wi--; } /********************创建堆***********************/ function heap(arr, s, e) { var len = arr.length; var index = 0; var i, j, key; while(index < len) { var i = index * 2 + 1; var j = index * 2 + 2; if(i <= len && arr[index] < arr[i]) { key = arr[i]; arr[i] = arr[index]; arr[index] = key; continue; } if(j <= len && arr[index] < arr[j]) { key = arr[j]; arr[j] = arr[index]; arr[index] = key; continue; } index++; } } /********************创建堆***********************/ } /********************************归并排序**********************************/ function mergeSort(arr) { (function(arr, s, e) { var f = arguments.callee; var m; if(s < e) { m = Math.floor((s + e) / 2); f(arr, s, m); f(arr, (m + 1), e); /*********************************************/ var b1 = s; var e1 = m; var b2 = m + 1; var e2 = e; var temp = []; while(b1 <= e1 && b2 <= e2) { if(arr[b1] < arr[b2]) { temp.push(arr[b1]); b1++; } else { temp.push(arr[b2]) b2++; } } while(b1 <= e1) { temp.push(arr[b1]); b1++; } while(b2 <= e2) { temp.push(arr[b2]); b2++; } var l = temp.length; for(var i = 0; i < l; i++) { arr[s + i] = temp[i]; } /*********************************************/ } })(arr, 0, arr.length - 1); } /**********************************基数排序(从右到左)***************************************/ function radixSort(arr) { Number.prototype.length = function() { return this.toString().length; } Number.prototype.index = function(n) { var l = this.length(); return l >= n? this.toString().substr(l - n, 1) : 0; } var maxLen = arr[0].length(); var len = arr.length; var lenTemp = 0; for(var i = 1; i < len; i++) { lenTemp = arr[i].length(); if(lenTemp > maxLen) { maxLen = lenTemp; } } var temp, tempLen, itemTemp, key, ai; for(var j = 1; j <= maxLen; j++) { temp = [[], [], [], [], [], [], [], [], [], []]; for(var k = 0; k < len; k ++) { itemTemp = arr[k]; key = itemTemp.index(j); temp[key].push(itemTemp); } ai = 0; for(var m = 0; m < 10; m++) { tempLen = temp[m].length; if(tempLen > 0) { for(var n = 0; n < tempLen; n++) { arr[ai] = temp[m][n]; ai++; } } } } } /**********************************数组sort排序***************************************/ function arrSort(arr) { arr.sort(function(a, b) { return a > b? true : false; }); } var st = (new Date()).getTime(); /********************************************************/ //quickSort(list); //insertSort(list); //sellSort(list); //bubbleSort(list); //selectSort(list); //mergeSort(list); //radixSort(list); //arrSort(list); /********************************************************/ var et = (new Date()).getTime(); document.write(list); alert(et - st); // --></mce:script> </body> </html>
