基数排序

基数排序按关键字的各位（个位、十位…或按字节）做多次稳定的「分配 / 收集」，属于分配类排序，不直接比较元素大小。

本文解决什么问题

• LSD（低位优先）流程直觉
• 适用条件与复杂度
• 和比较排序的边界

适用

关键字可拆成有限位、各位取值范围不大（如非负整数、定长字符串）。

常见 LSD：先按个位稳定排序，再按十位……直到最高位。

例: 170, 45, 75, 90, 802, 24, 2, 66
按个位分配收集 → 再按十位 → 再按百位 → 有序

每一位常用计数排序做稳定子排序（本篇不展开计数排序完整代码）。

复杂度与性质

设 $d$ 为位数，$r$ 为进制（如 10 或 256）：

时间	约 $O(d\cdot(n + r))$
空间	通常要 $O(n + r)$
稳定	是（要求子排序稳定）

不是基于比较的下界 $O(n \log n)$ 在此场景可不适用——因为利用了键的数字结构。

小结

基数排序在特定关键字形态下可很快。先理解「按位多趟稳定分配」，再写完整代码。

下一篇：排序算法比较。