排序 · 分区、下界与线性时间

排序算法的教科书叙述多半止于「快排平均 $O(n \log n)$、归并稳定、堆排原地」这几句结论。本系列把三个真正会咬人的地方摊开:partition 的指针边界 (写错一个 <= 就死循环)、$\Omega(n \log n)$ 这条下界为什么成立又为什么不适用于所有排序、以及线性时间排序拿什么换来了线性。

三页彼此接续:quicksort 讲清 partition 与 pivot;比较排序的下界 用决策树给出 $\lceil \log_2 n! \rceil$ 这条硬底线, 并把 heapsort 放在它旁边作为紧确达成者;线性时间排序 展示不做比较时下界如何失效。归并线上的自适应排序另有 Timsort 与 Powersort 一页, 堆本身的机制见 二叉堆。

可复现的随机: 本系列所有 lab 的随机化 (pivot 随机选、样例数组生成、bucket 输入分布) 都走 core/rng.ts 的种子生成器, 没有一处 Math.random。帧序列因此完全确定, 正文里引用的比较次数与页面上单步走出来的数字对得上。 quicksort · partition

quicksort：分区与 pivot

quicksort 的全部难点在 partition。本页拆开 Lomuto 与 Hoare 的指针边界、pivot 选法对递归深度的影响、重复键上的三路切分，以及 introsort 用递归深度阈值切回 heapsort 的兜底。

lower bound · heapsort

比较排序的下界与 heapsort

decision tree 模型给出比较排序的硬底线：$n!$ 个叶子迫使树高不低于 $\log_2 n!$。本页穷举实测各算法离底线多远，并把 stable 与 in-place 摆进同一张坐标系。

counting · radix

线性时间排序：键的结构

counting、radix 与 bucket sort 不做元素间的比较，因而不受 $\Omega(n \log n)$ 约束。本页给出它们绕开下界的理由、radix sort 对 stable 的硬性依赖，以及线性时间背后的值域、位数与常数账。

相关链接

• 自适应归并排序 · Timsort 与 Powersort 本站 归并线上的另一半:先识别天然 run, 再让合并顺序决定总搬移量。与本系列的 partition 线互补。
• 优先队列与二叉堆 本站 sift-up / sift-down 与 $O(n)$ heapify 的机制在那一页讲透, 本系列只从排序视角用它。
• 分治与主定理 本站 quicksort 的 $T(n) = T(k) + T(n-k-1) + \Theta(n)$ 为何在均分时才落到 $O(n \log n)$。
• 二分查找 本站 同一类指针边界问题:开区间与循环不变量。二分插入排序与三路分区的边界写法同源。
• Quicksort (Hoare, 1961) dl.acm.org 原始论文, 双指针分区的最初形态就在这里, 与后来教科书里的 Lomuto 版本并非一回事。
• Quicksort is Optimal (Sedgewick & Bentley) cs.princeton.edu 三路分区在重复键上的最优性:代价随键分布的熵走, 与 Powersort 那条熵界同源。