第3章 排序与查找——从确定性到概率性的思想跃迁
本章核心叙事
这章的独特逻辑不是"排序算法有哪些"，而是从确定性到概率性的思想跃迁：确定性排序有其理论极限（Ω(n lg n)），要突破它必须引入随机性。而随机性不是缺陷，是设计——这正是理解 LLM 采样策略的基础。
3.1 排序的理论极限
决策树下界 Ω(n lg n)：n! 个排列 ≤ 2^h 片叶，h ≥ lg(n!) = Ω(n lg n)。信息论论证——每次比较最多 1 bit 信息，排序 n! 种排列至少需要 lg(n!) bit。
排序三元悖：O(n) 时间 + 稳定 + 原地——三者只能取二。计数排序 O(n) 但不原地，堆排序 O(n lg n) 不稳定。不存在同时满足三者的比较排序。
3.2 插入排序与循环不变式
插入排序的完整证明——循环不变式三步法（初始化、保持、终止）。最坏 Θ(n²)，最好 Θ(n)，随机排列期望 Θ(n²/4)——倒置数的概率论证。
3.3 分治——归并排序与快速排序
归并排序 Θ(n lg n)，关键操作是 MERGE。快排的期望分析是指示器随机变量的巅峰之作：E[X] = Σ_{i<j} 2/(j-i+1) = O(n lg n)。随机化快排消除对输入分布的依赖——但 McIlroy 的杀手序列可以对任何确定性快排构造 Θ(n²) 输入。
确定性 vs 随机化快排的本质区分：随机化消除的是对输入分布的依赖，不是对 RNG 的依赖。
3.4 堆排序
堆排序 Θ(n lg n)，原地且最坏情况保证。建堆线性时间 Θ(n) 的证明见 §2.6（高度分布 ⌈n/2^{h+1}⌉）。
3.5 线性时间排序
计数排序（Θ(n+k)）、基数排序（LSD逐位稳定排序）、桶排序（均匀分布假设，E[n_i²] = 2-1/n）——三者各自逃逸决策树下界的不同方式。
3.6 顺序统计量——选择比排序容易
同时求 min 和 max 只需 ⌈3n/2⌉-2 次比较。随机选择期望 O(n)，确定性选择（BFPRT）最坏 O(n)——5 元组的神奇数字。选择问题 Θ(n) 但排序问题 Ω(n lg n)，选择比排序根本更容易。
3.7 哈希——随机化作为设计原则
Skiena 的核心转换：哈希不是数据结构技巧，是随机化算法。balls-and-bins 模型的精确分析。Bloom 过滤器（无假阴性）。MinHash（minhash 相等概率 = Jaccard 相似度）。完美散列（二级方案 E[Σn_j²] < 2n）。
CLRS 的补充：全域散列的形式化构造和 Θ(n²/m) 碰撞上界证明。Rabin-Karp 作为蒙特卡罗随机化算法典范。
3.8 字符串匹配
朴素匹配 O(nm)。Rabin-Karp：滚动哈希，蒙特卡罗随机化算法典范——O(n+m) 期望，小概率假阳性可验证。KMP：失败函数 π 利用模式自身的前缀-后缀重叠，避免主串回溯，O(n+m) 最坏情况保证。KMP 的核心洞察：模式串对自身的匹配提供了跳过不可能位置的信息。
三种算法的选择：需要精确匹配且最坏保证 → KMP；需要多模式匹配 → Aho-Corasick；需要概率性快速 → Rabin-Karp。
3.9 二分查找与超越
二分查找：O(log N) 分治经典。Skiena 的变体（计数、一侧搜索、平方根）。vEB 树将查找从 O(log n) 推到 O(log log u)——当键为整数时可突破比较下界。
3.10 练习
层次一（基础）：
- 证明决策树下界 Ω(n lg n)
- 用循环不变式证明 PARTITION 的正确性
- 比较计数排序、基数排序、桶排序的适用条件和限制
层次二（LLM 协同）： 4. 让 LLM 实现随机化快排，构造使其退化为 Θ(n²) 的输入（McIlroy 杀手序列） 5. 给定一个应用场景，比较三种哈希策略（链式、开放寻址、Bloom 过滤器）的优劣——让 LLM 分析，你评判 6. 排序三元悖在 LLM 推理中的体现：自回归生成是"稳定但不是 O(1)"的，beam search 是"O(1)但不稳定"的——探讨
层次三（Agent 设计）： 7. 设计一个 Skill：输入数据特征（规模、分布、键类型），自动在确定性排序、随机化排序和哈希之间选择策略