基数排序

定义

基数排序(Radix Sort)是一种非比较排序算法,把关键字拆成若干位(如十进制位、字节),按位多轮分发与收集完成排序,历史可追溯到打孔卡片时代的制表机。

原理

常用 LSD(最低位优先)方案:从最低位开始,每一轮用稳定的计数排序按当前位把元素分配到桶中再收集,处理完所有位后整体有序。稳定性是正确性的关键。设关键字有 d 位、每位取值 k 种,复杂度为 O(d(n+k)),当 d 为常数时接近线性。MSD(最高位优先)则从高位递归分桶,适合变长字符串。

应用

大规模整数、IP 地址、定长字符串排序,数据库与外排序系统中的分区阶段,以及后缀数组构造(如 DC3 算法)内部都用到基数排序思想。

优缺点

突破比较排序 O(n log n) 下界;但需要额外空间,且关键字位数大或类型复杂时不适用。