复习排序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){//初始调用没有left
29         left=0;
30     }
31     if(undefined===right){//初始调用,参数没有right
32         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运行的结果,快排最后秒杀全场

 复习排序with javascript

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 }

复习排序with javascript测试的时候,没留意到不改变原数组的问题,打印出原数组 ,我一度以为是自己写错,囧。好吧,too simple。

复习排序with javascript,布布扣,bubuko.com

复习排序with javascript

上一篇:java/matlab混合编程应用移植到其他电脑上遇到的问题


下一篇:SpringBoot--application.yml