COURSE NOTES / DAY 04
算法设计与分析 Day4:随机快速排序、排序下界与三道作业详解
RedMoon · 算法设计与分析 · Day4
快速排序的一次划分会把枢轴放到最终位置。剩下的工作量,取决于枢轴两侧各有多少元素。本次课从划分规模出发,推导随机快速排序的期望时间,再结合堆排序、计数排序和决策树,讨论排序算法利用的信息及其复杂度下界。
文末详解三道作业:线性时间最大子数组、用最小堆合并有序表,以及快速排序与插入排序的组合。每题包含题意、算法、执行示例、正确性证明和复杂度分析。
记 , 为自然对数;区间 包含两端。Python 代码使用 0-based 下标,返回的最大子数组区间也包含左右端点。时间分析默认一次比较、数组访问及机器字范围内的算术运算花费常数时间;涉及输入编码长度时,会单独说明。
一、课堂热身:多数元素为什么可以两两抵消
1. 多数元素与众数的区别
课件第 2 页的题目是 LeetCode 169「多数元素」:给定一个非空数组,保证存在出现次数 严格大于 的元素,找出它。
众数只要求出现次数最多,多数元素则要求占据一半以上。例如 中,1 和 2 都是众数,但没有多数元素。严格多数至多只有一个,因为两个数的出现次数不可能都超过 。
直接统计频次即可求解。用哈希表记录,期望时间为 ,最坏空间为 ;若已知整数值域为 ,也可以使用长度为 的计数数组,时间为 ,空间为 。值域越大,初始化计数数组的成本越高。
2. Boyer–Moore 投票法
从数组中删去两个值不同的元素,原来的多数元素仍然是剩余数组中的多数元素。
设多数元素为 ,原来出现 次。若删去的一对中包含 ,它还剩 次,且 ;若这一对都不是 ,它的次数不变,占比反而更高。因此,不断抵消后留下的候选值就是 。
实现时维护一个候选值 candidate 和未被抵消的数量 count:
def majority_element(a):
if not a:
raise ValueError("input must be nonempty")
candidate, count = None, 0
for x in a:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
return candidate以 为例:
| 下标 | 读入值 | 处理后的候选值 | count |
发生的操作 |
|---|---|---|---|---|
| 0 | 2 | 2 | 1 | 空状态建立候选值 |
| 1 | 2 | 2 | 2 | 同值累积 |
| 2 | 1 | 2 | 1 | 抵消一对不同值 |
| 3 | 1 | 2 | 0 | 当前候选全部抵消 |
| 4 | 1 | 1 | 1 | 重新建立候选值 |
| 5 | 2 | 1 | 0 | 再次抵消 |
| 6 | 2 | 2 | 1 | 剩下候选值 2 |
count 记录尚未被抵消的候选数量,不代表候选值在整个数组中的出现次数。算法只扫描一次,时间 ,辅助空间 。
若题目不保证多数元素存在,还需在第二遍扫描中统计候选值,检查它是否出现超过 次。例如 第一遍也会产生候选值,但数组中没有多数元素。
二、分治排序:归并排序与快速排序的分工
排序的输出既要按非降序排列,也要与输入包含完全相同的元素及重复次数。正确性证明需要同时覆盖有序性与元素保留,避免遗漏或增加元素。
课堂先区分了问题、算法和分析。排序规定要解决什么问题,归并排序与快速排序给出具体做法,正确性和运行时间分析则回答这些做法是否正确、需要多少代价。同一个问题可以有多种算法,分析时也可以采用不同模型。
| 分治环节 | 归并排序 | 快速排序 |
|---|---|---|
| 边界 | 长度不超过 1 时返回 | 长度不超过 1 时返回 |
| 分 | 按下标切成两半,切分本身简单 | 扫描元素,按枢轴值划分 |
| 治 | 排序左右两半 | 排序枢轴两侧 |
| 合 | 线性合并两个有序区间 | 枢轴已经就位,无须再线性合并 |
| 子问题规模 | 两侧约为 | 可能从 到接近均分 |
归并排序的主要线性工作在合并阶段,快速排序则在划分阶段。分析快速排序时,需要继续考察划分后两个子问题的规模。
三、随机快速排序:划分与实现
1. 枢轴必须退出后续递归
先从数组中均匀随机选取一个位置,以该位置的元素为枢轴 。单独取出这次出现,再将其余元素分成:
递归结果为:
这里的加号表示顺序拼接。枢轴本身不再进入 或 ,所以两侧规模之和是 ,每个递归子问题都严格变小。
数组含重复值时,也必须排除选作枢轴的这次出现。否则,把枢轴放回「小于等于」的一侧后,全相等数组可能原样进入下一次递归,无法结束。原地划分会固定一个枢轴位置,使后续区间严格缩小。
2. 原地划分的四个区域
课件第 8 页使用 Lomuto 划分。先把随机选中的枢轴换到 ,令 ,再扫描 。
循环每次开始时维护:
| 区域 | 语义 |
|---|---|
| 已处理且全部 | |
| 已处理且全部 | |
| 尚未检查 | |
| 暂存枢轴 |
若 ,先令 加 1,再交换 与 ,把这个元素纳入左区间;若 ,则直接推进扫描位置。
扫描结束后,交换 与 。令 ,得到:
from random import Random
def randomized_partition(a, p, r, rng):
pivot_index = rng.randrange(p, r + 1)
a[pivot_index], a[r] = a[r], a[pivot_index]
x = a[r]
i = p - 1
for j in range(p, r):
if a[j] <= x:
i += 1
a[i], a[j] = a[j], a[i]
a[i + 1], a[r] = a[r], a[i + 1]
return i + 1
def quicksort(a, rng=None):
if rng is None:
rng = Random()
def sort(p, r):
if p >= r:
return
q = randomized_partition(a, p, r, rng)
sort(p, q - 1)
sort(q + 1, r)
sort(0, len(a) - 1)
return a3. 课件示例的交换过程
输入 ,取末尾的 20 为枢轴。使用 0-based 下标,初始 :
| 扫描阶段 | 比较结果与动作 | 数组 |
|---|---|---|
| ,不交换 | ||
| ,不交换 | ||
| ,令 ,交换位置 0 和 2 | ||
| 扫描结束 | 交换位置 和末尾枢轴 |
返回 。20 已经就位,但右侧 还没有排序。一次划分只保证枢轴两侧满足大小关系。
4. 正确性与空间
用循环不变式证明划分正确。初始化时,两个已处理区域均为空;扫描中,每次交换将符合条件的元素放进左区间,并保持右区间的性质;扫描结束时,未知区域为空,最后一次交换将枢轴放到两区之间。
再对区间长度归纳,即可证明快速排序正确。长度不超过 1 时,区间已有序。更长的区间经过划分后,枢轴两侧满足大小关系;由归纳假设,两个更短区间递归排序后也各自有序,拼接起来便得到整个有序区间。全过程只交换已有元素,因此输入的多重集合保持不变。
长度为 的划分需要 次关键字比较,时间 ,辅助空间 。上面的快速排序仍有递归栈:互异元素、随机枢轴时,期望栈深为 ,最坏可达 。若每次只递归较短一侧、用循环处理较长一侧,可以把栈空间最坏限制在 。
5. 重复值与稳定性
Lomuto 使用 <= 判断。所有元素相等时,每次划分都把其余 个元素留在左侧,无论随机选中哪个位置,时间都是 。随机化改变了枢轴的选择方式,但这个划分规则仍会把所有相等元素放到同一侧。
课件之外,还可以用三路划分处理重复值:将元素分成 、、 三区,只递归两侧;所有值相等时,一次线性扫描即可结束。后续期望递推假设 元素互异,此时每个枢轴秩恰好对应一种左右规模。
这种交换式快速排序通常不稳定。例如给相同键附上标签, 以 1 划分后成为 ,两个键为 2 的记录已交换先后。
四、输入、随机选择与运行时间
1. 运行时间有两个自变量
记 为输入数组 、随机选择序列 下的运行时间。即使固定 ,不同的枢轴序列也会产生不同的递归树。
「随机快速排序的期望时间」通常对算法的随机选择取期望:
若元素互异,这个期望为 。分析时先固定任意输入,再对枢轴的随机选择取平均,无须假设输入本身是随机排列。
平均情况 则对输入取平均,需要先给定输入分布。它可能与随机算法的期望时间具有相同的渐近阶,但两者取平均的对象不同。
2. 不带有序性预检查的普通版本
若每次都接近均分:
若每次都选到当前最小值或最大值:
后一种情况下,扫描规模累加为 。随机快速排序也可能连续选到这样的枢轴,因此最坏时间仍为二次量级,未降至 。
3. 加入有序性检查后的版本
课件第 11 页另加了一步:先扫描数组,发现已经有序就返回。对这个变体,已排序输入的运行时间是 ,因为只需完成一次检查。
带预检查版本在有序输入上花费的时间,与普通快速排序在均衡划分下的 对应不同条件。几种情况如下:
| 所讨论的情况 | 时间 |
|---|---|
| 普通版本,划分始终接近均衡 | |
| 普通版本,划分始终极端不均衡 | |
| 带预检查版本,输入原本有序 | |
| 互异元素的随机版本,对随机枢轴取期望 |
预检查本身需要线性时间。下一节沿用课件的规范化递推,分析不提前返回的普通随机版本。
五、随机快速排序的期望时间推导
1. 按枢轴秩分类
设 为规模 的期望代价。元素互异、从当前子数组均匀选择枢轴时,枢轴可能有 个更小的元素,每种情况概率都是 。
当左侧规模为 时,右侧规模为 。将一次线性处理的代价规范化写成 ,得到:
两部分求和包含相同的项,只是次序相反,因此:
若保留具体实现中的常数项和线性项系数,推导方式与渐近阶不变。边界代价 均为常数;相邻规模作差时,要从两个递推式都成立的规模开始,再把有限个初值并入常数。
2. 乘以规模,再对相邻式子作差
两边乘以 :
把规模换为 :
两式相减,求和只留下最后一项:
于是:
求和项由此消去,递推只剩相邻两个规模。
3. 除以 ,得到可累加的形式
令 ,就有 。展开至一个固定初值 :
因此:
若选择使递推在 也成立的规范化初值,便可直接写成课件中的 。若程序在长度为 1 时立即返回,从 开始展开即可,渐近结论一致。
调和级数产生对数,因为:
均衡递归树因为每次规模约减半而产生对数层数。这里则先对所有枢轴秩取平均,再由调和级数得到对数因子,因此允许部分划分很不均衡。
4. 为什么随机版本仍可能很慢
互异元素下,每次恰好选到当前最小值这一种具体序列的概率为:
这个概率对应一条指定的极端路径。分析算法整体变慢的概率,还要考虑其他坏路径。上面的递推证明了期望为 ;若要得到指数衰减的尾界等更强的高概率结论,还需额外论证,不能由期望上界直接推出。
5. 补充推导:精确比较次数
如果只统计划分时的关键字比较,令 为期望比较次数,,则:
设排好序后各元素为 。一对 只有在区间 中最先成为枢轴的是某个端点时才会相互比较,因此:
利用期望的线性性求和:
最坏比较次数为 。下图由这两个公式绘制,比较的是理论计数:
期望比较次数约为 ,最坏比较次数按二次增长。这里的 只统计关键字比较;前面将每层全部线性工作简写为 的 ,采用的是另一种计量单位。
六、Quickselect:只递归包含目标秩的一侧
若目标是第 小元素,每次划分后只需判断枢轴的最终位置:
- 枢轴位置恰好为目标位置,直接返回。
- 目标在左侧,只继续处理左侧。
- 目标在右侧,只继续处理右侧。
def quickselect(a, rank, rng=None):
if not 0 <= rank < len(a):
raise ValueError("rank must be a valid zero-based index")
if rng is None:
rng = Random()
p, r = 0, len(a) - 1
while p <= r:
q = randomized_partition(a, p, r, rng)
if q == rank:
return a[q]
if rank < q:
r = q - 1
else:
p = q + 1这里的 rank 是 0-based 排名,例如奇数长度数组的中位数对应 rank = len(a) // 2。算法会改动输入数组。
若每次保留的规模约减半,总扫描代价为 。随机枢轴下的期望线性时间,可以用归纳法证明。设 为所有目标秩中最大的期望代价。固定任意目标秩,枢轴左边有 个元素时,记下一步实际处理的规模为 ;若恰好找到目标,则记为 0。于是:
对于 ,
用归纳假设 控制所有更小规模,对任何目标秩都有:
同一个常数 对所有目标秩都成立,故 ,有限初值并入常数。因此,互异元素、均匀随机枢轴下的期望时间为 ,最坏仍为 。
课件第 19 页将找中位数的期望时间写成 ,应改为 。初始划分就要扫描线性数量的元素,分析总时间还需累加后续各层的扫描工作。要保证确定性的最坏线性时间,则需采用其他枢轴策略,例如 median-of-medians。
七、堆排序与自底向上建堆
1. 建堆、查看堆顶与取出堆顶
每次扫描剩余数组找最小值,连续取出 次的总代价为 。最小堆要求父节点不大于子节点,因此全局最小值始终在堆顶。
| 操作 | 代价 | 做了什么 |
|---|---|---|
| 自底向上建堆 | 从整个输入建立堆序 | |
| 查看最小值 | 读取堆顶,不删除 | |
| 取出最小值 | 删除堆顶,并恢复堆序 |
课堂将最小堆视作黑盒:先建堆,再反复弹出最小值。
import heapq
def heap_sort(a):
heap = list(a)
heapq.heapify(heap)
result = []
while heap:
result.append(heapq.heappop(heap))
return result建堆花费 ,随后 次删除各需至多 ,总时间为 。上面的实现复制了输入,并单独保存输出,额外空间为 。教材中常见的 原地堆排序 使用最大堆,将最大值交换到数组末尾,辅助空间可降至 。空间结论取决于采用哪种实现。
2. 补充推导:建堆的 上界为何可以收紧
逐个插入 个数,时间上界为 。heapify 采用自底向上调整:大多数节点靠近叶子,调整距离很短,只有少数上层节点可能下降很多层。
高度为 的节点数量至多为 ,每个节点的调整代价为 。因此:
课堂主要使用建堆、取堆顶的接口及其复杂度。上面的求和补充了线性建堆的原因,后面的多路归并也会用到这一结论。
八、计数排序与值域大小
1. 算法与例子
假设输入都是正整数,值域为 。建立计数数组 ,让 记录 出现的次数,再按 的顺序输出。
对课堂例子 :
| 值 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 次数 | 1 | 2 | 1 | 0 | 1 |
输出为 。
def counting_sort(a):
if not a:
return []
upper = max(a)
counts = [0] * (upper + 1)
for x in a:
counts[x] += 1
result = []
for x in range(1, upper + 1):
result.extend([x] * counts[x])
return result这段代码要求输入为正整数;若要支持 0 或负整数,需要调整扫描范围或增加偏移。找最大值、统计频次及输出共需 ,初始化和遍历值域需 ,所以:
若把返回的输出数组也计入额外存储,总空间为 。
这个简化版本只输出整数键值。若每条记录还带有其他字段,稳定排序就要保留完整记录及相同键的原有先后顺序,应采用累计计数与稳定放置等标准写法。重复输出相同整数,并不能完成这种记录排序。
2. 数值大小与二进制编码长度
复杂度式中的 表示数值大小,而计算复杂性中的「多项式时间」以输入编码长度 为参照。
正整数 的二进制长度是 。变长编码下,总输入长度还要加上分隔或长度信息;通常可以把主要部分写为:
若统一用足够容纳 的定长字段,单个字段需要 位,总长度约为 。
数值可以相对编码长度呈指数增长。例如数组只含一个数 ,存储它需要 位;若算法初始化从 1 到 的计数表,单这一步就需要 的时间和空间。
因此, 虽然是数值参数的多项式,却未必是二进制输入长度的多项式。这类依赖数值大小的界称为 伪多项式时间。若输入额外满足 ,其中 为固定常数,则该算法在这一受限输入族上是多项式时间;当 时,时间进一步降为线性。
3. 桶排序、基数排序与 Sleep Sort 的条件
课堂还提到了桶排序和基数排序,作为课件延伸。桶排序的期望线性时间依赖适当的输入分布和桶内处理条件;输入不是正整数这一点,本身不足以保证桶排序线性完成。基数排序则需计入位数及每一位的排序成本。
Sleep Sort 按数值设置等待时间,再按唤醒顺序输出。分析它时,要把计时、调度、并发资源和值域大小纳入计算模型;只数代码中的显式比较会漏掉这些代价。系统调度也未必能让任意输入都可靠有序。这个例子说明,复杂度结论必须与计算模型一起理解。
九、比较排序下界:为什么至少需要 次比较
1. 用决策树表示算法
限制算法只能通过比较获得键之间的顺序信息。对 个互异元素,一次比较只会产生两个可能结果,可表示为二叉树的一个分支。
树根对应第一次比较;向左或向右表示比较结果;后续节点对应由此前结果决定的下一次比较。到达叶子时,算法已经能确定一个正确的输出下标顺序。
一条根到叶子的路径长度,就是该输入执行的比较次数;树高就是最坏输入所需的比较次数。
2. 为什么至少要有 个叶子
把输入位置标记为 。当键互异时,它们可能有 种严格全序。一个固定的输出下标顺序,例如 ,只能在与它匹配的全序下正确。
正确的比较排序必须覆盖所有这些可能性。两个需要不同输出顺序的全序不能最终共享同一个输出叶子,因此叶子数至少是 。
这里区分的是元素相对顺序。即使键可以取无限多种数值,只要全序相同,它们仍可以沿同一条比较路径到达同一叶子。
3. 由叶子数推出高度
高度为 的二叉树最多有 个叶子,因此:
再证明 。上界直接用 :
下界取阶乘中最大的至少 个因子,每个都不小于 :
由此得到:
课件第 30 页在阶乘附近标注了 。这里应使用粗上界 ,并在取对数后得到 ,不能把前一个标记当作阶乘的等价式。
例如 时有 6 种全序,二叉树至少要有 6 个叶子,最坏路径至少为 。一般的叶子计数只给出下界,不保证存在某个算法恰好达到这个整数值。
4. 下界的适用范围
该下界针对最坏情况。带有序性预检查的算法遇到已排序输入时,仍可在线性扫描后返回;某些输入较容易处理,与最坏情况下界一致。
计数排序通过键值直接寻址计数表,利用了比较模型以外的信息,因此其 时间与比较排序下界相容。特定分布、重复值结构及其他受限输入族,也可能允许更快的算法。
推广到随机算法的期望下界,还需对输入分布取平均。让 种全序等概率出现,任何固定的正确比较决策树,平均叶深都至少为 。再对随机选择取平均,平均比较次数仍为 ,因此至少有一个输入的期望比较次数达到这一量级。这里要区分两个量词顺序:固定随机选择后存在坏输入,并不等于存在一个输入对所有随机选择都坏。
一次二元比较至多提供一比特的分支信息,而排序需要区分 种顺序。决策树用叶子数与树高的关系,给出了这一信息量直觉的严格证明。
十、常见排序算法的复杂度对照
下表列出常见实现的复杂度,以及平均或期望结论所需的条件。
| 算法 | 最坏时间 | 平均或期望时间 | 辅助空间与条件 |
|---|---|---|---|
| 插入排序 | 随机排列下 | ;近乎有序时为 | |
| 归并排序 | 常见数组实现为 | ||
| 随机快速排序 | 互异元素下 | 原地划分;常见递归栈期望 | |
| 原地堆排序 | 上界 | ;使用最大堆原地放置 | |
| 计数排序 | 计数表 ;含输出为 |
其中 为当前数组的逆序对数:若 且 ,两者就构成一个逆序对。插入排序每次向右移动一个前驱元素,都会消除一个逆序对,第三道作业将据此计算移动次数。
十一、作业 1:非递归的线性时间最大子数组
1. 题意与状态分析
来源:课件第 32 页,CLRS 练习 4.1-5。
给定非空数组 ,元素可以为正、负或零。求一个 非空连续子数组,使元素和最大。要求从左向右扫描,采用非递归算法,在线性时间内完成。
题目提示:已知前缀 的答案,扩展到 后,最优解只有两种位置关系:
- 完全位于旧前缀中。
- 以新元素 结尾。
因此需要同时记录整个前缀的最佳值,以及恰好在当前位置结束的最佳值。前者保存已有答案,后者决定新元素接在哪一段后面;只保留全局最大值会缺少后一项信息。
2. 两个状态与递推
定义:
即以位置 结尾的最大非空子数组和。另设:
即整个前缀 中的最大非空子数组和。
以 结尾的最优区间,要么只选 ,要么把一个以 结尾的最优区间延长:
前缀最佳值则为:
初值为 。旧后缀贡献为负时,从当前元素重新开始更优。这一选择取决于以当前位置结束的状态,不能由此前的全局最佳值决定。
3. 返回最大和与左右端点的实现
def max_subarray(a):
if not a:
raise ValueError("nonempty subarray requires nonempty input")
end_sum = best_sum = a[0]
end_left = best_left = best_right = 0
for j in range(1, len(a)):
if end_sum + a[j] < a[j]:
end_sum = a[j]
end_left = j
else:
end_sum += a[j]
if end_sum > best_sum:
best_sum = end_sum
best_left, best_right = end_left, j
return best_sum, best_left, best_right返回值为 (最大和, 左端点, 右端点)。相等时保留已有答案,因此有多个最优区间时,会返回最先记录的那个,满足题目求一个最优区间的要求。
4. 手算完整过程
取:
| 当前结尾区间 | 已记录的最佳区间 | ||||
|---|---|---|---|---|---|
| 0 | -2 | -2 | -2 | ||
| 1 | 1 | 1 | 1 | ||
| 2 | -3 | -2 | 1 | ||
| 3 | 4 | 4 | 4 | ||
| 4 | -1 | 3 | 4 | ||
| 5 | 2 | 5 | 5 | ||
| 6 | 1 | 6 | 6 | ||
| 7 | -5 | 1 | 6 | ||
| 8 | 4 | 5 | 6 |
答案为 ,总和为 6,端点为 。处理到位置 7 时,结尾状态的和下降,但记录的全局最佳区间保持不变。
5. 正确性证明
循环处理完下标 后,保持两个不变式:
end_sum等于所有以 结尾的非空子数组中的最大和,end_left是对应起点。best_sum等于前缀 中所有非空子数组的最大和,记录的端点对应一个达到该和的区间。
初始 时只有一个非空区间 ,两个状态均取 ,成立。
假设处理完 时两个不变式成立。以 结尾的非空区间,要么从 开始,要么由以 结尾的区间延长。后一类都加上同一个新元素,选旧区间中和最大的那个即可,因此第一次更新得到 。前缀的最优区间则要么不经过 ,要么以 结尾,第二次更新据此得到 。两次选择都同步维护端点,所以不变式继续成立。
循环结束时 ,前缀就是整个数组,因此返回值正确。
6. 边界与复杂度
数组全为负数时,例如 ,答案是单个元素 ,返回 。若把最佳值初始化为 0,便会错误地返回一个不允许的空子数组。
长度为 1 时,直接返回唯一元素。空数组不满足输入要求,代码会抛出异常。若题目改为允许空子数组,可以将答案下限设为 0,但也要相应修改状态定义与证明,和本题的非空约定区分开。
每个元素只更新固定数量的变量,因此时间为 ,辅助空间为 。上一课的分治方法花费 ;这里用一个最佳结尾状态,保存下一次扩展所需的跨边界信息。
十二、作业 2:用最小堆合并 个有序表
1. 题意与关键观察
来源:课件第 33 页,CLRS 练习 6.5-9。
给定 个已经分别按非降序排列的表,总元素数为 。将它们合成一个有序表,要求时间 。提示是使用最小堆进行多路归并。
每张有序表中,第一个尚未输出的元素就是剩余部分的最小值。因此,只需比较各非空表的当前表头,就能找到下一个输出值。
堆中保存至多 个候选值。取出一个表头后,只需从它所属的表补入后继。
2. 堆节点保存什么
对于数组形式的输入表,堆节点设为:
第一个字段决定数值大小;后两个字段记录来源,便于找到后继。值相等时,Python 元组继续比较表号和下标,因此可以正常处理重复值,也不需要比较不可排序的自定义节点。
def merge_sorted_lists(lists):
heap = [
(row[0], list_id, 0)
for list_id, row in enumerate(lists)
if row
]
heapq.heapify(heap)
result = []
while heap:
value, list_id, index = heapq.heappop(heap)
result.append(value)
next_index = index + 1
if next_index < len(lists[list_id]):
next_value = lists[list_id][next_index]
heapq.heappush(heap, (next_value, list_id, next_index))
return result若输入是链表,则每个堆节点保存当前节点及表号,弹出后沿 next 指针加入后继,算法结构不变。
3. 一次合并的全过程
设:
初始候选为 。下表为便于阅读,按数值和表号列出候选集合;实际堆数组的排列可能不同:
| 第几次取出 | 输出值与来源 | 加入的后继 | 取出后尚在堆中的候选值 |
|---|---|---|---|
| 1 | 1,来自 | 4 | |
| 2 | 1,来自 | 3 | |
| 3 | 2,来自 | 6 | |
| 4 | 3,来自 | 8 | |
| 5 | 4,来自 | 7 | |
| 6 | 6,来自 | 无 | |
| 7 | 7,来自 | 无 | |
| 8 | 8,来自 | 无 | 空 |
最终结果是 。每个输入元素进入输出一次;表耗尽后不再向堆中放入候选。
4. 正确性证明
循环开始时保持:
- 对每个仍有元素未输出的表,堆中恰有它的第一个未输出元素。
- 已输出部分有序,并且不大于任何尚未输出的元素。
初始化把各非空表的第一个元素加入堆,输出为空,成立。
各表内部有序,所以未输出元素都不小于本表的当前表头。堆顶又是所有当前表头中的最小值,也就是全体未输出元素的最小值。将它接在输出末尾,仍保持有序;再加入同一张表的后继,便恢复了每张未耗尽的表恰有一个候选值的不变式。
每轮恰好输出一个元素,循环共进行 轮。堆空时,各表都已经耗尽,所以输出有序并且包含全部输入元素。
5. 时间、空间与特殊情况
若 个表都非空且 ,初始化用 时间,heapify 也是 ;共弹出 次,每次至多再插入一次,堆大小始终不超过 ,因此:
最后一步使用了 。堆的辅助空间为 ,若把返回的输出也计入存储,则为 。
如果允许大量空表,扫描这 个输入表头本身就需 。设其中非空表数为 ,更完整的表达是:
时返回空表;只有一个非空表时,复制输出仍需 ,即使 ,总时间也不为零。题目常用的 写法默认至少合并两张非空表。
逐个扫描所有当前表头,每输出一个元素需要 ,总计 ;最小堆把这一步的维护成本降到了 。
十三、作业 3:截断快速排序,再对全数组做插入排序
1. 题意中的执行顺序
来源:课件第 34 页,CLRS 练习 7.4-5。
修改快速排序:调用到一个 少于 个元素 的子数组时,直接返回,让这个小区间暂时无序。整个快速排序阶段结束后,再对 整个数组 执行一次插入排序。
要求证明期望时间为:
并讨论理论上、实践中如何选择 。
分析采用互异元素和均匀随机枢轴,设 。截止条件严格为 ,长度恰好为 的子数组仍要划分。
2. 完整算法
def hybrid_sort(a, k, rng=None):
if k < 2:
raise ValueError("cutoff k must be at least 2")
if rng is None:
rng = Random()
def partial_quicksort(p, r):
if r - p + 1 < k:
return
q = randomized_partition(a, p, r, rng)
partial_quicksort(p, q - 1)
partial_quicksort(q + 1, r)
partial_quicksort(0, len(a) - 1)
for j in range(1, len(a)):
key = a[j]
i = j - 1
while i >= 0 and a[i] > key:
a[i + 1] = a[i]
i -= 1
a[i + 1] = key
return a代码复用前面的 randomized_partition,可接受空数组及 的情况;后者会直接进入全数组插入排序。题目中含 的复杂度分析,采用的范围为 。
前面的划分只交换元素,最后的插入排序又会排好整个数组,因此算法正确。分析运行时间时,需要先说明第一阶段留下的数组有多接近有序。
3. 未排序小块之间的顺序
递归在小于 的区间上停止。这些终止区间内部可以无序,但它们之间的顺序已经由祖先枢轴确定。
任取两个不同的终止区间,考虑把它们首次分开的祖先划分。左侧全部元素小于该枢轴,右侧全部元素大于该枢轴,所以左区间中的每个元素都小于右区间中的每个元素。已经就位的枢轴也不会与其他区间形成逆序。
因此,剩余逆序对只可能出现在同一个未排序小块内部。
以 为例,一种合法的第一阶段结果是:
其中 4 和 7 是已经固定的枢轴,三个小块的长度分别为 3、2、2,均小于 4。小块内部尚未排序,块间已满足前块所有值小于后块所有值的关系。
4. 插入排序的代价用逆序对计量
标准插入排序插入 key 时,每向右移动一个比它大的前驱元素,就消除一个逆序对。每个原始逆序对恰好引起一次这种移动,加上每轮固定开销,运行时间为:
其中 是第一阶段结束后的逆序对数。
设未排序小块长度为 。这些块互不重叠,满足 、。长度为 的块至多有 个逆序对,所以:
因此,最后一次 全数组 插入排序需要 。全局逆序对数限制了整个扫描过程的移动次数,所以即使不逐块排序,也能得到这个上界。
前面的具体例子中, 有 2 个逆序对, 和 各有 1 个,总计 。完整数组的插入过程只需 4 次右移:
| 插入的键 | 被右移的元素 | 局部结果 |
|---|---|---|
| 1 | 3 | |
| 2 | 3 | |
| 5 | 6 | |
| 8 | 9 |
其余插入轮次只进行固定数量的检查。最终数组为 。
5. 截断快速排序的期望代价
若每次恰好均分,递归约有 层,每层处理 个元素,于是得到 。这是均衡划分下的直观分析。要覆盖随机快速排序中的不均衡划分,还需计算达到截止规模之前的期望工作量。
将长度为 的一次划分所需的 工作,平均分摊给区间内的每个元素。固定任意原始元素 ,跟踪它在尚需划分的子问题中经历的区间规模。
称某次枢轴为「好枢轴」,若它的 1-based 秩 满足:
这些秩至少占一半,所以每次条件概率至少为 。取到好枢轴后,若 本身就是枢轴,它退出递归;否则它进入的那一侧规模至多为 ,取整不会破坏这个上界。
从规模 缩小到小于 ,至多需要:
次这样的成功缩小。即使中间出现坏划分,每等到一次好枢轴,期望尝试次数也至多为 2:给定此前任意划分历史,下一次选中好枢轴的条件概率始终至少为 。如果元素提前成为枢轴,跟踪还会更早结束。
因此,一个元素参与划分的期望次数为:
再对 个元素求和,利用期望的线性性:
不同元素的递归路径可以相互依赖。上述求和只用到每步随机枢轴的条件概率,以及期望的线性性,无须假设路径独立或每层均衡。
6. 合并两阶段的界
加入插入排序以及递归调用的线性级开销:
最后一步利用 ,将 吸收到 中。特别地, 时虽然 ,第一阶段仍需一次线性划分。这部分由总界中的 项覆盖,单独计算第一阶段时仍要保留。
这个界是随机枢轴下的期望结论。若连续选到很差的枢轴,第一阶段仍可能花费二次时间。输入含大量重复值、继续采用二路 Lomuto 划分时,互异元素下的期望证明也不适用。
7. 理论上怎样选择
若目标是保持最优的渐近量级,取一个固定常数 即可:
取 ,总界也保持在 ,与固定常数的渐近阶相同;取 时,上界则为 。
若进一步比较两阶段的成本常数,可以使用模型:
把 暂当作连续变量,则:
这个模型给出的理想阈值为常数规模,具体取决于两阶段的成本系数。它不能确定一个适用于所有机器和程序的整数;渐近大 隐藏了这些系数,实际最优阈值仍需测量。
8. 实践中怎样选择
固定实现与硬件,在同一批数据上比较几个小阈值。测试应覆盖随机、近乎有序、逆序及重复值较多的输入,并通过重复运行观察稳定耗时,减少随机枢轴波动对判断的干扰。
短数组上,插入排序的循环紧凑,局部访问连续;快速排序则要承担枢轴选择、划分和递归管理的开销。阈值决定何时切换两种算法,合适的取值还受元素大小、比较函数成本和缓存行为影响,需要通过测量确定。
9. 证明中需要保留的条件
- 截止条件是「少于 」,长度等于 时仍划分。
- 插入排序执行于整个数组;它的代价由全局剩余逆序对数控制。
- 小块内部无序,但块间顺序已经确定,否则 无法成立。
- 期望划分代价需要概率论证;理想均分的递归树只能提供直观解释。
- 小区间划分使用 辅助空间,不等于整段递归算法也只用 空间。
十四、复习题
- 多数元素的
count为什么不是实际出现次数?去掉存在性保证后应补哪一步? - Lomuto 划分的四个区域是什么?为什么最后交换后还不能说左右两侧已经有序?
- 为什么互异元素下,枢轴秩的均匀分布足以分析任意固定输入?
- 快速排序的期望递推为什么能通过相邻规模作差消掉求和?
- 递归层数为对数,为什么 Quickselect 的时间仍为线性?
- 自底向上建堆为什么是线性时间?查看堆顶与取出堆顶的成本有何区别?
- 为什么未必是关于二进制编码长度的多项式?
- 比较排序的叶子为什么至少有 个?下界为什么允许某些输入在线性时间内完成?
- 最大子数组的两个状态各自覆盖哪些候选区间?
- 多路归并为什么只需为每张表保留一个候选元素?
- 混合排序第一阶段之后,为什么逆序对只能留在小块内部?
- 怎样在允许随机坏划分的情况下,证明第一阶段的期望代价?
附 · 资料下载
主要依据为课程课件《04-advanced_sorting》、本次课堂转写《算法课排序复杂度与决策树证明》,以及当天课堂摘要。三道作业的编号、输入要求和目标复杂度均以课件末尾题目为准。
单页手写提纲用于快速回顾课堂主线,详细推导和作业解答见本文: