counting · radix

线性时间排序：键的结构

比较排序的下界证明了一条谁也绕不过的底线，前提是算法获取信息的唯一途径是比较。本页的三种排序不满足这个前提：它们拿键的表示直接算出位置，一次元素之间的大小比较都不做。底线随之失效，代价是对键的形状提出了要求。

三节各讲一种：counting sort 按键值直接定位，radix sort 把它按位重复若干遍，bucket sort 把值域切段后段内再排。末节结算这些算法在 $n$ 之外欠下的账。

1 · 下界为什么管不到

decision tree 模型有两个前提：每个内部节点只有两条出边，因为一次比较只有两种答案；以及算法关于输入的全部知识都来自这些答案。 $n!$ 个叶子需要 $\lceil \log_2 n! \rceil$ 层，说的是「用只有两个刻度的尺子量 $n!$ 种可能，至少要量多少次」。

counting sort 破的是第二条。键值为 $v$ 的元素落在计数数组的第 $v$ 格，这一步没有问任何两个元素谁大谁小，信息直接来自键的表示。同一个数组重排一次就得到答案， $\log_2 n!$ 这个数字对它不构成任何约束。

代价写在前提里。比较排序只要求键之间存在全序，键是什么都行；本页的三种算法要求键有额外结构——是有界的整数，或者能拆成有限个位，又或者已知它大致均匀地散布在某个区间上。信息不会凭空出现，它是从键的表示里读出来的，键没有这种结构时读不出来。

2 · counting sort

counting sort 只扫三趟：数出每个键出现几次；对计数数组求前缀和；再把输入逐个填进输出。

前缀和之后，cnt[v] 的含义是「键不超过 $v$ 的元素共有几个」，也就是键为 $v$ 的最后一个元素应该落的下标加一。填充这一趟从右往左扫输入，每放一个就把对应的计数减一。方向选右起并非美学问题：键相同的元素里，输入中最靠后的那个先被放到最靠后的空位，输入里的先后因此原样保留下来，counting sort 是 stable 的。

时间与空间都是 $\Theta(n + k)$ ， $k$ 是值域大小。 $k$ 与 $n$ 同阶时它才配叫线性算法；图 2-1 的第三个样例 $k = 10$ 而 $n = 8$ ，计数数组比输入本身还长。

图 2-1 · counting sort 的三趟。上方是输入，中间是计数数组，下方是输出槽位，槽位下的小字标出这个元素来自输入的哪个位置。可换样例观察

k

与

n

的比例。

3 · radix sort 对 stable 的硬性依赖

值域一大，counting sort 的计数数组就撑不住。把键按 $b$ 进制拆成 $d$ 位，每次只按一位分发，每位的值域只有 $b$ ，问题就回到了 counting sort 能处理的规模。这就是 radix sort。

LSD radix sort 从最低位开始，逐位向上做 $d$ 趟分发。它的正确性是一个归纳：假设前 $t$ 趟之后元素已按低 $t$ 位有序，第 $t+1$ 趟按第 $t+1$ 位分发时，这一位不同的元素由本趟定序；这一位相同的元素在桶内保持进桶的先后，也就是上一趟留下的次序，于是整体按低 $t+1$ 位有序。

归纳里的支点是那句「保持进桶的先后」。逐位分发一旦不 stable，上一趟的成果当场作废：

警示 · 把回收改成「每个桶反过来倒出」，8 个两位数的样例 31 41 21 11 51 12 32 22 实测排成 12 11 22 21 32 31 41 51：十位确实升序，但十位相同的那两个数里，个位大的反而排在前面，第一趟按个位排好的次序被第二趟抹掉了。第一趟本身仍然合法，那时还没有需要保住的旧次序。这条实测钉在 core/linear.test.ts，正确与错误两种回收方式的末态都写进了断言。

图 3-1 · LSD radix sort 的逐位分发与回收。色块下方小字是本趟看的那一位，读数条上的「低位有序」标出已处理的那几位是否仍整体不降。可关掉桶内保序，观察它在第二趟崩掉。

4 · MSD 与提前收手

MSD radix sort 反过来，从最高位开始分桶，再对每个桶按下一位递归。它有一个 LSD 拿不到的好处：某个桶只剩一个元素时，这个元素的位置已经定了，更低的位一眼都不用看。字符串这类变长键几乎只能用 MSD，因为从最低位起要先对齐长度。

提前收手能省多少，取决于键在高位上散不散得开。8 个三位数的样例里 LSD 无论如何要读满 24 个位；高位就把大家分开的那份输入，MSD 只读 10 个位，省 58%；共享前缀的那份与首位全相同的那份则都读满 24 个，一分不省。MSD 的优势有前提，不是白给的。

图 4-1 · MSD radix sort 的递归分桶。高亮块是当前正在处理的段，读数条右端对照 LSD 与 MSD 各自读了多少个位。可换输入，看三种键分布下的差别。

5 · bucket sort 与分布假设

bucket sort 把值域等分成 $m$ 段，按值把元素扔进对应的桶，桶内用插入排序，最后按桶号拼起来。落桶只是一次除法，比较全部发生在桶内。

期望线性的推导要用到「键在值域上均匀分布」这个假设：每个桶期望装 $n/m$ 个元素，桶内插入排序的期望代价是 $O((n/m)^2)$ ， $m$ 个桶加起来是 $O(n^2/m)$ ；取 $m = \Theta(n)$ 就落回 $O(n)$ 。假设一旦不成立， $n^2/m$ 里的平方就露出来了。

$n = 24$ 落进 6 个桶的实测：均匀分布下桶内比较 40 次、六个桶分别装 2、4、8、3、2、5 个；把分布换成三次方压向左端后是 78 次，桶长变成 16、2、0、2、0、4，最大的桶独吞了三分之二的元素。

注 · 偏斜的代价在小规模上看不出平方的样子。原以为把分布拧歪就该立刻显出 $O(n^2)$ ， $n = 24$ 上却只涨到 1.95 倍——最大的桶虽然膨胀，其余五个几乎空了，省下的抵掉一部分。把规模抬到 $n = 1024$ 、 $m = 128$ 才拉得开：均匀 2702 次比较对偏斜 11341 次，最大桶 17 对 190，倍率 4.2。平方项要等最大的那个桶自己长到足够大才显形，这也说明「均匀分布」这个前提在小数据上很难被证伪。

图 5-1 · bucket sort 的落桶、桶内插入排序与回收。每个桶的表头写着它负责的值域段与当前元素个数。可切换分布与桶数，读数条给出桶内比较次数与最大桶。

6 · 线性时间的账单

三种算法的复杂度里都带着与键有关的参数，把它们摊开才看得出「线性」是对谁而言的。

算法	时间	额外空间	前提
counting sort	$\Theta(n + k)$	$\Theta(n + k)$	键是 $0$ 到 $k-1$ 的整数
LSD radix sort	$\Theta(d(n + b))$	$\Theta(n + b)$	键可拆成 $d$ 个 $b$ 进制位
MSD radix sort	最坏同上，键早分开则更少	$\Theta(n + b)$ 加递归栈	同上，且高位有区分度
bucket sort	期望 $\Theta(n)$ ，最坏 $\Theta(n^2)$	$\Theta(n + m)$	键在值域上大致均匀

$d$ 与 $b$ 可以互换：加大基数就减少趟数。同一份 24 个三位数上， $b = 10$ 要 3 趟， $b = 100$ 只要 2 趟，代价是桶数组从 10 格涨到 100 格。键是 64 位整数、取 $b = 256$ 时 $d = 8$ ，也就是恒定 8 趟线性扫描——对小的 $n$ ，这 8 趟未必比 $n \log_2 n$ 次比较更快。

还有一栏是三者共同的短板：都不 in-place。counting sort 与 radix sort 需要一个 $\Theta(n)$ 的输出数组，bucket sort 需要 $m$ 个动态数组。比较排序的下界 §5 那张表里， $O(1)$ 额外空间那一格至今只有 heapsort 一个住户，本页三种算法一个也进不去。

7 · 参考文献

Seward, H. H. (1954). Information sorting in the application of electronic digital computers to business operations (Master's thesis, Report R-232). MIT Digital Computer Laboratory.
Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley, §5.2.5.
McIlroy, P. M., Bostic, K., & McIlroy, M. D. (1993). Engineering radix sort. Computing Systems, 6(1), 5–27.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press, Chapter 8.