专栏名称: SegmentFault思否
SegmentFault （www.sf.gg）开发者社区，是中国年轻开发者喜爱的极客社区，我们为开发者提供最纯粹的技术交流和分享平台。
目录
相关文章推荐
OSC开源社区  ·  RAG市场的2024：随需而变，从狂热到理性 ·  2 天前  
程序猿  ·  41岁DeepMind天才科学家去世：长期受 ... ·  2 天前  
OSC开源社区  ·  宇树王兴兴早年创业分享引围观 ·  5 天前  
OSC开源社区  ·  AI大模型如何影响基础软件行业中的开发工具与环境？ ·  6 天前  
程序猿  ·  惊世骇俗！梁文锋硕士学位论文赏析：让人拍案叫绝！ ·  5 天前  
51好读  ›  专栏  ›  SegmentFault思否

前端排序算法总结

SegmentFault思否  · 公众号  · 程序员  · 2017-09-29 08:00

正文

前言

排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？

当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较你和一个连快排都不会写的人的时候，会优先选择你的。那么，前端需要会排序吗？答案是毋庸置疑的，必须会。现在的前端对计算机基础要求越来越高了，如果连排序这些算法都不会，那么发展前景就有限了。本篇将会总结一下，在前端的一些排序算法。如果你喜欢我的文章，欢迎评论，欢迎Star~。欢迎关注我的github博客

正文

首先，我们可以先来看一下js自身的排序算法sort()

Array.sort

相信每个使用js的都用过这个函数，但是，这个函数本身有些优点和缺点。我们可以通过一个例子来看一下它的功能： 

  1. const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];
  3. console.log(arr.sort());   //[ 1, 10, 100, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88 ]
  5. console.log(arr.sort((item1, item2) => item1 - item2)); //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]

相信你也已经看出来它在处理上的一些差异了吧。首先，js中的sort会将排序的元素类型转化成字符串进行排序。不过它是一个高阶函数，可以接受一个函数作为参数。而我们可以通过传入内部的函数，来调整数组的升序或者降序。

sort函数的性能：相信对于排序算法性能来说，时间复杂度是至关重要的一个参考因素。那么，sort函数的算法性能如何呢？通过v8引擎的源码可以看出，Array.sort是通过javascript来实现的，而使用的算法是快速排序，但是从源码的角度来看，在实现上明显比我们所使用的快速排序复杂多了，主要是做了性能上的优化。所以，我们可以放心的使用sort()进行排序。

冒泡排序

冒泡排序，它的名字由来于一副图——鱼吐泡泡，泡泡越往上越大。

回忆起这个算法，还是最初大一的c++课上面。还是自己上台，在黑板上实现的呢！

思路：第一次循环，开始比较当前元素与下一个元素的大小，如果比下一个元素小或者相等，则不需要交换两个元素的值；若比下一个元素大的话，则交换两个元素的值。然后，遍历整个数组，第一次遍历完之后，相同操作遍历第二遍。

图例：

代码实现： 

  1. const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];
  3. function bubbleSort(arr){
  4.   for(let i = 0; i < arr.length - 1; i++){
  5.     for(let j = 0; j < arr.length - i - 1; j++){
  6.       if(arr[j] > arr[j + 1]){
  7.         swap(arr, j, j+




    
1);
  8.       }
  9.     }
  10.   }
  11.   return arr;
  12. }
  14. function swap(arr, i, j){
  15.   let temp = arr[i];
  16.   arr[i] = arr[j];
  17.   arr[j] = temp;
  18. }




    

  19. console.log(arr);

代码地址：https://jsbin.com/wawusap/edit?js,console

性能：

  • 时间复杂度：平均时间复杂度是O(n^2)

  • 空间复杂度：由于辅助空间为常数，所以空间复杂度是O(1);

改进：

我们可以对冒泡排序进行改进，使得它的时间复杂度在大多数顺序的情况下，减小到O(n);

1.加一个标志位，如果没有进行交换，将标志位置为false，表示排序完成。

代码地址：https://jsbin.com/seyonuq/edit?js,console 

  1. const arr = [1, 20, 10, 30, 




    
22, 11, 55, 24, 31, 88, 12, 100, 50];
  3. function swap(arr, i, j){
  4.   const temp = arr[i];
  5.   arr[i] = arr[j];
  6.   arr[j] = temp;
  7. }
  9. for




    
(let i = 0; i < arr.length - 1; i++){
  10.   let flag = false;
  11.   for(let j = 0; j < arr.length - 1 - i; j++){
  12.     if(arr[j] > arr[j+1]){
  13.       swap(arr, j, j+1);
  14.       flag = true;
  15.     }




    

  16.   }
  18.   if(!flag){
  19.     break;
  20.   }
  21. }
  22. 




    

  23. console.log(arr);  //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]

2.记录最后一次交换的位置， 因为最后一次交换的数，是在这一次排序当中最大的数，之后的数都比它大。在最佳状态时，时间复杂度也会缩小到O(n);

代码地址：https://jsbin.com/moruvet/edit?js,console 

  1. const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50 ,




    
112];
  3. function swap(arr, i, j){
  4.   let temp = arr[i];
  5.   arr[i] = arr[j];
  6.   arr[j] = temp
  7. }




    

  9. function improveBubble(arr, len){
  10.   for(let i = len - 1; i >= 0; i--){
  11.     let pos = 0;
  12.     




    
for(let j = 0; j < i; j++){
  13.       if(arr[j] > arr[j+1]){
  14.         swap(arr, j, j+1);
  15.         pos = j + 1;
  16.       }




    

  17.     }
  18.     len = pos + 1;
  19.   }
  20.   return arr;
  21. }




    

  23. console.log(improveBubble(arr, arr.length));  //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]
选择排序

选择排序，即每次都选择最小的，然后换位置

思路：

第一遍，从数组中选出最小的，与第一个元素进行交换；第二遍，从第二个元素开始，找出最小的，与第二个元素进行交换；依次循环，完成排序

图例：

代码实现： 

  1. const




    
 arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];
  3. function swap(arr, i, j){
  4.   




    
var temp = arr[i];
  5.   arr[i] = arr[j];
  6.   arr[j] = temp;
  7. }
  8. 




    

  9. function selectionSort(arr){
  10.   for(let i = 0; i < arr.length - 1; i++){
  11.     let index = i;
  12.     




    
for(let j = i+1; j < arr.length; j++){
  13.       if(arr[index] > arr[j]){
  14.         index = j;
  15.       }
  16.     }




    

  17.     swap(arr, i, index);
  18.   }
  19.   return arr;
  20. }




    

  22. console.log(selectionSort(arr)); //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]

代码地址：https://jsbin.com/tagutas/edit?js,console

性能：

  • 时间复杂度：平均时间复杂度是O(n^2)，这是一个不稳定的算法，因为每次交换之后，它都改变了后续数组的顺序。

  • 空间复杂度：辅助空间是常数，空间复杂度为O(1);

插入排序

插入排序，即将元素插入到已排序好的数组中

思路：

首先，循环原数组，然后，将当前位置的元素，插入到之前已排序好的数组中，依次操作。

图例：

代码实现： 

  1. const arr = [1, 20, 10, 30, 22, 11, 55, 24, 0, 31, 88, 12, 100




    
, 50 ,112];
  3. function insertSort(arr){
  4.   for(let i = 0; i < arr.length; i++){
  5.     let temp = arr[i];




    

  6.     for(let j = 0; j < i; j++){
  7.       if(temp < arr[j] && j === 0){
  8.         arr.splice(i, 




    
1);
  9.         arr.unshift(temp);
  10.         break;
  11.       }else if




    
(temp > arr[j] && temp < arr[j+1] && j < i - 1){
  12.         arr.splice(i, 1);
  13.         arr.splice(j+1, 0, temp);
  14.         break;
  15.       }




    

  16.     }
  17.   }
  18.   




    
return arr;
  19. }
  21. console.log(insertSort(arr));  //[ 0, 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]

代码地址：https://jsbin.com/punuta/edit?js,console

性能：

  • 时间复杂度：平均算法复杂度为O(n^2)

  • 空间复杂度：辅助空间为常数，空间复杂度是O(1)

我们仨之间

其实，三个算法都是难兄难弟，因为算法的时间复杂度都是在O(n^2)。在最坏情况下，它们都需要对整个数组进行重新调整。只是选择排序比较不稳定。

快速排序

快速排序，从它的名字就应该知道它很快，时间复杂度很低，性能很好。它将排序算法的时间复杂度降低到O(nlogn)

思路：

首先，我们需要找到一个基数，然后将比基数小的值放在基数的左边，将比基数大的值放在基数的右边，之后进行递归那两组已经归类好的数组。

图例：

原图片太大，放一张小图，并且附上原图片地址，有兴趣的可以看一下：

原图片地址

代码实现： 

  1. const arr = [30, 32, 6, 24, 37, 32, 45, 21, 38, 23, 47];
  2. 




    

  3. function quickSort(arr){
  4.   if(arr.length <= 1){
  5.     




    
return arr;
  6.   }
  7.   let temp = arr[0];
  8.   




    
const left = [];
  9.   const right = [];
  10.   for(var i = 1; i < arr.length; i++){
  11.     




    
if(arr[i] > temp){
  12.       right.push(arr[i]);
  13.     }else{
  14.       left.push(arr[i]);




    

  15.     }
  16.   }
  17.   




    
return quickSort(left).concat([temp], quickSort(right));
  18. }
  20. console.log(quickSort(arr));

代码地址：https://jsbin.com/jeqayi/edit?js,console

性能：

  • 时间复杂度：平均时间复杂度O(nlogn)，只有在特殊情况下会是O(n^2)，不过这种情况非常少

  • 空间复杂度：辅助空间是logn，所以空间复杂度为O(logn)

归并排序

归并排序，即将数组分成不同部分，然后注意排序之后，进行合并

思路：

首先，将相邻的两个数进行排序，形成n/2对，然后在每两对进行合并，不断重复，直至排序完。

图例：

代码实现： 

  1. //迭代版本




    

  2. const arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
  3. 




    

  4. function mergeSort(arr){
  5.   const len = arr.length;
  6. 




    

  7.   for(let seg = 1; seg < len; seg += seg){
  8.     let arrB = [];
  9.     




    
for(let start = 0; start < len; start += 2*seg){
  10.       let row = start, mid = Math.min(start+seg, len), heig = Math.min(start + 2*seg, len);
  11.       let start1 = start, end1 = mid;




    

  12.       let start2 = mid, end2 = heig;
  13.       while(start1 < end1 && start2 < end2){
  14.         arr[start1] < arr[start2] ? arrB.push(arr[start1++]) : arrB.push(arr[start2++]);




    

  15.       }
  16.       while(start1 < end1){
  17.         arrB.push(arr[start1++]);




    

  18.       }
  19.       




    
while(start2 < end2){
  20.         arrB.push(arr[start2++]);
  21.       }
  22.     }




    

  23.     arr = arrB;
  24.   }
  25. 




    

  26.   return arr;
  27. }
  28. 




    

  29. console.log(mergeSort(arr));

代码地址：https://jsbin.com/qazupis/edit?js,console 

  1. //递归版
  2. const arr = [3,44,




    
38,5,47,15,36,26,27,2,46,4,19,50,48];
  4. function




    
 mergeSort(arr, seg = 1){
  5.   const len = arr.length;
  6.   if(seg > len){
  7.     return






请到「今天看啥」查看全文


推荐文章
OSC开源社区  ·  RAG市场的2024：随需而变，从狂热到理性
2 天前
程序猿  ·  41岁DeepMind天才科学家去世：长期受抑郁困扰、曾诉AI工作压力太大、为利润而工作
2 天前
OSC开源社区  ·  宇树王兴兴早年创业分享引围观
5 天前
OSC开源社区  ·  AI大模型如何影响基础软件行业中的开发工具与环境？
6 天前
程序猿  ·  惊世骇俗！梁文锋硕士学位论文赏析：让人拍案叫绝！
5 天前
笑点研究所  ·  树：好不容易隐形了，我特么招你惹你了？
8 年前
深圳特区报  ·  微看 | 春游踏青不识花木？你需要一本《草木深圳》
7 年前
果库  ·  除了 MUJI，还有哪些不错的家居设计商店？
7 年前
山东大学  ·  揭秘 | 山大“双创”成果展，不只是总理考察过那么简单
7 年前
河北卫视  ·  【母亲节活动】礼物领取中……
7 年前
Sov5搜索   ·   小百科   ·   今天看啥   ·   移动版
51好读 - 好文章就要读起来!