Arrays.sort()的底层实现

练习：912. 排序数组

稳定排序&不稳定排序

对于序列中的相同元素，如果排序之后它们的相对位置没有发生改变，则称该排序算法为「稳定排序」，反之则为「不稳定排序」
应用：
如果单单排序 int 数组，那么稳定性没有什么意义。但如果排序一些结构比较复杂的数据，那么稳定性排序就有更大的优势了。

比如说你有若干订单数据，已经按照订单号排好序了，现在你想对订单的交易日期再进行排序：

如果用稳定排序算法（比如归并排序），那么这些订单不仅按照交易日期排好了序，而且相同交易日期的订单的订单号依然是有序的。

但如果你用不稳定排序算法（比如快速排序），那么虽然排序结果会按照交易日期排好序，但相同交易日期的订单的订单号会丧失有序性。

在实际工程中我们经常会将一个复杂对象的某一个字段作为排序的 key，所以应该关注编程语言提供的 API 底层使用的到底是什么排序算法，是稳定的还是不稳定的，这很可能影响到代码执行的效率甚至正确性。

1. 快速排序

2022/2 - 7/27

算法思想：以最左边的数字为基准数，两个哨兵分别位于数组的左右两端，右端的先出发，遇到比基准数小或相等的就停下，此时左边哨兵出发，遇到比基准数大的的就停下，然后交换两个数字的，重复这个过程，直到两个哨兵相遇，此时将相遇时的数字与基准数交换，这样基准数左边都是比基准数小或相等的，右边都是比基准数大的，分别在左右两部分做递归操作即可；

void sort(int[] nums, int lo, int hi) {
    if (lo >= hi) {
        return;
    }

    int p = partition(nums, lo, hi);
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

int partition(int[] nums, int lo, int hi) {
    int pivot = nums[lo];
    int i = lo + 1, j = hi;

    while (i <= j) {                              // 注意边界
        while (j > lo && nums[j] > pivot) {    
            j--;
        }
        while (i < hi && nums[i] <= pivot) {
            i++;
        }
        if (i >= j) {
            break;
        }
        swap(nums, i, j);
    }
    swap(nums, lo, j);
    return j;
}

void shuffle(int[] nums) {
    Random rand = new Random();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        swap(nums, i, i + rand.nextInt(n - i));
    }
}

void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

复杂度分析：

partition 执行的次数是二叉树节点的个数，每次执行的复杂度就是每个节点代表的子数组 nums[lo…hi] 的长度，所以总的时间复杂度就是整棵树中「数组元素」的个数。

假设数组元素个数为 N，那么二叉树每一层的元素个数之和就是 O(N)；分界点分布均匀的理想情况下，树的层数为 O(logN)，所以理想的总时间复杂度为 O(NlogN)。

由于快速排序没有使用任何辅助数组，所以空间复杂度就是递归堆栈的深度，也就是树高 O(logN)。

快速排序的效率存在一定随机性，如果每次 partition 切分的结果都极不均匀：
快速排序就退化成选择排序了，树高为 O(N)，每层节点的元素个数从 N 开始递减，总的时间复杂度为：

N + (N - 1) + (N - 2) + … + 1 = O(N^2)
所以我们说，快速排序理想情况的时间复杂度是 O(NlogN)，空间复杂度 O(logN)，极端情况下的最坏时间复杂度是 O(N^2)，空间复杂度是 O(N)。

例题：

力扣算法 Java 刷题笔记【快速排序】hot100（一）快速排序 快速选择算法 1

2. 归并排序

2022/2/22

3. 插入排序

2022/7