概览：
前置知识：讲解007-时间复杂度和空间复杂度-分析随机行为的时间复杂度的部分 007笔记
经典随机快速排序流程讲解
荷兰国旗问题优化随机快速排序流程讲解
荷兰国旗问题优化后的过程： 在当前范围上选择一个数字x，利用荷兰国旗问题进行数组的划分，<x =x >x 对<x范围重复这个过程，对>x范围重复这个过程
荷兰国旗问题的优化点：选出一个数字x，数组在划分时会搞定所有值是x的数字
快速排序的时间和空间复杂度分析
核心点：怎么选择数字？
选择的数字是当前范围上的固定位置，比如范围上的最右数字，那么就是普通快速排序
选择的数字是当前范围上的随机位置，那么就是随机快速排序
普通快速排序，时间复杂度O(n^2)，额外空间复杂度O(n)
随机快速排序，时间复杂度O(n * logn)，额外空间复杂度O(logn)
关于复杂度的分析，进行定性的说明，定量证明略，因为证明较为复杂
算法导论-7.4.2有详细证明
1 经典随机快速排序流程
以一个例子为例：
1
无序数组[6 2 4 1 5 9]
每一轮的规则如下：
我将每一步都详细记录了：
接着将在两侧发生递归，在两侧随机选择数，最终一定会使得整个数组有序。
代码
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
public void quickSort(int[] arr, int l, int r) {
if (l >= r) return;
int x = arr[l + (int) (Math.random() * (r - l + 1))];//随机选择一个数
int mid = partition1(arr, l, r, x);
quickSort(arr, l, mid - 1);
quickSort(arr, mid + 1, r);
}
//注意返回的是x的最终位置
public int partition1(int[] arr, int l, int r, int x) {
int a = l, xi = -1;//xi就是用来记录x的位置的
for (int i = l; i <= r; i++) {
if (arr[i] <= x) {
swap(arr, i, a);
if (arr[a] == x) xi = a;
a++;
}
}
swap(arr, xi, a - 1);
return a - 1;
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
用上面的代码可以测试https://leetcode.cn/problems/sort-an-array/description/
其实这也显示了这个经典算法的弊端。当随机选择x之后，如果有一堆数字和x相同，那么这个算法就很慢了
因此就有了荷兰国旗问题优化随机快速排序来优化上面出现的这个情况。
2 荷兰国旗问题优化随机快速排序
上面的流程可以看出比x小的始终都在a这个边界的左侧，现在利用荷兰国旗问题优化，将整个数组分成三个部分：
- 小于x
- 等于x
- 大于x
思路如下：还是拿i去扫描遍历一遍数组
- 小于x，交换a，i位置上的数，a++且i++
- 等于x，i++
- 大于x，交换b，i位置上的数，b–且i不变
以刚才的无序数组[6 2 4 1 5 9]为例，遍历一轮看看上面的思路到底是个什么意思。
这个例子没有体现如果有两个或者多个4会怎样，但是如果是有多个4，其实最终从a到b都是4，也就是说a到b最终更新成==x区域的左右边界
代码
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
//荷兰国旗问题
public static int first, last;
public void quickSort(int[] arr, int l, int r) {
if (l >= r) return;
int x = arr[l + (int) (Math.random() * (r - l + 1))];
partition2(arr, l, r, x);
// 为了防止底层的递归过程覆盖全局变量
// 这里用临时变量记录first、last
// first、last包括这2个位置都是等于x的
int left = first;
int right = last;
quickSort(arr, l, left - 1);
quickSort(arr, right + 1, r);
}
public void partition2(int[] arr, int l, int r, int x) {
first = l;
last = r;
int i = l;
while (i <= last) {
if (arr[i] < x) {
swap(arr, first++, i++);
} else if (arr[i] == x) {
i++;
}else {
swap(arr, last--, i);
}
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
3 快速排序的时间和空间复杂度分析
之前在007节强调过，对于引入随机行为的算法（如快速排序），最差情况（如每次选到最大/最小值）发生的概率极低，分析其平均时间复杂度或期望时间复杂度更有意义。
比如生成一个数组，要求每个数字不一样，现在生成了索引0位置的数为8，万一是最差情况，那么索引为1位置的数生成的始终是8，那么此时时间复杂度就会评估成无穷大，这么估计就没有任何意义了。
同理，如果快速排序每次选择的数不是随机的，而是最左侧或者最右侧（比如下面就以最右侧为例），那么此时如果数组长这样：
1
[1,2,3,4,5,6]
那么每一轮其实就和冒泡/选择排序没有什么区别了，第一轮确定了6的位置是最后一个，第二轮确定5的位置是倒数第二个……
这时候时间复杂度就是\(O(n^2)\)，此时空间复杂度是\(O(N)\)
上面是情况最差的时候快速排序的时间复杂度分析。
现在分析比较好的情况：即选择的数（不管是随机选的还是其他方式选择的，最终导致这个数的结果位置就是钟点位置），导致可以用master公式来估计，那么\(T(N) = 2*T(N/2)+O(n)\)，即a = 2, b = 2, c = 1，根据master公式，得到时间复杂度就是\(O(N*logN)\)，这和归并排序时间复杂度一样。
那么空间复杂度呢？最佳是\(O(logN)\)
因为递归调用的层数就是\(logN\)
没错，测试数据有时候就会用最恶心的情况来为难你！（从上面的测试结果就可以看出）
总结
对于快速排序：
最差情况：时间复杂度\(O(n^2)\)，空间复杂度\(O(n)\)
最佳情况：时间复杂度\(O(NlogN)\)，空间复杂度\(O(logN)\)
如果是固定流程（选择x的位置是固定的，不管是最后还是最前，还是最中间），那么时间复杂度和空间复杂度就得按照最差情况来估计。
所以随机产生的x到底应该怎么估计时间复杂度呢？
数学家已经证明，如果按照均等的概率（1/N）来到某一个位置，对其求期望，时间复杂度是\(O(N*logN)\)，空间复杂度是\(O(logN)\)
要看详细证明可以看【算法导论-7.4.2】
另外-关于力扣912
其比较快的解法是计数排序。这里不做笔记。
