快速排序、随机算法与第i大元素
快速排序
快速排序由 C.A.R. Hoare 于 1962 年提出，是实际应用中最广泛使用的排序算法之一，具有以下显著特点：
- 分治算法：核心思想是分治法
- 原地排序：只需要常数级别的额外空间
- 实用性极强：经过调优后通常比归并排序快 2 倍以上
- 缓存友好：具有良好的数据局部性
分治思想
分解：选择一个枢轴元素 (pivot) \(x\)，将数组划分为两个子数组，左侧 \(\leq x\)，右侧 \(\geq x\)
递归求解：对两个子数组递归执行快速排序
合并：由于排序是原地进行的，合并步骤不需要任何操作
关键在于线性时间的划分过程
形象地表示：
1 | [ ≤ x ] [ x ] [ ≥ x ] |
划分过程
1 | Partition(A, p, r) |
维护两个指针 \(i\) 和 \(j\)，遍历数组，将小于等于枢轴的元素交换到前面，大于枢轴的元素留在后面
划分过程的详细示例
以数组 [7, 8, 2, 6, 5, 1, 3, 4] 为例，选择 \(x = 4\) 作为枢轴：
1 | 初始: 7 8 2 6 5 1 3 [4] |
划分的正确性证明
循环不变量：在每次循环迭代中，数组被划分为四个区域
1 | [ ≤ x ] [ > x ] [ 未处理 ] [ x ] |
- \(A[p..i-1]\) 中的元素都 \(\leq x\)
- \(A[i..j-1]\) 中的元素都 \(> x\)
- \(A[j..r-1]\) 中的元素尚未被检查
- \(A[r] = x\) 是枢轴
对于大小为 \(n\) 的子数组，\(j\) 递增 \(n-1\) 次，每次 \(\Theta(1)\)，划分过程的时间复杂度为 \(\Theta(n)\)
Hoare 划分
1 | HOARE-PARTITION(A, p, r): |
与 Lomuto 划分的区别：Hoare 选第一个元素为枢轴，两个指针从两端扫描，平均交换次数更少，且对所有元素相同的输入不会退化到 \(O(n)\)
完整算法
1 | Quicksort(A, p, r) |
时间复杂度分析
假设所有输入元素互不相同，选择元素的下标等价于选择该元素，假设所有划分方式出现的概率相同
最好情况
每次划分恰好将数组分成两个大小相等的子数组：
\[T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)\]
这与归并排序的复杂度相同
“几乎最好”情况
考虑每次划分比例为 \(1:9\)：
1 | 层次 代价 左子树大小 右子树大小 |
- 递归树最短路径：\(\log_{10} n\) 层
- 递归树最长路径：\(\log_{10/9} n\) 层
- 每层总代价最多 \(cn\)
- 叶子节点总数 \(O(n)\)
\[cn \log_{10} n \leq T(n) \leq cn \log_{10/9} n + O(n)\]
\(\log_{10} n\) 和 \(\log_{10/9} n\) 都是 \(\Theta(\log n)\)，所以 \(T(n) = \Theta(n \log n)\)
*从这里可以得到结论：即使划分不完全均匀，只要划分比例是常数比（如 \(1:9\)、\(1:99\) 等），复杂度仍为 \(\Theta(n \log n)\)
最坏情况
每次划分都极端不均匀（一侧没有元素）：
\[T(n) = T(0) + T(n-1) + \Theta(n) = T(n-1) + \Theta(n) = \Theta(n^2)\]
输入已排好序（升序或降序）时出现最坏情况
注意：已排序输入是插入排序的最好情况，却是快速排序的最坏情况
好坏交替
设幸运划分 \(L(n) = 2U(n/2) + \Theta(n)\)，不幸运划分 \(U(n) = L(n-1) + \Theta(n)\)
将 \(U\) 代入 \(L\)：
\[L(n) = 2(L(n/2 - 1) + \Theta(n/2)) + \Theta(n) = 2L(n/2 - 1) + \Theta(n) = \Theta(n \log n)\]
即使好坏划分交替出现，总时间复杂度仍为 \(\Theta(n \log n)\)
如何避免最坏情况
策略一：选择中间元素作为枢轴，仍然存在使算法退化的输入排列，不能根本解决问题
策略二：随机选择枢轴，运行时间独立于输入排列，没有任何特定输入能导致最坏情况，最坏情况仅由随机数生成器决定
随机算法
随机算法是在执行过程中做出随机选择的算法，核心特性：
- 运行时间独立于输入排列
- 对手无法构造恶意输入
- 最坏情况由随机数生成器决定，而非输入
概率论基础
样本空间 \(S\)：所有基本事件的集合
事件 \(A\)：\(S\) 的一个子集
概率公理：\(\Pr\{A\} \geq 0\)，\(\Pr\{S\} = 1\)，若 \(A \cap B = \emptyset\) 则 \(\Pr\{A \cup B\} = \Pr\{A\} + \Pr\{B\}\)
容斥原理：\(\Pr\{A \cup B\} = \Pr\{A\} + \Pr\{B\} - \Pr\{A \cap B\} \leq \Pr\{A\} + \Pr\{B\}\)
期望：\(E[X] = \sum_x x \cdot \Pr\{X = x\}\)
期望的线性性：\(E[aX + Y] = aE[X] + E[Y]\)，无论 \(X\) 和 \(Y\) 是否独立都成立
独立性：若 \(X\) 和 \(Y\) 独立，则 \(E[XY] = E[X] \cdot E[Y]\)
指示器随机变量： 若 \(A\) 发生，\(I\{A\} = 1\)，否则为 \(0\) ，\(E[I\{A\}] = \Pr\{A\}\)
随机快速排序
1 | Randomized-Partition(A, p, r) |
随机选择枢轴，所有划分方式 \((0:n-1, 1:n-2, \ldots, n-1:0)\) 以等概率 \(\frac{1}{n}\) 出现
期望时间分析
定义指示器随机变量 \(X_k\)（\(k = 0, 1, \ldots, n-1\)）：当 Partition 产生 \(k:(n-k-1)\) 的划分时 \(X_k = 1\)
\[ E[X_k] = \Pr\{X_k = 1\} = \frac{1}{n} \]
令 \(T(n)\) 为运行时间随机变量
\[ T(n) = \sum_{k=0}^{n-1} X_k \cdot (T(k) + T(n-k-1) + \Theta(n)) \]
取期望，利用线性性和独立性：
\[ E[T(n)] = \frac{1}{n} \sum_{k=0}^{n-1} (E[T(k)] + E[T(n-k-1)]) + \Theta(n) \]
由于\(T(k)\) 和 \(T(n-k-1)\) 对称：
\[ E[T(n)] = \frac{2}{n} \sum_{k=0}^{n-1} E[T(k)] + \Theta(n) \]
这样得到了期望的递归式
由此可以得出随机快速排序的期望运行时间为 \(\Theta(n \log n)\)
点击查看代入法证明
用代入法证明 \(E[T(n)] \leq an \log n + b\)
不难知道 \(\sum_{k=1}^{n-1} k \log k \leq \frac{n^2}{2} \log n - \frac{n^2}{8}\)
\[ E[T(n)] \leq \frac{2}{n} \sum_{k=1}^{n-1} (ak \log k + b) + \Theta(n) \\ \leq \frac{2a}{n} \left(\frac{n^2}{2} \log n - \frac{n^2}{8}\right) + \frac{2b(n-1)}{n} + \Theta(n) \\ = an \log n - \frac{an}{4} + 2b + \Theta(n) \] 选择 \(b\) 足够大以处理初始条件，选择 \(a\) 足够大使得 \(an/4\) 能控制 \(\Theta(n)\) 和 \(2b\) 项
则 \(E[T(n)] \leq an \log n + b\)
直接计算比较次数
将输入排序后为 \(z_1 < z_2 < \ldots < z_n\)，定义指示器随机变量 \(X_{ij}\)： \[ X_{ij} = \begin{cases} 1 & \text{如果 } z_i \text{ 和 } z_j \text{ 在算法过程中被比较} \\ 0 & \text{否则} \end{cases} \]
则总比较次数 \(X = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} X_{ij}\)
引理：\(z_i\) 和 \(z_j\) 被比较当且仅当 \(z_i\) 或 \(z_j\) 是集合 \(\{z_i, z_{i+1}, \ldots, z_j\}\) 中第一个被选为枢轴的元素
在这些元素中任何元素被选为枢轴之前，它们都在同一子数组中
一旦 \(z_i\) 或 \(z_j\) 被选为枢轴，它会与同一子数组中所有元素比较
如果中间的 \(z_k\)（\(i < k < j\)）先被选为枢轴，\(z_i\) 和 \(z_j\) 被分到不同子数组，永远不会被比较 \[ \Pr\{X_{ij} = 1\} = \frac{2}{j - i + 1} \]
\[ E[X] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \frac{2}{j-i+1} = \sum_{i=1}^{n-1}\sum_{k=1}^{n-i} \frac{2}{k+1} \leq \sum_{i=1}^{n-1} 2H_n \leq 2n\ln n \]
其中 \(H_n \approx \ln n\) 是调和级数
精确结果：期望比较次数 \(2n\ln n \approx 1.39 n\log_2 n\)（\(n\lceil\log_2 n\rceil - 2^{\lceil\log_2 n\rceil} + 1\)），比归并排序（\(n\log_2 n\)）多约 \(39\%\)，但由于原地、缓存友好等优势，实际更快
快速排序的实际表现
快速排序在实践中表现极好，常见的工程优化包括：
- 小数组（\(k \approx 10 \sim 20\)）切换到插入排序
- 三数取中选择枢轴
- 3-way 划分处理重复元素（Dijkstra 荷兰国旗问题）
3-way 划分将数组分为 \(< v\)、\(= v\)、\(> v\) 三部分：
1 | 3-WAY-PARTITION(A, lo, hi): |
Sedgewick-Bentley 定理：3-way 快速排序的比较次数是熵最优的
期望比较次数 \(\Theta(n \cdot H)\)，其中 \(H = -\sum \frac{k_i}{n} \log_2 \frac{k_i}{n}\) 是 Shannon 熵
所有元素不同时退化为 \(\Theta(n\log n)\)，所有元素相同时退化为 \(\Theta(n)\)
解决了重复元素退化的问题
比较排序的下界
比较排序模型
插入排序、归并排序、快速排序、堆排序都是比较排序：仅通过元素之间的比较确定相对顺序
目前最好的运行时间是 \(O(n \log n)\)
自然就可以提出问题：\(O(n \log n)\) 是否是比较排序能达到的最好性能？
决策树模型
决策树是一棵二叉树，用于模拟比较排序的执行过程
- 每个输入大小 \(n\) 对应一棵决策树
- 内部节点标记为 \(i:j\)（比较 \(a_i\) 和 \(a_j\)）
- 左子树对应 \(a_i \leq a_j\)，右子树对应 \(a_i > a_j\)
- 叶节点包含一个排列 \(\langle \pi(1), \pi(2), \ldots, \pi(n) \rangle\)
- 最坏情况运行时间 = 决策树的高度
对 \(\langle a_1, a_2, a_3 \rangle\) 排序的决策树：
1 | 1:2 |
下界定理
定理：任何能够对 \(n\) 个元素排序的决策树的高度为 \(\Omega(n \log n)\)
点击查看证明
证明：
首先决策树必须至少有 \(n!\) 个叶节点（\(n!\) 种可能排列）
则高度为 \(h\) 的二叉树最多有 \(2^h\) 个叶节点
因此 \(n! \leq 2^h\)
利用 Stirling 近似 \(n! \geq (n/e)^n\)：
\[ h \geq \lg(n!) \geq \lg\left(\frac{n}{e}\right)^n = n \lg n - n \lg e = \Omega(n \log n) \]
推论：归并排序是渐近最优的比较排序算法
信息论视角
排序问题可以看作通信问题：输入是 \(n!\) 种可能排列之一，输出是确定的排列
每次比较提供 1 bit 信息，要在 \(n!\) 种可能中唯一确定一种排列，至少需要 \(\log_2(n!)\) bits
这个下界只适用于比较排序模型
非比较排序（计数排序、基数排序、桶排序）利用输入的额外结构信息，不受此限制
第 \(i\) 小的元素
给定 \(n\) 个元素，选择第 \(i\) 小的元素（秩为 \(i\) 的元素）
特殊情况：\(i = 1\) 最小值，\(i = n\) 最大值，\(i = \lfloor (n+1)/2 \rfloor\) 中位数
朴素算法排序后取第 \(i\) 个：\(O(n \log n)\)，能否 \(O(n)\)？
随机选择算法
1 | RAND-SELECT(A, p, q, i) |
核心思想：利用随机划分，只递归处理包含目标元素的一侧
概率分析
定义”幸运划分”：两侧子数组大小都至少 \(\frac{n}{10}\)，随机选择枢轴时，产生幸运划分的概率至少为 \(\frac{8}{10}\)
设 \(t_i\) 为连续幸运划分间的划分次数，\(t_i\) 服从几何分布，\(E[t_i] =\frac{8}{10}\)
期望总时间：
\[ \frac{10}{8}n + \frac{10}{8} \cdot \frac{9}{10}n + \frac{10}{8} \cdot \left(\frac{9}{10}\right)^2 n + \cdots = \frac{10}{8}n \cdot \frac{1}{1-\frac{9}{10}} = O(n) \] \(E[T(n)] = O(n)\)
点击查看形式化分析
定义指示器随机变量 \(X_k\)：PARTITION 产生 \(k:(n-k-1)\) 划分时 \(X_k = 1\)
为获得上界，假设目标总在较大一侧：
\[ T(n) \leq \sum_{k=0}^{n-1} X_k \cdot T(\max(k, n-k-1)) + \Theta(n) \]
取期望，利用 \(E[X_k] = 1/n\)：
\[ E[T(n)] \leq \frac{2}{n} \sum_{k=\lfloor \frac{n}{2} \rfloor}^{n-1} E[T(k)] + \Theta(n) \]
假设 \(E[T(n)] \leq cn\)，由 \(\sum_{k=\lfloor \frac{n}{2} \rfloor}^{n-1} k \leq \frac{3n^2}{8}\)：
\[E[T(n)] \leq \frac{2c}{n} \cdot \frac{3n^2}{8} + \Theta(n) = \frac{3cn}{4} + \Theta(n) = cn - \left(\frac{cn}{4} - \Theta(n)\right) \leq cn\]
最坏情况线性时间选择
SELECT 算法（Blum, Floyd, Pratt, Rivest, Tarjan, 1973），核心思想：递归生成好的枢轴
1 | SELECT(i, n) |
至少 \(\lceil \frac{1}{2} \lceil \frac{n}{5} \rceil \rceil\) 个组中位数 \(\geq x\)，因此至少 \(3\lceil \frac{1}{2} \lceil \frac{n}{5} \rceil \rceil\) 个元素 \(\geq x\)
对 \(n \geq 50\)，至少 \(\frac{3n}{10}\) 个元素 \(\geq x\)（同理 \(\leq x\)），步骤 4 最多处理 \(\frac{7n}{10}\) 个元素
\[T(n) = T(\frac{n}{5}) + T(\frac{3n}{4}) + \Theta(n)\]
代入 \(T(n) \leq cn\)：
\[T(n) \leq \frac{cn}{5} + \frac{3cn}{4} + \Theta(n) = \frac{19cn}{20} + \Theta(n) \leq cn\]
\(T(n) = O(n)\)
为什么选 5？
- 分组大小 3：\(T(n) = T(\frac{n}{3}) + T(\frac{2n}{3}) + \Theta(n)\)，\(\frac{1}{3} + \frac{2}{3} = 1\)，不收敛，\(T(n) = \Theta(n\log n)\)
- 分组大小 5：\(\frac{1}{5} + \frac{3}{4} = \frac{19}{20} < 1\)，收敛
- 分组大小 7：\(T(n) = T(\frac{n}{7}) + T(\frac{5n}{7}) + \Theta(n)\)，\(\frac{6}{7} < 1\)，也可以工作
- 5 是使算法有效的最小分组大小
| 算法 | 期望时间 | 最坏时间 | 常数因子 |
|---|---|---|---|
| 随机选择 | \(O(n)\) | \(O(n^2)\) | 小 |
| 确定性 SELECT | \(O(n)\) | \(O(n)\) | 大 |
Introselect 算法（Musser, 1997）：C++ STL std::nth_element 的实现策略——先尝试随机选择，递归深度过深时切换到确定性 SELECT，结合两者优点
数据流模型与频繁元素
数据以流的形式到达，元素逐个到达，无法存储整个数据流，需要在有限内存下进行统计分析
频繁元素问题
给定数据流 \(s_1, s_2, \ldots, s_m\)，每个元素取值于 \(\{1, 2, \ldots, n\}\)
频繁元素：出现次数超过 \(\frac{m}{c}\) 次的元素
精确解需要 \(O(n)\) 空间，值域可能非常大时不可接受
Misra-Gries 算法 (1982)
确定性流式算法，两遍扫描找频繁元素，空间 \(O(c \log m)\) 位
维护最多 \(c\) 个计数器，每个关联一个元素及其估计频次
处理每个元素 \(e\)： 1. 如果 \(e\) 已有计数器，加 1 2. 如果 \(e\) 没有计数器但计数器不到 \(c\) 个，新建并设为 1 3. 如果所有 \(c\) 个计数器都被占用，所有计数器减 1，删除值为 0 的
算法示例
数据流：32, 12, 14, 32, 6, 12, 4, 7, 12, 32, 7，\(c = 3\)
1 | 处理 32: {32: 1} |
精度保证
设 \(f_e\) 为真实频次，\(\hat{f}_e\) 为估计频次：
\[f_e - \frac{m}{c} \leq \hat{f}_e \leq f_e\]
点击查看证明
上界 \(\hat{f}_e \leq f_e\)：计数器只在元素出现时递增，减少操作只会让估计值更小
下界 \(\hat{f}_e \geq f_e - m/c\)：每次减少操作同时将 \(c\) 个计数器各减 1（加上触发的新元素，消耗 \(c+1\) 个元素的出现）
设总共执行 \(d\) 次减少操作，数据流共 \(m\) 个元素：
\[ d \leq \frac{m}{c+1} < \frac{m}{c} \]
元素 \(e\) 的计数器最多被减少 \(d\) 次：\(\hat{f}_e \geq f_e - d \geq f_e - \frac{m}{c}\)
Misra-Gries 给出的是候选频繁元素列表，需要第二遍扫描验证
空间下界
Misra-Gries 的空间 \(O(c \log m)\) 已接近最优，可以证明任何确定性流式算法都需要 \(\Omega(c)\) 个字的空间
附录：
数据流算法相关
Misra-Gries 是数据流算法的开山之作，后续发展了一系列重要的流式算法：
| 算法 | 年份 | 解决问题 | 空间 |
|---|---|---|---|
| Misra-Gries | 1982 | 频繁元素 | \(O(c)\) |
| Flajolet-Martin | 1985 | 不同元素计数 | \(O(\log n)\) |
| AMS Sketch | 1999 | 频率矩估计 | \(O(1/\varepsilon^2)\) |
| Count-Min Sketch | 2003 | 频率估计 | \(O(1/\varepsilon \cdot \log(1/\delta))\) |
| HyperLogLog | 2007 | 不同元素计数 | \(O(\log\log n)\) |
这些算法在搜索引擎、网络监控、社交媒体等领域有广泛应用
相关数学工具
Stirling 近似：\(n! \approx \sqrt{2\pi n} (\frac{n}{e})^n\)，因此 \(\lg(n!) = \Theta(n \log n)\)
调和级数：\(H_n = \sum_{k=1}^{n} \frac{1}{k} = \ln n + \gamma + O(\frac{1}{n})\)，\(\gamma \approx 0.5772\)
几何级数：\(\sum_{k=0}^{\infty} r^k = \frac{1}{1-r}\)（\(|r| < 1\)）
Markov 不等式：对非负随机变量 \(X\) 和 \(t > 0\)，\(\Pr\{X \geq t\} \leq \frac{E[x]}{t}\)