稳定性

同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定性的；否则就没有。

比如[1,4,5,4]排序之后就是[1,4,4,5]，对于两个4，如果还是保持之前的顺序，那就是有稳定性。

什么时候需要稳定性？

假设现在有一堆学生的数据，每个学生有两个字段：class班级和age年龄。首先我们按年龄进行排序，排序之后再按班级排序，第二次排序是稳定的，那么每个班级里的学生都是按年龄排序的。稳定性就是保持相同值之间的相对次序。在实际的一些处理场景中还是很有用的。

排序算法总结

不具备稳定性的排序

选择排序、快速排序、堆排序

具备稳定性的排序

冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

排序算法总结

如何选择排序算法

从上述表格中可以选出三种最优的，下面进行分析优缺点：

• 归并排序：有稳定性；空间复杂度较高
• 快速排序：常数项指标最低，意味最快；但没有稳定性，空间复杂度无法做到O(1)
• 堆排序：空间使用最少

基于比较的排序，能否做到时间复杂度少于O(N*logN)？

目前不行

在时间复杂度为O(N*logN)的前提下，是否能做到空间复杂度少于O(N)，并具备稳定性？

目前不行

结论：如果要选择一种排序的话，一般来说，选择快速排序（常数项指标比归并排序最低），如果有空间限制，就选择堆排序，需要稳定性用归并排序。        目前没有找到时间复杂度O(N*logN)，额外空间复杂度为O(1)，又稳定的排序。

常见的坑

• 归并排序的额外空间复杂度可以变成O(1)，但是非常难，不需要掌握，有兴趣可以搜“归并排序 内部缓存法”（这种做法会失去稳定性，并且代码较难实现，不如直接使用堆排序）。
• “原地归并排序”的帖子都是垃圾，虽然会让归并排序的空间复杂度降为O(1)，但同时会让时间复杂度变成 O(N^2)，不如直接用插入排序
• 快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01 stable sort”。（会将空间复杂度提高为O(N)，不如直接用归并）
• 所有的改进都不重要，因为目前没有找到时间复杂度O(N*logN)，额外空间复杂度为O(1)，又稳定的排序。
• 有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官。（经典的快排做不到稳定性，快排的0和1标准相当于奇偶标准）

工程上对排序的改进

• 充分利用O(N*logN)和O(N^2)排序各自的优势
• 稳定性的考虑

充分利用O(N*logN)和O(N^2)排序各自的优势

实际使用中，我们一般不会只使用一种算法，而是使用综合算法，比如快排+插入，也可以归并+插入。

快排+插入

比如说，经典的快排算法是这样的：

public static void quickSort(int[] arr, int l,int r){ 
    if(l==r) return;
    swap(arr, l+(int)(Math.random() * (R-L+1)), r); 
    int[] p = partition(arr,l,r); 
    quickSort(arr,l,p[0]-1); // 小于区 
    quickSort(arr,p[1]+1,r); // 大于区 
}
复制代码

如何改进？

当样本量大的时候，利用快排的调度思想，左右两部分进行递归，所以总体的调度方式是快排；但在小样本量下，对这小样本部分进行插入排序。也就是说快排+插入结合的方式。因为快排时间复杂度O(N*logN)，插入时间复杂度是O(N^2)，在小样本情况下，插入排序的瓶颈不明显，并且其常数时间很低，两个算法结合，就是结合了小样本上插入排序的常数时间低的优势与大样本上快速排序的调度优势。

当样本量比较小的时候，在小样本量上直接做插入排序。我们可以改成这样：

public static void quickSort(int[] arr, int l,int r){ 
   if(l==r) return;
   if(l>r-60){
       // 在arr[l...r]插入排序
       // O(N^2)小样本量的时候，跑得快
       return;
   }
   swap(arr, l+(int)(Math.random() * (R-L+1)), r); 
   int[] p = partition(arr,l,r); 
   quickSort(arr,l,p[0]-1); // 小于区 
   quickSort(arr,p[1]+1,r); // 大于区 
}
复制代码

系统中的排序算法

很多系统自带了排序算法，内部是怎么做的？

一般来说，如果是基础类型，使用的是快排，如果是非基础类型（自定义类型），就用的归并排序。

这种做法是基于稳定性的考量。如果是基础类型，会认为稳定性是没有用的，就默认使用常数时间比较低的快速排序，如果是非基础类型的数据，系统无法判定你是否需要稳定性，就使用归并排序来保证稳定性。

在C/C++/Java的底层，底层库的排序，代码非常多，在极致优化排序算法，但归根结底就是利用各个排序的优势，进行拼装结合。

对于算法的优化，都是从稳定性、复杂度这两个维度进行考量的。