Javascript中，实现十大排序方法之一（冒泡排序及其优化设想）

冒泡排序的Javascript实现

首先定义一个取值范围在（0~100000）之间的随机值的长度为10万的数组，

 1 function bubbleSort(arr) {
 2         console.time('冒泡排序耗时');
 3         var len = arr.length,temp;
 4         for(var i=0;i<len;i++){
 5             for(j=0;j<len-i-1;j++){
 6                     if(arr[j]>arr[j+1]){
 7                            temp = arr[j+1];
 8                            arr[j+1] = arr[j];
 9                            arr[j] = temp;
10                     }
11             }
12         }
13         console.timeEnd('冒泡排序耗时');
14         return arr;
15 }
16 
17 
18 var array = [];
19 
20 for(var i=0;i<100000;i++){
21      var x = Math.random()*100000;
22      var y = Math.floor(x);
23      array.push(y);
24 }
25 
26 console.log(bubbleSort(array));     
27 //冒泡排序十次平均耗时: 37019.239013671875ms

下面我们来看一下在javascript中的array原型链上的sort()方法的特点

1 function Sort(arr) {
2       console.time('排序耗时');
3       var arr1= arr.sort(function(a,b){return a-b});
4       console.timeEnd('排序耗时');
5       return arr1;
6       
7 }
8 
9 Sort(array);                //排序十次平均耗时: 79.05419921875ms

由上面的代码可以知道，javasrcipt中array原型链上的sort方法的效率是很高的

//冒泡排序的改良方法（一）

function bubbleSort1(arr) {
　　console.time('改进后冒泡排序耗时一');
　　var i = arr.length-1,tmp; //初始时,最后位置保持不变　　
　　while ( i> 0) {
　　　　var pos= 0; //每趟开始时,无记录交换
　　　　for (var j= 0; j< i; j++){
　　　　　　if (arr[j]> arr[j+1]) {
　　　　　　　　 pos= j; //记录交换的位置
　　　　　　　　 tmp = arr[j]; 
                           arr[j]=arr[j+1];
                           arr[j+1]=tmp;
　　　　　　}
　　　　}
　　　　i= pos; //为下一趟排序作准备
　　}
　　console.timeEnd('改进后冒泡排序耗时一');
　　return arr;
}

console.log(bubbleSort1(array));             
    //           改进后冒泡排序十次平均耗时: 30493.7470703125ms

//冒泡排序的改良方法（二）

 1 function bubbleSort2(arr) {
 2 　　var low = 0;
 3 　　var high= arr.length-1; //设置变量的初始值
 4 　　var tmp,j;
 5 　　console.time('改进后冒泡排序耗时二');
 6 　　while (low < high) {
 7 　　　　for (j= low; j< high; ++j) {         //正向冒泡,找到最大者
 8 　　　　　　if (arr[j]> arr[j+1]) {
 9 　　　　　　　　tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
10 　　　　　　}
11 　　　　}
12 　　　　--high;  //修改high值, 前移一位
13 　　　　for (j=high; j>low; --j) {          //反向冒泡,找到最小者
14 　　　　　　if (arr[j]<arr[j-1]) {
15 　　　　　　　　tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp;
16 　　　　　　}
17 　　　　}　
18 　　　　++low;  //修改low值,后移一位
19 　　}
20 　　console.timeEnd('改进后冒泡排序耗时二');
21 　　return arr;
22 }
23 
24 console.log(bubbleSort2(array));
// 改进后冒泡排序十次平均耗时:   23629.715087890625ms

//冒泡排序的改良方法（三）

 1 function bubbleSort3(arr) {
 2 　　var low = 0;
 3 　　var high= arr.length-1; //设置变量的初始值
 4 　　var tmp,j;
 5 　　console.time('改进后冒泡排序耗时三');
 6 　　while (low < high) {
 7 　　　　var pos1 = 0,pos2=0; 
 8 　　　　for (let i= low; i< high; ++i) { //正向冒泡,找到最大者
 9 　　　　　　if (arr[i]> arr[i+1]) {
10 　　　　　　　　tmp = arr[i]; arr[i]=arr[i+1];arr[i+1]=tmp;
11 　　　　　　　　pos1 = i ;
12 　　　　　　}
13 　　　　}
14 
15 　　　　high = pos1;// 记录上次位置
16 
17 　　　　for (let j=high; j>low; --j) { //反向冒泡,找到最小者
18 　　　　　　if (arr[j]<arr[j-1]) {
19 　　　　　　　　tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp;　　
20 　　　　　　　　pos2 = j;
21 　　　　　　}
22 　　　　}　　　
23 　　　　
24 　　　　low = pos2; //修改low值
25 　　}
26 　　console.timeEnd('改进后冒泡排序耗时三');
27 　　return arr;
28 }
29 
30 console.log(bubbleSort3(array));              
31 // 改进后冒泡排序十次平均耗时:  20408.427734375ms

由上面的运行结果可知，冒泡排序虽然是比较常用的排序方法，但其实其执行效率是比较低的

冒泡排序的平均时间维度为： O（n*n）最好的情况 O（n）最差的情况： O(n*n) 空间复杂度 O（1）排序方式： in-place 稳定性：稳定

图片名词解释：
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存

稳定：即如果两个数相等，那么位置不会交换

不稳定：如果两个数相等，那么也有可能交换位置