首页 > 代码库 > 复习排序with javascript
复习排序with javascript
最近又翻看了一下数据结构（数据结构学渣）。
以前总是看不懂，连冒泡和选择排序都要纠结半天，后来才慢慢有意识能区分开来。
当真的理解了快速排序之后，才觉得，这是个很赞的排序，很容易理解。
于是简单的，模仿c的做法，实现了javascript上的排序，目前只有冒泡、选择和快速排序。//不过貌似快速排序用到了传递的性质，也许我应该改改。
1 function bubbleSort(arr){ 2 var len = arr.length; 3 for(var i=0; i<len-1;i++){ 4 for(var j=0; j<len-i-1; j++){ 5 if(arr[j]>arr[j+1]){ 6 var temp = arr[j+1]; 7 arr[j+1] = arr[j]; 8 arr[j] = temp; 9 }10 }11 }12 return arr;13 }14 function chooseSort(arr){15 var len = arr.length;16 for(var i=0; i<len-1;i++){17 for(var j=i+1; j<len; j++){18 if(arr[i]>arr[j]){19 var temp = arr[j];20 arr[j] = arr[i];21 arr[i] = temp; 22 }23 }24 }25 return arr;26 }27 function quickSort(arr, left, right){28 if(undefined===left){//初始调用没有left29 left=0;30 }31 if(undefined===right){//初始调用，参数没有right32 right = arr.length-1;33 }34 if(left>right){35 return;36 }37 //移动左右索引变量38 var i = left;39 var j = right;40 var midKey = arr[left];41 while(i<j){42 while(i<j&&midKey<=arr[j]){43 j--;44 }45 while(i<j&&midKey>=arr[i]){46 i++;47 }48 if(i<j){49 var temp = arr[i];50 arr[i] = arr[j];51 arr[j] = temp;52 }53 }54 //交换中间数与中轴数55 arr[left] = arr[i];56 arr[i] = midKey;57 //递归左右，分治思想58 quickSort(arr, left, i-1);59 quickSort(arr, i+1, right);60 return arr;61 }62 function timeIt(fn, arr){//计算方法执行速度63 var start = new Date().getTime();64 arr = fn(arr);65 var end = new Date().getTime();66 console.log("cost(ms):"67 +(end-start)+" result:"+arr[0]+ " " + arr[1] +" "+arr[2]+"..."+arr[arr.length-1]);68 }69 var a = [2,5,3,2,2,8,5,9,4,6,3,1,3,7];70 //console.log(bubbleSort(a));71 timeIt(bubbleSort, a)72 a = [2,5,3,2,2,8,5,9,4,6,3,1,3,7];73 timeIt(chooseSort, a);//console.log(chooseSort(a));74 a = [2,5,3,2,2,8,5,9,4,6,3,1,3,7];75 timeIt(quickSort, a)//console.log(quickSort(a));76 77 var randArr = [];78 for(var i=0;i<10000; i++){79 randArr[i] = Math.floor(Math.random()*100000);80 } 81 a = randArr.slice();82 timeIt(bubbleSort, a)83 a = randArr.slice();84 timeIt(chooseSort, a);//console.log(chooseSort(a));85 a = randArr.slice();86 timeIt(quickSort, a)
冒泡跟选择以前容易混淆，是因为不明白怎样叫冒泡，实际上，冒泡就是对整个序列，进行一趟前后元素两两比较的形式，大的数后移（或者小的），这样达到一趟实现了把大的数（或者小的数）移到了尾部，那整一个序列看成尾部朝上，往后一趟序列，从头开始一直到倒数第n个数进行两两比较，犹如关键元素（最大值或者最小值）往上冒泡的样子 ，因此叫冒泡。
而选择排序，则是对序列的每个数，从头开始，针对该位置与剩下的数进行比较， 如果有出现大于（小于）该位置的数，则交换位置，这样每一趟下来，就能确定固定位置该放置的数。 //这个解释感觉跟选择没多大关联，姑且当做是选择位置吧。
那么快速排序，就是直接用效率命名了。为什么快呢？看代码实现 ，while里面还有while，还有递归，感觉不快的样子，关于时间复杂度的问题，我还没嚼透。
快排思想是分而治之，既然一个分散的序列，假设通过比较某个值，分别将大于和小于该数的分到一边，就成了两部分，然后同样的道理，各部分再按切分大小方法再细分成两部分……以此推下去，直到变成了最小的部分就是三个数，a<b<c，这个时候各个细小部分组合起来，明显就是一个排序好的序列了。
最后贴一下代码在chrome console运行的结果，快排最后秒杀全场
2014-06-20 更新： 快排加入另一种实现，利用array的api，不过似乎速度不尽如人意，但是做到了不破坏实参数组的效果，而且不过在元素大的时候还是比冒泡选择强：
1 function quickSortArr(arr){ 2 if(arr.length==1){ 3 return arr; 4 } 5 if(arr.length==0){//这两句if实际上可以写成一句的 6 return []; 7 } 8 var left = [], 9 right = [];10 var povit = arr[0];11 for(var i=1;i<arr.length;i++){12 if(arr[i]<=povit){13 left.push(arr[i]);14 }else{15 right.push(arr[i]);16 }17 }18 var re = quickSortArr(left).concat([povit],quickSortArr(right));19 return re;//这里为了调试才加的变量，实际可以不用20 }
测试的时候，没留意到不改变原数组的问题，打印出原数组 ，我一度以为是自己写错，囧。好吧，too simple。