排序算法——稳定性及其汇总

目录

9、排序算法的稳定性及其汇总

9.1 排序算法的稳定性

9.2 常见的坑

9.3 工程上对排序的改进

---

9、排序算法的稳定性及其汇总

9.1 排序算法的稳定性

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

误区：认为稳定性是随数据的差异会影响算法的时间空间复杂度【容易产生的认知】

不具备稳定性的排序： 选择排序、快速排序、堆排序

具备稳定性的排序： 冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

总结：只要有跨度的交换，就会丧失稳定性。相邻交换的则不会。

不具有稳定性的排序算法：

选择排序

快速排序

堆排序更是无视稳定性，他只认识孩子和父亲，进行大跨度无序交换

具有稳定性的排序算法：

冒泡排序

插入排序

归并排序关键在于merge的时候，要先拷贝左边的数，而用归并解决小和问题的时候，要先拷贝右边的数，则丧失稳定性

目前没有找到时间复杂度0（N*logN），额外空间复杂度0（1），又稳定的排序。

9.2 常见的坑

1. 归并排序的额外空间复杂度可以变成0（1），但是非常难，不需要掌握，有兴趣可以搜“归并排序内部缓存法”

2. “原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变成O（N~2）

3. 快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01stable sort"

4. 所有的改进都不重要，因为目前没有找到时间复杂度0（N*logN），额外空间复杂度0（1），又稳定的排序。

5. 有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官。

9.3 工程上对排序的改进

1）充分利用O（N*IogN）和0（N^2）排序各自的优势 2）稳定性的考虑

在快速排序中，当样本量小于60的时候，插入排序时间复杂度相当，当常数操作复杂度极低，因此可以将2种混合起来。

public class Test {
    public static void quickSort(int[] arr, int 1, int r) {
        if(1 ==r){
            return;
        }
        if (1 >r - 60) {//插入排序
            在arr[1..r]插入排序
            O（Nへ2）小样本量的时候，跑的快
            return;
        }
        swap(arr, 1 + (int) (Math.random() * (r - 1 + 1)), r);//快速排序
        int[] p = partition(arr, 1, r);
        quickSort(arr, 1, p[0] - 1); //‹ 区
        quickSort(arr, p[1] + 1, r); // > 区
    }
}

大样本调度快选择 O（N*IogN)；小样本选择插入，跑得快 0（N^2)