🧠 快速排序 · 思考题与练习详解
“理解快排的关键不在于记住代码，而在于理解随机化的力量与分治的本质差异。”
🧩 思考题一：随机化的数学保证
❓ 问题
为什么随机化能保证期望 O(nlogn)？
💡 详解
核心思想：随机化避免了对手精心构造的最坏情况，让算法在概率平均意义上表现优秀。
🔹 最坏情况分析
固定选择最后一个元素作为 pivot：
1
2
3
4
5
|
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high];
}
|
攻击者可以构造已排序数组，使每次划分都极不均衡：
1
2
3
4
5
| [1, 2, 3, 4, 5, 6, 7, 8]
pivot=8 → [1,2,3,4,5,6,7] [8]
pivot=7 → [1,2,3,4,5,6] [7]
...
时间复杂度: O(n²)
|
🔹 随机化的数学证明
关键引理：在随机化快排中，任意两个元素被比较的概率 ≤ j−i+12
证明思路：
定义指示随机变量：
Xij={10如果 i 和 j 被比较否则
总比较次数：
X=i=1∑n−1j=i+1∑nXij
期望比较次数：
E[X]=i=1∑n−1j=i+1∑nE[Xij]=i=1∑n−1j=i+1∑nj−i+12
计算这个双重求和：
E[X]=2k=2∑nkn−k+1=2nk=2∑nk1−2k=2∑n1
E[X]=2n(Hn−1)−2(n−1)=2nHn−4n+2
其中 Hn 是调和级数，Hn≈lnn+γ
因此：
E[X]=O(nlogn)
🎯 代码验证
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <iostream>
#include <vector>
#include <random>
#include <chrono>
class QuickSortAnalyzer {
private:
long long comparisonCount;
public:
QuickSortAnalyzer() : comparisonCount(0) {}
int randomizedPartition(std::vector<int>& arr, int low, int high) {
static std::random_device rd;
static std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(low, high);
int pivotIndex = dis(gen);
std::swap(arr[pivotIndex], arr[high]);
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
comparisonCount++;
if (arr[j] <= pivot) {
std::swap(arr[++i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
void randomizedQuickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pivotIndex = randomizedPartition(arr, low, high);
randomizedQuickSort(arr, low, pivotIndex - 1);
randomizedQuickSort(arr, pivotIndex + 1, high);
}
}
void analyzePerformance() {
std::vector<int> sizes = {100, 1000, 10000, 100000};
for (int size : sizes) {
comparisonCount = 0;
std::vector<int> arr(size);
std::iota(arr.begin(), arr.end(), 1);
randomizedQuickSort(arr, 0, arr.size() - 1);
double expected = 2 * size * log(size);
double ratio = static_cast<double>(comparisonCount) / expected;
std::cout << "大小 " << size << ": 比较次数=" << comparisonCount
<< ", 理论期望≈" << static_cast<int>(expected)
<< ", 比率=" << ratio << std::endl;
}
}
};
|
输出示例：
1
2
3
| 大小 100: 比较次数=812, 理论期望≈921, 比率=0.88
大小 1000: 比较次数=12945, 理论期望≈13816, 比率=0.94
大小 10000: 比较次数=188312, 理论期望≈184206, 比率=1.02
|
⚡ 思考题二：非递归版快速排序
❓ 问题
如何实现非递归版快速排序？
💡 详解
使用栈模拟递归调用，避免函数调用开销：
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <iostream>
#include <vector>
#include <stack>
#include <random>
struct Range {
int low;
int high;
Range(int l, int h) : low(l), high(h) {}
};
void iterativeQuickSort(std::vector<int>& arr) {
std::stack<Range> stack;
stack.push(Range(0, arr.size() - 1));
while (!stack.empty()) {
Range current = stack.top();
stack.pop();
int low = current.low;
int high = current.high;
if (low >= high) continue;
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
if (arr[j] <= pivot) {
std::swap(arr[++i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
int pivotIndex = i + 1;
int leftSize = pivotIndex - low;
int rightSize = high - pivotIndex;
if (leftSize < rightSize) {
stack.push(Range(pivotIndex + 1, high));
stack.push(Range(low, pivotIndex - 1));
} else {
stack.push(Range(low, pivotIndex - 1));
stack.push(Range(pivotIndex + 1, high));
}
}
}
int main() {
std::vector<int> arr = {7, 2, 1, 6, 8, 5, 3, 4};
iterativeQuickSort(arr);
std::cout << "非递归快排结果: ";
for (int num : arr) std::cout << num << " ";
std::cout << std::endl;
}
|
🔄 执行过程演示
1
2
3
4
5
6
7
8
9
10
| 初始栈: [(0,7)]
弹出 (0,7)，分区后 pivotIndex=3
栈状态: [(4,7), (0,2)]
弹出 (4,7)，分区后 pivotIndex=6
栈状态: [(0,2), (5,6), (4,4)]
弹出 (0,2)，分区后 pivotIndex=1
栈状态: [(5,6), (4,4), (2,2), (0,0)]
...
|
📊 递归 vs 迭代对比
| 特性 | 递归版本 | 迭代版本 |
|---|
| 空间复杂度 | O(logn) 栈空间 | O(logn) 显式栈 |
| 函数调用 | 有开销 | 无开销 |
| 调试难度 | 容易（调用栈清晰） | 较难 |
| 最坏情况栈深度 | O(n) | O(logn)（通过优化） |
🎯 思考题三：内存排序的适用性
❓ 问题
为什么快排比归并排序更适合内存排序？
💡 详解
🔹 缓存友好性分析
1
2
3
4
5
6
7
8
9
10
11
|
for (int j = low; j < high; ++j) {
if (arr[j] <= pivot) {
std::swap(arr[++i], arr[j]);
}
}
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
|
🔹 实际性能测试
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
| void performanceComparison() {
std::vector<int> sizes = {1000, 10000, 100000, 1000000};
for (int size : sizes) {
std::vector<int> arr1(size), arr2(size);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(1, size);
for (int i = 0; i < size; ++i) {
int val = dis(gen);
arr1[i] = arr2[i] = val;
}
auto start1 = std::chrono::high_resolution_clock::now();
quickSort(arr1, 0, arr1.size() - 1);
auto end1 = std::chrono::high_resolution_clock::now();
auto start2 = std::chrono::high_resolution_clock::now();
mergeSort(arr2, 0, arr2.size() - 1);
auto end2 = std::chrono::high_resolution_clock::now();
auto time1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1);
auto time2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2);
std::cout << "大小 " << size << ": 快排=" << time1.count()
<< "μs, 归并=" << time2.count() << "μs, 比率="
<< static_cast<double>(time1.count()) / time2.count() << std::endl;
}
}
|
典型结果：
1
2
3
| 大小 1000: 快排=156μs, 归并=243μs, 比率=0.64
大小 10000: 快排=1892μs, 归并=3124μs, 比率=0.61
大小 100000: 快排=23456μs, 归并=39871μs, 比率=0.59
|
📊 综合对比
| 特性 | 快速排序 | 归并排序 |
|---|
| 平均时间复杂度 | O(nlogn) | O(nlogn) |
| 最坏时间复杂度 | O(n2) | O(nlogn) |
| 空间复杂度 | O(logn) | O(n) |
| 缓存友好性 | ✅ 优秀 | ❌ 较差 |
| 稳定性 | ❌ 不稳定 | ✅ 稳定 |
| 适用场景 | 内存排序、通用目的 | 外部排序、链表排序 |
🔍 思考题四：分治结构的本质差异
❓ 问题
归并和快排的"分治结构"本质差异是什么？
💡 详解
🔹 工作分配对比
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void quickSort(vector<int>& arr, int low, int high) {
if (low >= high) return;
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
|
🔹 分治哲学差异
| 方面 | 归并排序 | 快速排序 |
|---|
| 分治时机 | 先分后治 | 先治后分 |
| 工作重心 | 合并阶段 | 分区阶段 |
| 确定性 | 确定性的划分 | 随机化的划分 |
| 子问题关系 | 子问题独立 | 子问题通过pivot关联 |
🔹 递归树对比
归并排序递归树：
1
2
3
4
5
6
7
| [0..7]
/ \
[0..3] [4..7]
/ \ / \
[0..1] [2..3] [4..5] [6..7]
/ \ / \ / \ / \
[0][1] [2][3] [4][5] [6][7]
|
- 划分是确定的（总是中点）
- 所有叶子在同一层
- 合并操作在回溯时进行
快速排序递归树：
1
2
3
4
5
6
7
| (pivot=4)
/ \
/ \ / \
/ \ / \ / \
|
- 划分是随机的（取决于pivot选择）
- 叶子在不同深度
- 分区操作在递归前完成
🎯 工程意义
这种差异导致了不同的优化策略：
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
|
void optimizedMergeSort(vector<int>& arr, int left, int right) {
if (right - left < 16) {
insertionSort(arr, left, right);
return;
}
}
void optimizedQuickSort(vector<int>& arr, int low, int high) {
if (high - low < 16) {
insertionSort(arr, low, high);
return;
}
int mid = low + (high - low) / 2;
if (arr[mid] < arr[low]) std::swap(arr[low], arr[mid]);
if (arr[high] < arr[low]) std::swap(arr[low], arr[high]);
if (arr[high] < arr[mid]) std::swap(arr[mid], arr[high]);
std::swap(arr[mid], arr[high - 1]);
int pivotIndex = partition(arr, low, high);
}
|
🚀 扩展练习
🧩 练习1：三路快速排序
处理大量重复元素的优化版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void threeWayQuickSort(std::vector<int>& arr, int low, int high) {
if (low >= high) return;
int pivot = arr[high];
int lt = low;
int gt = high;
int i = low;
while (i <= gt) {
if (arr[i] < pivot) {
std::swap(arr[lt++], arr[i++]);
} else if (arr[i] > pivot) {
std::swap(arr[i], arr[gt--]);
} else {
i++;
}
}
threeWayQuickSort(arr, low, lt - 1);
threeWayQuickSort(arr, gt + 1, high);
}
|
🧩 练习2：尾递归优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void tailRecursiveQuickSort(std::vector<int>& arr, int low, int high) {
while (low < high) {
int pivotIndex = partition(arr, low, high);
if (pivotIndex - low < high - pivotIndex) {
tailRecursiveQuickSort(arr, low, pivotIndex - 1);
low = pivotIndex + 1;
} else {
tailRecursiveQuickSort(arr, pivotIndex + 1, high);
high = pivotIndex - 1;
}
}
}
|
🧩 练习3：内省排序（IntroSort）
STL std::sort 的实现原理：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void introSort(std::vector<int>& arr, int low, int high, int depthLimit) {
if (high - low < 16) {
insertionSort(arr, low, high);
return;
}
if (depthLimit == 0) {
heapSort(arr, low, high);
return;
}
int pivotIndex = partition(arr, low, high);
introSort(arr, low, pivotIndex - 1, depthLimit - 1);
introSort(arr, pivotIndex + 1, high, depthLimit - 1);
}
void sort(std::vector<int>& arr) {
int depthLimit = 2 * log2(arr.size());
introSort(arr, 0, arr.size() - 1, depthLimit);
}
|
💎 总结
通过这四个思考题，我们深入理解了：
- 随机化的力量：数学证明期望复杂度的保证
- 迭代实现的技巧：用栈模拟递归，优化空间使用
- 工程实践选择：缓存友好性决定内存排序的效率
- 算法设计哲学：分治时机的差异导致完全不同的特性
🎯 “快速排序教会我们的不仅是排序，更是如何在不确定性中寻找确定性的性能保证。”
这些深入理解为我们学习更高级的随机化算法和工程优化奠定了坚实基础。