企业官网建设流程全解析

• 文档
• 教程
• 教育

本文围绕《算法导论》（Introduction to Algorithms，第三版，简称 CLRS）第 7 章 Problems 7-2「Quicksort with equal element values」展开，解答经典问题：当数组中存在大量相等元素时，标准随机快速排序为何退化、如何设计返回两个分界下标的三向划分过程PARTITION′，以及如何把 7.4.2 节的期望时间分析推广到"元素互异"假设之外。读完本文，你将掌握可复现的三向快排伪代码、其循环不变量与正确性论证，并理解相等元素对快速排序期望复杂度影响的完整分析链条。对应题解正文见仓库 docs/Chap07/Problems/7-2.md，其在 mkdocs.yml 的站点导航中登记为第 7 章问题 7-2。

一、背景：7.4.2 节分析中的"元素互异"假设

CLRS 第 7 章 7.4.2 节对随机快速排序RANDOMIZED-QUICKSORT的期望运行时间分析（期望比较次数 $\Theta(n\lg n)$）建立在一个关键假设上：输入数组中所有元素值互不相同。该假设保证了每次PARTITION选出的主元（pivot）在数组中唯一，划分出的两个子数组大小之和恒为 $n-1$，从而可以用指示随机变量与期望线性叠加（如 docs/Chap07/7.4.md 中 7.4-4 的推导）得到期望 $O(n\lg n)$ 的上界。

当元素值出现重复时，这个分析框架面临两个直接问题：

1. 主元不再唯一：PARTITION返回的下标 $q$ 无法把"等于主元"的元素与"小于主元"的元素完全分开，子问题的定义出现歧义。
2. 划分可能退化：如仓库 docs/Chap07/7.1.md 中习题 7.1-2 的解答所示，当子数组 $A[p..r]$ 所有元素都相等时，标准PARTITION返回 $q = r$；而 7.2-2 的解答进一步指出，此时快速排序的运行时间退化为 $\Theta(n^2)$。

Problem 7-2 的任务，就是先确认这种退化有多严重（问题 a），再修改PARTITION得到三向划分PARTITION′（问题 b），进而构造只在"未知区间"上递归的QUICKSORT′（问题 c），最后调整 7.4.2 节的分析（问题 d）。这是 CLRS 中最经典的三向划分（three-way partitioning）设计练习之一，思想上与 Dijkstra 提出的"荷兰国旗问题"一脉相承。

二、问题 a：所有元素相等时的运行时间

结论：当所有元素值相等时，RANDOMIZED-QUICKSORT的运行时间为 $\Theta(n^2)$。

依据如下：由于每个元素都等于主元，PARTITION每次都会返回 $q = r$（见 7.1-2），也就是说划分永远产生"左侧子数组 $A[p..r-1]$ + 右侧空子数组"的极不平衡结构。于是得到递推式：

$$ T(n) = T(n - 1) + \Theta(n) = \Theta(n^2), $$

其中 $\Theta(n)$ 是单次PARTITION的开销（见 7.1-3 的论证：循环体执行 $r-1-p=\Theta(n)$ 次）。这个递推式的解法 $\Theta(n^2)$ 正是仓库 docs/Chap07/7.2.md 中习题 7.2-1 用代入法（substitution method）严格证明过的结论：猜测 $T(n) \le c_3n^2$ 并验证上界，再用对称论证得到下界，最终得到 $T(n)=\Theta(n^2)$。

直觉上这与最坏情况下"输入按递减序排列"（7.2-3）的情形完全一致：每一次划分都只剩一个规模为 $n-1$ 的子问题，递归深度达到 $n$，总代价呈平方级增长。注意这与输入是随机排列还是固定排列无关——问题的根源在于"重复元素 + 单主元划分"这一组合本身。

三、问题 b：设计PARTITION′——双下标三向划分

3.1 要求与设计目标

PARTITION′需要在 $\Theta(r-p)$ 时间内原地置换 $A[p..r]$，并返回两个下标 $q$ 和 $t$（$p \le q \le t \le r$），使得划分后满足三个条件：

• $A[q..t]$ 中所有元素都等于主元；
• $A[p..q-1]$ 中每个元素都小于 $A[q]$；
• $A[t+1..r]$ 中每个元素都大于 $A[q]$。

与书中标准PARTITION（以 $A[r]$ 为主元、返回单个下标）不同，PARTITION′以 $A[p]$ 为主元，并通过low、high两个指针维护一个"等于主元"的连续区间，最终返回该区间的左右端点。仓库中的参考实现如下：

PARTITION'(A, p, r) x = A[p] // 以子数组首元素为主元 low = p // 等于区间的左端点 high = p // 等于区间的右端点 for j = p + 1 to r if A[j] < x // 将小于主元的元素移到区间最前，等于区间整体右移一位 y = A[j] A[j] = A[high + 1] A[high + 1] = A[low] A[low] = y low = low + 1 high = high + 1 else if A[j] == x // 将新发现的相等元素并入等于区间 exchange A[high + 1] with A[j] high = high + 1 return (low, high)

3.2 循环不变量与逐行解读

该过程维护的循环不变量（在每轮迭代开始前成立）可表述为：

• $A[p..low-1]$：所有元素严格小于 $x$；
• $A[low..high]$：所有元素严格等于 $x$；
• $A[high+1..j-1]$：已扫描但尚未归入前两区的元素（经交换后实际为大于 $x$ 的元素）；
• $A[j..r]$：尚未扫描的元素。

三种分支的作用：

• A[j] < x：做一次三轮交换。先把 $A[j]$ 暂存到y，把"等于区间"右邻的元素 $A[high+1]$ 换到 $A[j]$ 位置，把等于区间的第一个元素 $A[low]$ 换到 $A[high+1]$，最后把较小元素y放到 $A[low]$。随后low、high同时右移一位——等于区间整体右移，新区间 $[low..high]$ 仍全部等于 $x$，且新的 $A[low]$ 左侧全是小于 $x$ 的元素。
• A[j] == x：把 $A[high+1]$ 与 $A[j]$ 交换，然后high++，等于区间向右扩一格。
• A[j] > x：不做任何操作，元素留在原处，随着 $j$ 前进自然进入"大于"区域。

可见该算法的本质是单趟线性扫描（每个元素恰好处理常数次），因此运行时间为 $\Theta(r-p)$，满足题目要求。

3.3 一个完整的手算示例

以 $A = \langle 5, 3, 5, 1, 5, 4 \rangle$（$p=1, r=6$）为例，$x = 5$，初始low = high = 1：

最终返回 $(q, t) = (4, 6)$：$A[1..3] = \langle 3,1,4 \rangle$ 全部小于 5，$A[4..6] = \langle 5,5,5 \rangle$ 全部等于 5，右侧"大于区"为空。可以看到，即使全部元素相等，PARTITION′也只需一趟 $\Theta(n)$ 的扫描就把整个子数组并入"等于区"，这正是后续QUICKSORT′能够避免平方级退化、甚至在全部相等时达到 $\Theta(n)$ 的原因。

3.4 正确性论证要点

• 终止性：for循环从 $p+1$ 到 $r$ 固定执行 $r-p$ 次，必然终止并返回。
• 分区性质：循环结束时 $j = r+1$，不变量给出 $A[p..low-1] < x$、$A[low..high] = x$、$A[high+1..r] > x$，恰好对应题目的三条要求（$q = low$，$t = high$）。
• 时间界：每次迭代至多执行常数次赋值/交换，循环外为常数开销，故总时间 $\Theta(r-p)$。

四、问题 c：构造QUICKSORT′与RANDOMIZED-QUICKSORT′

有了双下标划分，递归结构就非常自然：中间"等于主元"的块已经就位、无需再参与排序，只需对左右两侧"未确定为相等"的子数组递归。仓库给出的参考实现：

QUICKSORT'(A, p, r) if p < r (low, high) = RANDOMIZED-PARTITION'(A, p, r) QUICKSORT'(A, p, low - 1) QUICKSORT'(A, high + 1, r)

其中RANDOMIZED-PARTITION′是按 7.3 节随机化标准做法对PARTITION′的封装：先用RANDOM(p, r)随机选一个下标 $i$，将 $A[p]$ 与 $A[i]$ 交换，再调用PARTITION′(A, p, r)返回双下标。其流程可还原为：

RANDOMIZED-PARTITION'(A, p, r) i = RANDOM(p, r) exchange A[p] with A[i] return PARTITION'(A, p, r)

关键区别在于递归区间：标准QUICKSORT递归的是 $[p, q-1]$ 与 $[q+1, r]$（只排除了单个主元），而QUICKSORT′递归的是 $[p, low-1]$ 与 $[high+1, r]$——整块与主元相等的元素全部被排除在递归之外。这就是题目所述"只在不已知彼此相等的分区上递归"。

由此可以得到一个重要的极端情形：当所有元素都相等时，第一次RANDOMIZED-PARTITION′返回 $(low, high) = (p, r)$，两个递归调用的区间分别为 $[p, p-1]$ 与 $[r+1, r]$，均为空，递归立即终止。总时间为单趟划分的 $\Theta(n)$——把问题 a 中 $\Theta(n^2)$ 的最坏情形彻底消除了。

五、问题 d：如何调整 7.4.2 节的分析

7.4.2 节用指示随机变量 $X_{ij}$（$A[i]$ 与 $A[j]$ 是否被比较）推导期望比较次数时，依赖"元素互异"来保证每个元素对至多比较一次。QUICKSORT′的分析调整策略（按仓库题解）可以这样理解：

因为不再对等于主元的元素递归，QUICKSORT′产生的每个子问题规模，都不大于元素互异时QUICKSORT对应子问题的规模。

具体而言，设原始数组中与主元相等的元素个数为 $m \ge 1$。互异情形下每次划分两侧子问题大小之和为 $n-1$；而在QUICKSORT′中，中间等于块（大小 $m$）被整体剔除，两侧子问题大小之和为 $n-m \le n-1$。因此：

1. 期望时间上界保持：7.4.2 节关于期望比较次数 $\sum_{i<j}\frac{2}{j-i+1} = \Theta(n\lg n)$ 的推导，对"子问题规模不超过互异情形"的递归过程依然成立——互异情形的规模序列本身就是所有情形中最坏的上界。换句话说，QUICKSORT′的期望运行时间仍为 $\Theta(n\lg n)$，且渐进常数与互异情形一致。
2. 重复越多、性能越好：$m$ 越大，被剔除的中间块越大，递归层数与总工作量越少。两个极端为：全部互异（$m=1$）时退化为标准随机快排的 $\Theta(n\lg n)$；全部相等（$m=n$）时一步到位，$\Theta(n)$。
3. 主定理视角：一般情形下（每种值出现多次），递归深度被"互异值个数"而非"元素个数"控制。若数组只含 $k$ 种不同取值，期望复杂度至多为 $O(k\lg k)$ 量级（配合每层划分的线性扫描），这比把重复元素当独立元素排序要高效得多。

需要注意，该调整并不改变 7.4.2 节"期望而非最坏"的分析对象：RANDOMIZED-PARTITION′的随机性依然保证了对任意输入（包括含重复的输入）期望 $\Theta(n\lg n)$，而最坏情形（例如输入互异且逆序排列）仍为 $\Theta(n^2)$，与标准随机快排一致。

六、延伸：同一技巧在仓库其他问题中的印证

"三区划分"思想在 CLRS 第 7 章及全书中反复出现，仓库中可直接对照的还有：

• Problem 7-6：区间模糊排序（fuzzy sorting）：该问题处理"只知道数值所属区间 $[a_i,b_i]$"的排序，其FUZZY-SORT同样先把输入划分为"left / middle / right"三个子数组，只对 left 与 right 递归，middle 中相互重叠的区间无需排序。这与QUICKSORT′把"等于主元"的中间块整块跳过是同一设计范式。7-6 的期望时间分析也呈现同样的渐进规律：区间完全不重叠时为 $\Theta(n\lg n)$，全部重叠时退化为 $\Theta(n)$。
• 习题 7.1-2 与 7.2-2（[7.2-2 见 docs/Chap07/7.2.md）：前者指出全相等时标准PARTITION返回 $q=r$，后者据此得出全相等时QUICKSORT为 $\Theta(n^2)$——这两条正是问题 a 结论的直接依据。
• Problem 12-1：二叉搜索树中的相等键：相等键同样困扰 BST。该问题给出布尔标志交替下降、节点处维护相等键链表、随机选择左右子树等策略，分别将插入 $n$ 个相同键的代价从 $\Theta(n^2)$ 优化到 $\Theta(n\lg n)$ 乃至 $\Theta(n)$。与QUICKSORT′的思路一致："相等键/相等值"应当被显式聚合处理，而不是当作普通元素参与比较与递归。

这些关联说明了同一个工程结论：任何基于比较的排序/检索结构，在遇到大规模重复键时都应显式利用"相等"关系，否则会系统性退化。

七、小结

• 问题 a：全相等时RANDOMIZED-QUICKSORT满足 $T(n)=T(n-1)+\Theta(n)$，运行时间 $\Theta(n^2)$，退化根源是划分永远产生空子问题。
• 问题 b：PARTITION′以 $A[p]$ 为主元，用low/high维护"等于区"，一趟 $\Theta(r-p)$ 扫描内把子数组划为"小于 / 等于 / 大于"三区，返回等于区两端的 $(q,t)$。
• 问题 c：QUICKSORT′对等于区不递归，只递归左右两侧；全相等时单趟结束，总时间 $\Theta(n)$。
• 问题 d：将 7.4.2 节分析推广到含重复元素时，只需断言"子问题规模不超过互异情形"，期望 $\Theta(n\lg n)$ 的结论即可无改动地保留，且重复元素越多实际开销越低。

这一题组完整展示了"分析退化 → 改进划分 → 重构递归 → 修正分析"的算法设计闭环，是理解三向快排（如 C/C++ 标准库实现中针对重复键的优化思路）与大规模重复数据排序的基石。完整题解与其余相关章节均可在仓库 docs/Chap07 目录下查阅。

• 文档
• 教程
• 教育