基数排序

基数排序逐位处理键，并依赖每一轮稳定排序保留此前低位次序：新处理的高位优先级覆盖旧的低位顺序，相同高位内部却仍保留低位结果，于是逐位累积成完整次序。LSD 版本从最低位到最高位，完成第 $i$ 轮后，元素已按低 $i$ 位有序；MSD 版本从高位递归分桶。它绕过比较下界的代价是键能分解为有限位、每位字母表可高效计数。

十进制数按个位稳定排，再按十位稳定排，可得到两位数整体有序。若每轮排序不稳定，相同十位的元素会打乱个位次序，LSD 正确性失效。取基数 $2^b$ 可一次处理 $b$ 位，但计数数组大小也变为 $2^b$，存在时间—空间权衡。变长字符串需处理终止符和前缀顺序；浮点数与有符号整数要先设计保持数值序的编码。

对三位十进制数 $170,45,75,90,802,24,2,66$，补前导零后依次按个位、十位、百位做稳定计数排序，最终得到数值次序。若某轮排序不稳定，低位已经建立的顺序会被同高位元素打乱。

负数需分离符号或使用适配的编码；变长字符串的结束符次序要明确定义。位数 $d$ 很大或每位值域 $k$ 过大时，$O(d(n+k))$ 未必优于比较排序；把机器字运算当常数也隐含字长模型。

计数排序公理库计数排序Counting sort对有限整数键频数计数并按前缀位置输出的线性时间非比较排序。常作为稳定单轮，词公理库字Word · String从某个有限位置集到字母表的函数，即有限符号序列。提供位序列。若 $n$ 个键各占一个 $w$ bit 机器字，并在Word-RAM公理库Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。中用 $O(1)$ 提取一组数位，则选择每轮 $b$ bit 会得到约 $w/b$ 轮、每轮 $\mathrm{\Theta }(n+2^b)$ 的确定性成本。线性或近线性结论必须连同 $w,b$ 与桶空间一起报告。

超越比较的整数排序公理库超越比较下界的整数排序integer sorting · non-comparison integer sorting通过有限整数宇宙、按位操作和分桶，说明排序复杂度可突破比较模型的 n log n 下界。研究更广的字级分配、打包和递归结构，基数排序只是其中一条基线。固定宽度整数、定长字符串、IP 地址和按字段编码的数据库键都可逐位排序，但编码、稳定性和机器模型必须同时固定。若数据驻留外存，外存排序公理库外存排序External-memory sorting在 I/O 模型中以块传输而非 CPU 比较次数衡量海量排序。按块传输计费；一次数位分桶可能产生大量随机写，RAM 上的 $\mathrm{\Theta }(d(n+k))$ 并不自动给出最优 I/O。即使数据在内存，基数 $2^b$ 的选择也要在轮数、桶数组大小和缓存局部性之间权衡。