基数排序 | Codeboy's Blog

形式陈述

设每条记录的键是长度 $d\ge1$ 的字，每个数位属于一个有全序的有限字母表，已按该顺序编码为 $0,\ldots,K-1$ ，其中 $K\ge2$ 。最高位优先的字典序就是本页要实现的键序。记录占常数大小，或排序时只搬动常数大小的记录引用；取出一个数位也按常数成本计费。

LSD（最低有效位优先）从最低位到最高位，反复执行稳定的单数位排序。处理完低 $i$ 位后，记录按这 $i$ 位的字典序有序：下一轮把新数位作为主键，相同新数位内部保留已有低位次序。这条归纳不变量给出全部 $d$ 轮之后的正确性。

若输入有 $n\ge1$ 条记录，每轮用稳定计数排序，总时间为

\Theta(d(n+K)),

辅助空间为 $\Theta(n+K)$ ，两轮之间复用桶数组与输出缓冲。空输入直接返回；若允许长度零的键，所有键相同，无需执行数位轮次。

MSD（最高有效位优先）先按最高位分桶，再在各桶内递归处理下一位。不同桶之间的次序已经确定，因此它依赖的是递归前缀分组，而不是 LSD 的“稳定保留低位”证明。桶内为空、单元素或键已结束时可停止；具体时间、空间和稳定性要按所选实现另算。

直觉

LSD 每一轮都把更重要的一位放到前面，同时靠稳定性保存较低位已经建立的次序。它没有把整个键当作只能两两比较的黑盒，而是读取键的内部数位。速度因此取决于键的表示、位数和每位桶数。

例子与边界

对 $[170,45,75,90,802,24,2,66]$ ，先补前导零成三位十进制键，再执行三轮：

例如最后一轮中，百位为零的 $2,24,45,66,75,90$ 必须保留第二轮的顺序。若在同一百位桶里随意调换它们，此前建立的低两位次序就丢失。稳定性控制的是同键记录的相对次序，也让这些低位信息跨轮保留下来。

负整数可以通过保序编码处理；二补码固定宽度键的一种做法是在排序编码中翻转最高符号位，再按无符号键排序。浮点表示则还要明确正负零、无穷与 NaN 的目标排序规则，不能仅把原始 bit 当作普通无符号数。

变长字符串需要终止符与前缀先后约定；固定长度 LSD 的公式不自动涵盖字符访问总量。若键或记录跨越多个字，每次取位、搬运和输出的实际成本也要另计。

推论与应用

若每个键装入一个 $w$ bit 机器字，在Word-RAM中允许常数时间移位和掩码，选择 $1\le b\le w$ 位作为一组数位，会有

d=\lceil w/b\rceil,\qquad K=2^b.

最高一组不足 $b$ 位时按零补齐。于是确定性时间为 $O(\lceil w/b\rceil(n+2^b))$ ，前提是桶与输入/输出数组都在模型允许的可寻址内存内，计数也能装入机器字。扩大 $b$ 减少轮数，却增加桶初始化、空间与缓存压力。

整数排序还有打包、字典和递归分配等路线，基数排序提供其中一条具体基线。固定宽度整数、定长字符串和按字段编码的数据库键都可以使用它，但“固定几轮”只适用于已经固定的键宽，不能替代随规模增长的字长分析。

数据驻留外存时，还要按块传输计费。随机向许多桶写入可能增加 I/O；RAM 中的线性扫描与稳定分配界本身不保证外存最优。

参考资料

Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein，Introduction to Algorithms, 4th ed., MIT Press, 2022，§8.3。
Donald E. Knuth，The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998，§5.2.5。
Robert Sedgewick and Kevin Wayne, Algorithms, §5.1 String Sorts：键索引计数、LSD 与 MSD。