排序算法的比较与总结

规范

排序算法必须原地排序，不能修改数组的引用，只能修改数组内容

排序算法必须向外界提供统一的接口，仅接收一个数组作为参数，不返回任何内容；

排序算法的稳定性

这是一个我们经常提到，但是却又没有怎么留意的问题。什么是排序算法的稳定性呢，就比如现在我们有一堆手牌， 假设，我现在手里面按顺序有梅花6，红桃A，方块6，红桃2，黑桃5。我们按点数大小（Ace视为 1 点）从小到大进行排序，此时，有两个数值相同的 6，如果说，当我们的排序算法完成之后，梅花6还是排在方块6之前的话，那么我们就可以说这个排序算法是稳定的。什么时候我们才会考虑稳定性呢？就拿刚才的例子举例，我们希望当数值相同时，扑克的花色按最初的相对顺序排列，这时候就需要用一个稳定的排序算法。

比如，现在我们要选出优秀的学生参与奥赛班，我们对学生进行一次摸底考试，根据学生的的成绩排序，然后再根据学生的年纪进行排序，我们就可以选出相同成绩下年级较小的同学参赛，若排序算法不稳定的话，则会导致我们用年龄再次排序时就达不到预期的效果了。如果只是单纯的对成绩排序，那么就不会再有什么想通数组的初始顺序的问题了，所以，系统为我们实现的排序方法，当你在对数字进行排序的时候，一般会采用不稳定的，对对象进行排序的时候，会采用稳定的算法。

但是排序算法的稳定性并不是绝对的，这取决于你写的排序算法的判别条件，众所周知，插入排序是稳定的排序算法，但是假设我们把代码写成这样：

/**
 * 对数组进行插入排序
 * @param {Array<number>} arr 需要进行排序的数组
 */
function insertionSort(arr) {
  // 默认认为第一个元素已经有序
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    let cur = arr[i];
    //向前找合适的插入位置，退出条件有两种可能，1、找到了合适的插入位置；2、找到了头了
    while (j > 0 && arr[j - 1] >= cur) {
      // 在每次查找插入位置的时候，都将当前元素向后挪一位。
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = cur;
  }
}

如果我们把向前插入的条件写成arr[j - 1] >= cur，那么很明显当方块6进行插入的时候，它一定会跑到梅花6的前面去，变成了不稳定的排序算法了。

因此，排序算法的稳定性其实还是一个相对的概念，如果你只要举得出例子证明它，那么它就是稳定或者不稳定的。

复杂度、稳定性与额外占用空间比较

排序算法名称	平均算法复杂度	是否稳定	是否额外空间复杂度
冒泡排序	O(N²)	是	否
选择排序	O(N²)	是	否
插入排序	O(N²)	是	否
希尔排序	O(N*logN)	否	否
快速排序	O(N*logN)	否	是，平均 O(logN)，最坏 O(N)
归并排序	O(N*logN)	是	是，O(N)
堆排序	O(N*logN)	否	否
桶排序	O(N+C)，其中 C=N*(logN-logM)	是	是，O(N+M)，N 为数据的数量级，M 为桶的数量级
基数排序	O(P(N+B))	是	是，O(N+M)，N 为数据的数量级，M 为桶的数量级

时间比较

我们各类的语言底层（如 JS 的Array.prototype.sort）提供的排序算法就是根据不同排序算法的稳定性、时间复杂度、空间复杂度差异，根据待排数据的性质，在三者之间进行取舍，从而实现更加高效的排序算法。

为了让大家直观的体验不同排序算法的差异，我对这些排序算法在 LeetCode 上都依次进行了提交（同一个排序算法 3 次提交，对结果取最接近平均值的那组数据），然后将结果进行了统计，结果如下：

排序算法名称	执行用时	执行用时击败所有提交区间	内存消耗	内存消耗击败所有提交区间	是否稳定
冒泡排序	6036ms	10.62%	50.7MB	89.30%	是
选择排序	7100 ms	6.86%	50.7 MB	86.00%	是
插入排序	1508 ms	39.15%	50.8 MB	85.80%	是
希尔排序	108 ms	95.09%	50.8 MB	85.80%	是
朴素快速排序	1512 ms	39.06%	57.5 MB	37.14%	否
三元取中快速排序	112 ms	91.57%	50.8 MB	83.76%	否
归并排序（递归版）	620 ms	48.71%	54.2 MB	49.68%	是
归并排序（非递归版）	120 ms	83.46%	51.6 MB	63.65%	是
堆排序	108 ms	95.09%	50.5 MB	93.77%	否
桶排序（采用了 10 个桶，每个桶采用直接插入排序）	4140 ms	17.98%	61.4MB	11.93%	是
基数排序	108ms	23.01%	57.6MB	8.21%	是
程序内置排序函数（以 JS 为例）	108 ms	95.09%	50.6 MB	92.65%	不讨论

最后通过这个表格验证了我们的结论，因为语言底层的排序算法通过对不同对数据环境下的数据采用了符合场景的排序算法，速度是最快的。（在 LeetCode 上提交各种排序算法的我，那个小丑竟然是我自己）。有的同学可能会说我学排序算法学了个寂寞，不如直接就用语言提供的排序算法就好啊，其实我们学习是为了掌握理论，为的知道其底层原理，便于解决各种生产中的 bug，是对能力的一种培养。再者，面试官再问你各种排序算法，你心里面也有个谱了吧。