首页>前端>正文

【上海前端培训】JavaScript实现冒泡排序

时间:2018-03-28 18:20:05   来源:上海尚学堂   阅读:

一、前言

JS冒泡排序由于比较简单和容易理解,往往会成为人们首先想到的排序算法。最基本的想法就是在一次里面比较两个数字,并且确保他们在移动到其他项目之前有一个正确的顺序。在每一结束价值的“排序”到正确的位置最终只留下其他项目排序。·

二、排序实现思路

  1. 对比第一项和第二项
  2. 如果第一项应该在第二项的后面,交换他们
  3. 对比第二项和第三项
  4. 如果第二项应该在第三项之后,交换他们
  5. 持续直到数据结束

这个过程就是重复数次直到数据完全排序完毕,在每一次循环中,由于每一次的最后一项都是正确的排序,所以排序的项就越来越少。


三、javascript代码实现

 

[javascript] view plain copy
 
  1. function bubbleSort(arr){    
  2.     var len = arr.length;    
  3.     for (var i = 0; i < len; 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.     
  15. var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];//调用排序算法    
  16. console.log(bubbleSort(arr));//控制台输出结果    

        这个算法是最基本的实现方法,接着进行改进这个算法,通过设置一个标志性的变量position,用于记录每趟排序中最后一次进行交换的位置。因为position位置之后的记录都已经排序好了,所以进行下一趟排序时只需要扫描到position的位置就好。

改进之后的算法如下:(上海尚学堂前端培训 www.shsxt.com/html5)

 

[javascript] view plain copy
 
  1. function bubbleSort2(arr){    
  2.     var i = arr.length -1;//开始时,扫描的最后位置    
  3.     while(i>0){    
  4.         var position = 0;//标志性变量,表示当前排序中交换的位置    
  5.         for(var j = 0; j < i; j ++){    
  6.             if(arr[j]>arr[j+1]){    
  7.                 position = j;    
  8.                 var temp = arr[j+1];    
  9.                 arr[j+1] = arr[j];    
  10.                 arr[j] = temp;    
  11.             }    
  12.         }    
  13.         i = position;    
  14.     }    
  15.     return arr;    
  16. }    
  17.     
  18. var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];    
  19. console.log(bubbleSort2(arr));    
      传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。
改进之后的算法如下:

[javascript] view plain copy
 
  1. function bubbleSort3(arr){    
  2.     var low = 0;    
  3.     var high = arr.length-1;    
  4.     var temp;    
  5.     while(low < high){//找到最大值    
  6.         for(var j = low ; j < high ; j++){    
  7.             if (arr[j]> arr[j+1]) {              
  8.                 temp = arr[j+1];    
  9.                 arr[j+1] = arr[j];    
  10.                 arr[j] = temp;    
  11.              }    
  12.         }    
  13.         --high;//修改high值,向前移一位    
  14.     }    
  15.     while(low > high){//找到最小值    
  16.         for(var j = high ;j > low; j--){    
  17.             if (arr[j]> arr[j+1]) {              
  18.                 temp = arr[j+1];    
  19.                 arr[j+1] = arr[j];    
  20.                 arr[j] = temp;    
  21.              }    
  22.         }    
  23.         ++low;//修改low值,往后移动一位    
  24.     }    
  25.     return arr;    
  26. }    
  27. var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];    
  28. console.log(bubbleSort3(arr));    
参考文章:https://blog.csdn.net/u010297791/article/details/53898423


感谢阅读上海尚学堂前端技术文章,获取更多前端内容或支持请点击  上海前端培训
分享:0

电话咨询

客服热线服务时间

周一至周五 9:00-21:00

周六至周日 9:00-18:00

咨询电话

021-67690939
15201841284

微信扫一扫