前端工程师必学的经典排序算法

1. 前言

算法为王。

想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手；只有内功深厚者，前端之路才会走得更远。

本文中包含了 十大经典排序算法 的思想、代码实现、一些例子、复杂度分析。
这应该是目前最全的 JavaScript 十大经典排序算法 的讲解了吧。

准备

排序算法的稳定性： 排序前后两个相等的数相对位置不变，则算法稳定。

时间复杂度: 简单的理解为一个算法执行所耗费的时间，一般使用大O符号表示法，详细解释见时间复杂度

空间复杂度: 运行完一个程序所需内存的大小。

常见算法的复杂度（图片来源于网络）

以下算法最频繁的操作就是交换数组中两个元素的位置（按照正序或者是逆序），简单抽出一个函数如下：

 * 按照正序比较并交换数组中的两项
 *
 * @param {Array} ary
 * @param {*} x
 * @param {*} y
 */
function swap(ary, x, y) {
  if (x === y) return
  var temp = ary[x]
  ary[x] = ary[y]
  ary[y] = temp
}
复制代码

冒泡排序（Bubble-Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

解题思路：从数组的第一位开始，依次向后比较相邻元素的大小，如果前一个比后一个小，那么交换二者位置，直至数组末尾。
下一轮比较的起始位置加1，然后重复第一步。
重复1~2，直至排序结束。

//bubbleSort.js
Array.prototype.bubbleSort = function(){//数组的实例没有这个方法,但是其原型上有这个方法,我们照样可以调用这个方法
for(let i=0;i<this.length-1-i;i++){// 排序一轮以后 就不需要那么大的区间了  把最后一位去掉以后 的进行排序 每次都会区间变小
//  j < length - i - 1 是因为内层的 length-i-1 到 length-1 的位置已经排好了，不需要再比较一次。
  for(let j =0;j<this.length-1;j+=1){// length-1 是怕数组长度溢出 
 // i < length - 1 是因为外层只需要 length-1 次就排好了，第 length 次比较是多余的。
       // 打印相邻元素 
    if(this[j]>this[j+1]){
      const temp = this[j];
      this[j]=this[j+1];
      this[j+1]=temp
 } 
    }
      //this 就是数组
        console.log(this[j],this[j+1])
    }
}
const arr = [5,4,3,2,1]
arr.bubbleSort();
//时间复杂度O(n^2)
// 空间复杂度 O(1)
复制代码

优化：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

/ 冒泡排序（已优化）
//bubbleSort.js
Array.prototype.bubbleSort = function(){//数组的实例没有这个方法,但是其原型上有这个方法,我们照样可以调用这个方法
for(let i=0;i<this.length-1-i;i++){// 排序一轮以后 就不需要那么大的区间了  把最后一位去掉以后 的进行排序 每次都会区间变小
//  j < length - i - 1 是因为内层的 length-i-1 到 length-1 的位置已经排好了，不需要再比较一次。
  for(let j =0;j<this.length-1;j+=1){// length-1 是怕数组长度溢出 
 // i < length - 1 是因为外层只需要 length-1 次就排好了，第 length 次比较是多余的。
       // 打印相邻元素 
    let hasChange = false; // 提前退出冒泡循环的标志位
    if(this[j]>this[j+1]){
      const temp = this[j];
      this[j]=this[j+1];
      this[j+1]=temp;
      hasChange = true; // 表示有数据交换
 } 
    }
    if (!hasChange) break; // 如果 false 说明所有元素已经到位，没有数据交换，提前退出
    //this 就是数组
    console.log(this[j],this[j+1])
    }
}
const arr = [5,4,3,2,1]
arr.bubbleSort();
复制代码

选择排序

选择排序是先在数据中找出最大或最小的元素，放到序列的起始；然后再从余下的数据中继续寻找最大或最小的元素，依次放到排序序列中，直到所有数据样本排序完成。
复杂度分析：很显然，选择排序也是一个费时的排序算法，无论什么数据，都需要O(n*n) 的时间复杂度，不适宜大量数据的排序。

解题思路：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

//selectionSort.js
Array.prototype.selectionSort = function(){
 for(let i=0;i<this.length-1;i++){
   let indexMin = 0;//把第一位先设置为最小值
  for(let j =i;j<this.length;j+=1){
    if(this[j]<this[indexMin]){
    // 寻找最小的数
      indexMin =j;// 将最小数的索引保存
 } 
    }
     if(indexMin !== i){
      const temp = this[i];
      this[i]=this[indexMin];
      this[indexMin]=temp
      //this 就是数组
     }
    }
}
const arr = [5,4,3,2,1]
arr.selectionSort();
//时间复杂度O(n^2)
// 空间复杂度 O(1)
复制代码

插入排序

插入排序是先将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；然后从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，直到所有数据都完成排序；如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

解题思路：从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤 2~5

//insertionSort.js
Array.prototype.insertionSort = function(){
    for(let i =0;i<this.length;i++)    {
         const temp = this[1]
   let j =1;
     while(j>0){
         if(this[j-1]>temp){
             this[j]=this[j-1]
         }else{
             break;
         }
         j--;
     }
     this[j] = temp
    } 
}
const arr = [5,4,3,2,1]
arr.insertionSort();
//时间复杂度O(n^2)
// 空间复杂度 O(1)
复制代码

归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

解题思路：把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

//mergeSort 
Array.prototype.mergeSort = function(){
    const rec = (arr)=>{
        if(arr.length ===1){return arr ;}
        const mid = Math.floor(arr.length/2);
        const left = arr.slice(0,mid);
        const right= arr.slice(mid,arr.length);
        const orderLeft = rec(left);
        const orderRight = rec(right);
        const res =[]
        while(orderLeft.length||orderRight.length){
            if(orderLeft.length&&orderRight.length)             {
res.push(orderLeft[0]<orderRight[0]?orderLeft.shift():orderRight.shift())
               }else if(orderLeft.length){
                   res.push(orderLeft.shift())
               }else if(orderRight.length){
                   res.push(orderRight.shift())
               }
        }
        return res
    }
   const res = rec(this)
   res.forEach((n,i)=>{
       this[i]=n
   })
}
const arr = [5,4,3,2,1]
arr.mergeSort();
// 分 O(logn)
// 合 O(n)
//时间复杂度O(nlogn)
// 空间复杂度 O(1)
复制代码

快速排序

快速排序使用分治法策略来把一个数组分为两个子数组。首先从数组中挑出一个元素，并将这个元素称为「基准」，英文pivot。重新排序数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数组的中间位置。这个称为分区（partition）操作。之后，在子序列中继续重复这个方法，直到最后整个数据序列排序完成。

解题思路：从数列中挑出一个元素，称为 “哨兵”（pivot）；
重新排序数列，所有元素比哨兵值小的摆放在哨兵前面，所有元素比哨兵值大的摆在哨兵的后面（相同的数可以到任一边）。在这个分区退出之后，该哨兵就处于数列的中间位置。这个称为分区（partition）操作；
递归地把小于哨兵值元素的子数列和大于哨兵值元素的子数列排序。

//quickSort 
Array.prototype.quickSort = function(){
   const rec =()=>{
       if(arr.length ===1){return arr;}
       const left =[]
       const right = []
       const mid = arr[0];
       for(let i=1;i<arr.length;i+=1){
           if(arr[i]<mid){
               left.push(arr[i])
           }else {
               right.push(arr[i])
           }
       }
       return [...rec(left),mid,rec(right)]
   }
   const res = rec(this)
   res.forEach((n,i)=>{this[i]=n})
}
const arr = [5,4,3,2,1]
arr.quickSort();
// 递归 O(logn)
// 分区 O(n)
//时间复杂度O(nlogn)
// 空间复杂度 O(1)
复制代码

总结

刷题打卡第四天，选择面试经常问的排序算法、一起加油哇~

❤️ 感谢大家

如果你觉得这篇内容对你挺有有帮助的话：
点赞支持下吧，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）关注公众号给npy的前端秘籍，我们一起学习一起进步。
觉得不错的话，也可以阅读其他文章（感谢朋友的鼓励与支持???）

开启LeetCode之旅

LeetCode之双指针

LeetCode27、移除元素

参考：

手撕排序算法