1.排序算法稳定性

稳定性是指同样大小的样本再排序之后不会改变相对次序

对基础类型来说，稳定性毫无意义

对非基础类型来说，稳定性有重要意义

有些排序算法可以实现成稳定的，而有些排序算法无论如何都实现不成稳定的

【不稳定】：选择排序、快排、堆、希尔

【可以做到稳定】：冒泡、插入、归并

2.排序算法总结

1）不基于比较的排序，对样本数据有严格要求，不易改写 2）基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用 3）基于比较的排序，时间复杂度的极限是\(O(N*logN)\) 4）时间复杂度\(O(N*logN)\)、额外空间复杂度低于\(O(N)\)、且稳定的基于比较的排序是不存在的。 5）为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并

如果考虑常数时间，在\(O(N*logN)\)的时间复杂度中，快排是最好的最快的，但是快排不稳定。

单纯追求速度快—–>快排

追求稳定性—->归并排序

追求空间复杂度—->堆排序

3.排序算法常见的坑

1）归并排序的额外空间复杂度可以变成O(1)，“归并排序 内部缓存法”，但是将变得不再稳定。–>既然如此，用堆不香吗？？

2）“原地归并排序” 是垃圾贴，会让时间复杂度变成\(O(N^2)\)

3）快速排序稳定性改进，论文“01 stable sort”，但是会对样本数据要求更多。但是为啥不用基数排序呢？？那样不是更香吗？

【一道垃圾题】在整型数组中，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的相对次序不变，所有偶数之间原始相对次序不变。时间复杂度做到O(N)，额外空间复杂度做到O(1)

这道题做不着稳定性，不然归并排序的partition就可以稳定了，那么归并排序也可以变成稳定了。

4.工程上对排序的改进

1)稳定性的考虑

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

【解释第1点】比如java的Arrays.sort方法，如果查看源码会发现，对于基础类型，采用快排，对于非基础类型，采用归并。为什么呢？

• 因为基础类型，稳定性没什么用，用快排就可以了（常数时间，快排比归并和堆都要快）。追求极致的性能和内存效率，因此选择了快速排序。
• 如果是非基础类型，最好保证稳定性。在对一个学生对象数组按年龄排序时，如果两个学生的年龄相同，我们通常希望他们原本的顺序能保持不变。如果使用不稳定排序算法，这种原始顺序就会丢失。归并排序通常比优化后的快速排序略慢，因为它需要额外的内存操作。但为了保证稳定性和性能的可靠性，这种牺牲是值得的。

【解释第2点】：

在实际工程中，优秀的排序库（如 Java 的 Arrays.sort() 和 C++ 的 std::sort）通常不会只用一种排序算法，而是会根据数据规模动态选择或混合使用。例如下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 插入排序 O(N^2) 常数项小
// 快排 O(N * logN) 常数项高
// N 很大的时候 快排
public static void quickSort(int[] arr, int L, int R) {
    if (L + 60 > R) {
        执行插入排序arr[L...R]
        return;
    }
    int[] p = partition(arr, L, R);
    quickSort(arr, L, p[0]-1);
    quickSort(arr,p[0]+ 1, R);
}
public static int[] partition(int[] arr, int L, int R) {

• 大数组用快排 ($O(N \log N)$):当数组的元素数量很大时，快速排序的渐近优势会压倒一切。它的 $O(N \log N)$ 复杂度确保了整体性能不会随数据量爆炸式增长。
• 小数组用插入排序 ($O(N^2)$):当快速排序的递归将数组分解到足够小的子数组时（例如上面代码中的 if (L + 60 > R)），其递归调用栈的开销和常数因子（常数时间）开始凸显出来。此时，继续使用快排反而不如直接切换到插入排序。
  • 为什么选择插入排序？
    1. 常数因子小: 插入排序的实现非常简单，内层循环的常数开销极低。
    2. 对小数组高效: 对于几十个元素的数组，插入排序的 $O(N^2)$ 性能退化不明显，其简单的操作甚至比快排更快。
    3. 对已排序数据高效: 快速排序在分解子数组后，子数组可能已经部分有序，而插入排序在这种情况下表现非常好，接近线性时间 $O(N)$。

• Previous
  【体系学习008】前缀树与基数排序
• Next
  【体系学习010】链表题目