形式陈述

基数排序把键分成 $d$ 个数位，每位取 $k$ 种值。LSD 方案从最低位到最高位，反复使用稳定的按单个位排序；归纳可证处理前 $i$ 位后，记录按这 $i$ 位字典序有序。若每轮用计数排序，时间 $\mathrm{\Theta }(d(n+k))$。MSD 方案从最高位递归分桶，可提前终止但需要不同稳定性与空间分析。键长度、基数和表示成本必须计入复杂度。

直觉

稳定排序保证新处理的高位优先级覆盖旧的低位顺序，而相同高位内部仍保留低位排序结果，于是逐位累积成完整次序。

例子与边界

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

推论与应用

基数排序适合固定宽度整数、字符串和数据库键，在字长受限模型中可达到线性或近线性时间，并说明比较下界不适用于利用键内部结构的算法。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998，Chs. 5–6。