排序与查找

排序是算法的试金石：一个问题族（比较排序）有一个可证明的下界，另一族（非比较）绕过它。本章讲快排、归并、堆排序的比较与工程选择，比较排序 $\Omega(n \log n)$ 下界的决策树证明，以及二分查找的边界处理。

比较排序

算法	平均	最坏	稳定	空间	备注
快速排序	$O(n \log n)$	$O(n^2)$	否	$O(\log n)$	平均最快、缓存友好
归并排序	$O(n \log n)$	$O(n \log n)$	是	$O(n)$	稳定、适合外部排序
堆排序	$O(n \log n)$	$O(n \log n)$	否	$O(1)$	最坏有保证、缓存不友好
插入排序	$O(n^2)$	$O(n^2)$	是	$O(1)$	小数组最快（ $n \lesssim 30$ ）

快速排序

选基准、分区（小于/大于）、递归两侧。快排平均最快：分区是顺序访问、缓存友好、内循环紧凑。最坏 $O(n^2)$ 出现在基准选择不均（如已排序数组取首元素）——需要随机化（随机选基准）或三数取中。工程实现用内省排序（introsort）：快排为主，递归过深时切堆排序保住 $O(n \log n)$ 上界，小区间切插入排序——C++ std::sort 的做法。

归并排序

分半、递归、线性合并。稳定且最坏有保证；额外 $O(n)$ 空间换来顺序访问。归并稳定、适合外部排序与链表：外部排序（数据放磁盘）就是多路归并（→ I/O、总线与存储设备）；链表归并无需额外空间。

TimSort

Python 与 Java 的默认排序：归并排序 + 插入排序的混合——找天然有序的 run，小区间用插入排序，run 间用归并。对真实数据（部分有序）接近 $O(n)$ 。

下界：决策树证明

任何比较排序，每个"比较 a<b"有 2 个分支， $n!$ 种排列都要区分。决策树至少有 $n!$ 个叶子，高度至少

\log_2(n!) = \Theta(n \log n) \quad (\text{Stirling 近似}).

所以任何基于比较的排序最坏都是 $\Omega(n \log n)$ ——这不是实现不够好，是信息论下界：每次比较只提供 1 比特信息，区分 $n!$ 种排列至少需要 $\log_2 n!$ 比特。

线性时间排序

绕过下界的办法：不比较，直接用键的值。

计数排序：键范围 $[0, k]$ 时，统计频数再顺序输出—— $O(n + k)$ ；
基数排序（radix sort）：从低位到高位逐位用稳定排序—— $O(d(n + k))$ ， $d$ 为位数；定长整数键时线性；
桶排序：均匀分布的键分桶后各自排序——期望 $O(n)$ 。

它们的共同前提：键是有限范围或定长的。这个前提不满足时（任意对象、比较是唯一接口），下界成立。

二分查找

有序数组中查找 $O(\log n)$ 。实现极短，错误极多——二分查找的 off-by-one 是最常见 bug 之一，Knuth 说第一个二分查找发表后 16 年才出现完全正确的版本。两条纪律：

循环不变式：明确"答案若存在则在 [lo, hi) 中"，每次迭代严格缩小且不破坏这个不变式；
中点写法：mid = lo + (hi - lo) / 2 防溢出。

def bisect_left(a, x):
    lo, hi = 0, len(a)          # 不变式：答案在 [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo                    # 第一个 >= x 的位置

变体：bisect_left/bisect_right（第一个 ≥ / > x）、旋转数组查找、求 $\sqrt{x}$ 的整数部分。二分不只用于数组：任何单调谓词都可二分（"容量 x 是否够用"），这是"二分答案"技巧的通用形式。

本章要点

快排平均最快但最坏 $O(n^2)$ ，需要随机化或内省排序；归并稳定、适合外部排序与链表
比较排序下界 $\Omega(n \log n)$ 来自决策树：每次比较 1 比特，区分 $n!$ 排列
计数/基数/桶排序用键值代替比较绕过下界，前提是键有限范围或定长
二分查找的不变式与 mid = lo + (hi - lo)/2 是两条纪律；单调谓词都可二分