📚 覆盖：第 9–13 讲 · ⚠️ 本套的证明题（题 5、8、11、16）是本课程排序部分的核心，务必独立完成。

第一部分：插入排序与归并排序（第 9 讲）

题 1（4 分）

(a) 什么是稳定排序？给一个"必须用稳定排序"的具体场景。 (b) 插入排序内层条件写 a[i] > key 与 a[i] >= key 有什么区别？ (c) Go 的 slices.Sort 和 slices.SortStableFunc 分别是什么算法？何时必须用后者？

题 2（5 分）

数组 A = [5, 1, 4, 2, 8, 3]。

(a) 逆序对有多少个？全部列出。 (b) 插入排序在它上面会移动多少次元素？ (c) 证明：插入排序的移动次数恰好等于逆序对数量。

题 3（4 分）

(a) 归并排序的 merge 中，buf[j] < buf[i] 为什么不能写成 <=？ (b) 手工追踪 CountInversions([2, 4, 1, 3, 5])，写出每次合并累加的逆序对数。 (c) 为什么统计逆序对能做到 Θ(n log n) 而不是 Θ(n²)？

题 4（4 分）

(a) 为什么外部排序用归并而不是快排？从 I/O 访问模式回答。 (b) k 路归并用什么数据结构？复杂度是多少？ (c) 归并排序能做到原地吗？代价是什么？

第二部分：堆（第 10 讲）

题 5（8 分）⭐

(a) 给出数组 [16, 4, 10, 14, 7, 9, 3, 2, 8, 1] 的树形表示（最大堆视角）。 (b) 执行 siftDown(1)（0-indexed），画出结果。 (c) 证明自底向上建堆是 Θ(n)，写出关键求和步骤。 (d) 为什么逐个 Push 建堆是 Θ(n log n)？两者的代价分布有什么区别？

题 6（4 分）

(a) Pop 时为什么把最后一个元素搬到根，而不是直接提升某个子节点？ (b) 堆排序是原地且最坏 Θ(n log n)，为什么实践中还是快排更常用？ (c) introsort 如何利用堆排序？

题 7（6 分）

(a) 求最大的 k 个元素，为什么用最小堆？堆里存 k 个还是 n 个？ (b) 对比三种 Top-K 方法（全排序 / 堆 / 快速选择）的时间、空间与适用场景。 (c) 数据是无限流时必须用哪种？为什么？

题 8（5 分）

对顶堆求流式中位数。

(a) 写出 Add 的实现，说明为什么"先推给对面再拿回来"。 (b) 两个堆的大小关系不变式是什么？ (c) 复杂度是多少？

第三部分：快速排序（第 11 讲）

题 9（5 分）

(a) Lomuto 划分在"所有元素相等"时会怎样？为什么？ (b) Hoare 划分为什么没有这个问题？ (c) 两者的交换次数相差多少？

题 10（4 分）

证明：若每次划分比例固定为 1:99，快排仍是 Θ(n log n)。给出递归树层数的上下界。

题 11（8 分）⭐

用指示随机变量证明随机化快排的期望比较次数是 O(n log n)。

(a) 定义 X_{ij} 并写出 E[X] 的表达式。 (b) 陈述并证明核心引理：“zᵢ 与 zⱼ 被比较 ⟺ ？” (c) 推出 Pr[比较] = 2/(j−i+1)。 (d) 完成求和。

题 12（4 分）

(a) 三路划分在什么输入上把 Θ(n log n) 降到 Θ(n)？ (b) 若数组只有 k 个不同的值，复杂度是多少？ (c) “只递归较小的一半"如何把栈深度从 O(n) 降到 O(log n)？写出代码。

第四部分：下界与线性排序（第 12 讲）

题 13（6 分）⭐

(a) 画出 n = 3 的比较排序决策树。 (b) 叶子数为什么至少是 n!？树高对应什么？ (c) 完整写出 Ω(n log n) 下界的证明，指出用到 Stirling 的位置。 (d) 从信息论角度重述这个下界。

题 14（5 分）

(a) 计数排序的第三步为什么必须倒序遍历？举一个正序会破坏稳定性的具体例子。 (b) 基数排序为什么必须使用稳定的子排序？用两位数举例说明。 (c) 这两个"稳定性"要求是同一件事吗？

题 15（5 分）

用基数排序排 n = 10⁶ 个 32 位整数，每轮取 r 位。

(a) 写出复杂度关于 r 的表达式。 (b) 求使复杂度最优的 r。⚠️ 不要只回答「取 r = log₂ n」，请代入具体数字比较，并说明轮数与缓存带来的额外约束。 (c) 比较此时与 slices.Sort 的操作数量级。 (d) 为什么它没有"打破” Ω(n log n) 下界？

题 16（4 分）

(a) 桶排序的期望 Θ(n) 依赖什么假设？ (b) 构造一个使它退化为 Θ(n²) 的输入。 (c) 为什么随机化不能打破 Ω(n log n)？

第五部分：选择（第 13 讲）

题 17（6 分）

(a) 快速选择与快速排序的递归式差在哪里？为什么这个差别把 n log n 变成 n？ (b) 用代换法证明随机化快速选择的期望时间是 Θ(n)。 (c) 为什么快速选择可以写成循环？带来什么好处？

题 18（8 分）⭐

(a) 画图说明 BFPRT 中"至少 3n/10 个元素大于主元"。 (b) 写出递归式并用代换法求解，指出"9/10 < 1"用在哪一步。 (c) 组大小取 3 时递归式变成什么？解是多少？为什么恰好不行？ (d) 组大小取 7 也线性，为什么标准做法仍取 5？ (e) 为什么 BFPRT 在实践中几乎不单独使用？它的价值是什么？

参考解答

题 1

(a) 相等元素的相对顺序在排序后保持不变。场景：多关键字排序——先按工资排、再用稳定排序按部门排，同部门内的工资顺序得以保留。用户点击表头依次排序时必须如此。

(b) > 遇到相等元素就停下、不越过它 ⟹ 稳定；>= 会继续左移越过相等元素 ⟹ 不稳定（仍然正确）。一个字符之差。

(c) slices.Sort 是 pdqsort（不稳定）；slices.SortStableFunc 是插入排序 + 原地归并（symmerge，稳定）。当元素有排序键之外的可辨识信息、且依赖多轮排序或原有顺序时，必须用后者。

题 2

(a) 逆序对：(5,1)、(5,4)、(5,2)、(5,3)、(4,2)、(4,3)、(8,3) —— 共 7 个。

(b) 7 次。

(c) 插入排序的内层循环每执行一次，就把 a[i] 右移一位、key 相对左移一位，恰好消掉一个逆序对（相邻交换恰好改变一个逆序对的状态）。开始有 I 个逆序对，结束为 0，故总移动次数 = I。∎

题 3

(a) 写成 <= 时，相等元素会优先从右半取走，导致原本靠后的元素排到前面，破坏稳定性。

(b)

[2,4] 与 [1,3,5] 之前先分别归并：
  [2] [4] → [2,4]，inv += 0
  [1] [3] → [1,3]，inv += 0；再与 [5] → [1,3,5]，inv += 0
最后合并 [2,4] 与 [1,3,5]：
  取 1（右半）：左半剩 2 个（2,4）⟹ inv += 2
  取 2（左半）
  取 3（右半）：左半剩 1 个（4）  ⟹ inv += 1
  取 4，取 5
总计 inv = 3      （验证：(2,1)、(4,1)、(4,3)）

(c) 因为合并时可以一次性统计出 (mid − i) 个跨越逆序对，而不必逐对枚举。分治把 Θ(n²) 的枚举变成 Θ(log n) 层的 Θ(n) 统计。

题 4

(a) 归并只需顺序读每个 run，而快排需要在整个数组上随机访问。顺序 I/O 比随机 I/O 快约两个数量级，外部排序的瓶颈在磁盘。

(b) 大小为 k 的最小堆。总代价 Θ(N log k)（N 是元素总数），而朴素每次扫 k 个 run 是 Θ(Nk)。

(c) 能（symmerge 等原地归并算法），但合并变成 O(n log n)，总复杂度退化到 O(n log²n)，常数也大很多。“稳定 + 原地 + O(n log n)“三者不可兼得。

题 5

(a)

              16
            ╱    ╲
          4       10
        ╱  ╲     ╱  ╲
      14    7   9     3
     ╱ ╲   ╱
    2   8 1

(b) siftDown(1)（值 4，最大堆）：孩子是 14 和 7，最大是 14 > 4，交换；4 到位置 3，孩子是 2 和 8，最大是 8 > 4，交换。结果：

              16
            ╱    ╲
         14       10
        ╱  ╲     ╱  ╲
      8     7   9     3
     ╱ ╲   ╱
    2   4 1

(c) 高度为 h 的节点最多 ⌈n/2^{h+1}⌉ 个，每个的 siftDown 代价 O(h)：

T(n) = Σ_{h=0}^{⌊log n⌋} (n/2^{h+1})·O(h) = O(n · Σ_{h=0}^{∞} h/2^h)

由 Σ h·x^h = x/(1−x)²，代入 x = 1/2 得 Σ h/2^h = 2，故 T(n) = O(2n) = Θ(n)。∎

(d) 逐个 Push 用的是 sift-up，其代价是"节点到根的距离”。大多数节点在底部，而底部节点到根的距离恰恰是最大的（log n）。代价分布与 siftDown 正好相反，没有"底部便宜"的红利，总和是 Θ(n log n)。

题 6

(a) 直接提升子节点会破坏完全二叉树的形状（会在中间留洞）。搬最后一个元素到根，正好同时维持形状和（经 siftDown 后）堆序。

(b) 堆排序缓存不友好：siftDown 的访问步长是 2i+1，随深度指数增长，几乎每步都是缓存未命中。快排是两个方向的顺序扫描，硬件预取器可以完美预测，实测常快 2–3 倍。

(c) introsort 主用快排，当递归深度超过 2⌊log n⌋ 时切换到堆排序，把最坏情况从 Θ(n²) 压到 Θ(n log n)，同时保留快排的平均性能。

题 7

(a) 因为要淘汰的是"当前 k 个里最小的那个”，堆顶必须是待淘汰者 ⟹ 最小堆。堆里只存 k 个。

(b)

(c) 必须用堆。快速选择需要把全部数据放进内存并随机访问、重排；流式数据既不能全放内存也不能回头。

题 8

(a)

heap.Push(m.hi, x)              // 先进右半
heap.Push(m.lo, heap.Pop(m.hi)) // 右半最小移到左半
if m.lo.Len() > m.hi.Len() { heap.Push(m.hi, heap.Pop(m.lo)) }

“先推给对面再拿回来"消除了"该放哪一边"的判断：无论 x 落在哪个区间，经过一次 hi→lo 的传递后，lo 的所有元素必然 ≤ hi 的所有元素这个不变式自动成立。

(b) size(hi) ∈ {size(lo), size(lo)+1}（约定奇数个时中位数在 hi 顶）。

(c) Add 是 O(log n)（常数次堆操作），Median 是 O(1)。

题 9

(a) 条件 a[j] <= pivot 恒成立，每次划分点都落在最右端，递归深度 n ⟹ Θ(n²)。

(b) Hoare 的两个指针在遇到等于 pivot 的元素时都会停下并交换，使相等元素被均匀分到两侧，划分接近对半。

(c) Lomuto 平均 n/2 次交换，Hoare 平均 n/6 次，Hoare 约少 3 倍。

题 10

T(n) = T(n/100) + T(99n/100) + Θ(n)。递归树每层总代价 ≤ n。最浅叶子在深度 log₁₀₀ n，最深在 log_{100/99} n ≈ 68.9·log₁₀₀ n。

n·log₁₀₀ n ≤ T(n) ≤ n·log_{100/99} n    两端都是 Θ(n log n)
⟹ T(n) = Θ(n log n)

只差常数因子（约 69 倍），不是量级差别。

题 11

(a) 设排序后为 z₁<z₂<…<zₙ。X_{ij} = 1 iff zᵢ 与 zⱼ 曾被比较。X = Σ_{i<j} X_{ij}，E[X] = Σ_{i<j} Pr[zᵢ 与 zⱼ 被比较]。

(b) 引理：zᵢ 与 zⱼ 被比较 ⟺ zᵢ 或 zⱼ 是集合 Zᵢⱼ = {zᵢ,…,zⱼ} 中第一个被选为主元的元素。

证明：若先选中的是中间元素 z_k（i<k<j），则 zᵢ、zⱼ 被分到划分两侧，此后永不相遇；若先选中 zᵢ 或 zⱼ，它作为主元要与当前子数组所有元素比较，包括对方。且两元素至多比较一次（主元比完即被移出递归）。∎

(c) 主元从当前子数组均匀随机选取，故 Zᵢⱼ 中每个元素等概率成为第一个主元；|Zᵢⱼ| = j−i+1，其中 2 个是"好"的：Pr = 2/(j−i+1)。

(d)

E[X] = Σ_{i=1}^{n-1} Σ_{j=i+1}^{n} 2/(j−i+1)
     = Σ_{i=1}^{n-1} Σ_{k=1}^{n-i} 2/(k+1)
     < Σ_{i=1}^{n-1} 2Hₙ = O(n log n)                  ∎

题 12

(a) 输入中只有少数几个不同值时。三路划分把"等于 pivot"的整段直接跳过递归。

(b) Θ(n log k)；k = 1 时是 Θ(n)。

(c)

for lo < hi {
    p := partition(a, lo, hi)
    if p-lo < hi-p {
        quickSort(a, lo, p-1)  // 递归较小的一半
        lo = p + 1             // 较大的一半用循环
    } else {
        quickSort(a, p+1, hi)
        hi = p - 1
    }
}

每次递归的规模至少减半（因为递归的是较小的一半），故深度 ≤ log₂ n。

题 13

(a) 见第 12 讲第一节的图，6 片叶子、最长路径 3 次比较。

(b) 每个可能的输出排列必须至少对应一片叶子（否则存在算法给不出正确答案的输入），故 L ≥ n!。树高 = 最坏情况的比较次数。

(c) 高度 h 的二叉树最多 2^h 片叶子：

2^h ≥ L ≥ n!  ⟹  h ≥ log₂(n!)

由 Stirling：log₂(n!) = n log₂n − n log₂e + O(log n) = Θ(n log n) ⟹ h = Ω(n log n)。∎

(d) 要区分 n! 种可能答案，每次比较只提供 1 比特信息，故至少需要 log₂(n!) ≈ n log₂ n 次比较。排序的本质是确定输入是哪一个排列，而比较是一次只能问一个是非问题的信道。

题 14

(a) 前缀和给出的是每个值的最后一个位置。倒序遍历时，同值元素中原本靠后的先被放置、占据靠后位置，相对顺序保持。

例：[a₁=2, b=1, a₂=2]（a₁、a₂ 值都是 2）。倒序：先放 a₂ 到 2 号位、再放 a₁ 到 1 号位 ⟹ 结果 [1, a₁, a₂] ✓。正序：先放 a₁ 到 2 号位、再放 a₂ 到 1 号位 ⟹ [1, a₂, a₁] ✗ 顺序颠倒。

(b) LSD 基数排序处理第 i 位时，前 i−1 位已排好；稳定性保证第 i 位相同的元素保持按低位排好的顺序。例：[21, 12] 先按个位排得 [21, 12]，再按十位排——若不稳定，十位相同（这里不同，换成 [21, 22] 按个位排为 [21, 22]，按十位排若打乱则得 [22, 21]）就会丢掉低位的工作。

(c) 是同一件事的两个层面：计数排序的稳定性是基数排序正确性的前提。所以计数排序的倒序遍历不是可选优化，而是必需。

题 15

(a) T(n) = Θ((32/r)(n + 2^r))。

(b) ⚠️ 这一问是个陷阱。渐近指导是 r = Θ(log n)，但它给出的是量级而非最优参数。代入具体数字：

r = 11  →  T = 2.92×10⁶        r = 16  →  T = 2.13×10⁶
r = 17  →  T = 2.13×10⁶ ← 最小  r = 20  →  T = 3.28×10⁶

公式的最小值点在 r ≈ 17，而 r = log₂ n = 20 比它差 1.54 倍——因为 2^r 指数增长，越过 n 之后计数数组的开销迅速压倒省下的轮数。

再加两条工程约束：轮数 32/r 必须是整数（r = 20 意味着 1.6 趟，不可实现），计数数组要放进缓存（2^16 × 4B = 256 KB 已溢出 L2，而计数阶段是随机写）。实践答案是 r = 16（2 趟）或 r = 11（3 趟，L1 友好）。

(c) slices.Sort 约 1.39 n log₂ n ≈ 2.8×10⁷。取 r = 16 时基数排序约 2.13×10⁶，理论上快约 13 倍；实测通常只有 2–4 倍——差距来自基数排序计数阶段的随机写缓存未命中，以及 pdqsort 高度优化的常数。⭐ 这个「理论 13 倍 vs 实测 3 倍」的落差本身，就是渐近分析局限性的最好例子。

(d) 因为下界只对比较排序成立。基数排序用了键的位表示做直接寻址，一次操作获取的信息远多于 1 比特，它不在下界的模型内。

题 16

(a) 输入在区间上均匀分布，使每个桶的期望元素数为 O(1)。

(b) 全部元素落在 [0, 1/n) 内（如 [0, 0.0000001, 0.0000002, …]），全进第 0 个桶，桶内插入排序 Θ(n²)。

(c) 决策树论证对随机化算法同样适用：把随机串固定后每条随机串对应一棵决策树，取平均树高仍 ≥ log₂(n!)。随机化能避开最坏输入，但不能减少必需的信息量。

题 17

(a) 快排 T(n) = 2T(n/2) + Θ(n)，选择 T(n) = T(n/2) + Θ(n)——差在系数 2 上（只递归一侧）。后者的几何级数 n + n/2 + n/4 + … < 2n 收敛，故是 Θ(n)；前者每层总量都是 n，共 log n 层。

(b) 随机主元把数组划成 (i, n−i−1)，最坏进较大一侧：

E[T(n)] ≤ (2/n)Σ_{i=⌊n/2⌋}^{n-1} E[T(i)] + an
猜 E[T(n)] ≤ cn：
  ≤ (2c/n)(3n²/8) + an = (3c/4)n + an ≤ cn   （取 c ≥ 4a）✓

(c) 只递归一侧 ⟹ 天然尾递归，可直接改成 for 循环。好处：空间从 O(log n) 降到 O(1)，且无栈溢出风险。

题 18

(a) 各组竖排（组内自上而下递增）、按组中位数横向递增排列。x 是各组中位数的中位数 ⟹ 一半的组（约 n/10 组）其中位数 ≥ x；在这些组里，中位数及其下方的 3 个元素都 ≥ x：

≥ x 的元素数 ≥ 3·(1/2·⌈n/5⌉) ≈ 3n/10

对称地 ≤ x 的也至少 3n/10。∎

(b) T(n) ≤ T(n/5) + T(7n/10) + O(n)。猜 T(n) ≤ cn：

T(n) ≤ c(n/5) + c(7n/10) + an = (9c/10)n + an ≤ cn   只要 c ≥ 10a  ✓

“9/10 < 1"用在最后一步：它使得 (9c/10)n + an ≤ cn 有解（剩下的 c/10 的"余量"吸收了 an）。

(c) g = 3 时每侧至少排除 2·(n/6) = n/3，递归式 T(n) = T(n/3) + T(2n/3) + O(n)。规模和 1/3 + 2/3 = 1，没有余量吸收线性项，解是 Θ(n log n)。

(d) g = 7 时规模和 1/7 + 5/7 = 6/7 < 1，也是线性。但每组排序的常数开销更大（7 个元素 vs 5 个），总常数更差。5 是使和 < 1 的最小奇数。

(e) 常数因子约 20–40，而随机化快速选择约 2–4，实测慢 5–10 倍。价值：① 理论上证明"选择比排序容易”（Θ(n) vs Θ(n log n)）；② 工程上作为 introselect（std::nth_element）的兜底，保证最坏线性。