14.5.7 基数排序
基数排序是一类“分配-收集”排序。它不是靠两个元素反复比较大小，而是利用关键字可以拆成若干位这一特点，例如三位十进制数可以拆成个位、十位、百位。
为什么基数排序能绕开比较
比较排序要回答的问题是“两个关键字谁大谁小”。基数排序换了一个问法：当前这一位是几？如果是十进制，就把元素放进 0 到 9 这 10 个桶中。
| 术语 | 含义 | 十进制整数例子 |
|---|---|---|
| 基数 | 每一位可能取值的个数 | |
| 位数 | 需要处理多少位 | 三位数通常 |
| 分配 | 按当前位放入对应桶/队列 | 个位为 2 放入 2 号桶 |
| 收集 | 按桶编号顺序取回 | 0 号桶到 9 号桶依次连接 |
因此它适合关键字位数较少、每位取值范围明确的数据。例如课程中的数字都可以看作个位、十位、百位三部分。
从低位到高位的过程
常见基数排序使用 LSD 方法，即从最低位开始：个位 -> 十位 -> 百位。每一趟都按当前位分配，再按桶顺序收集。
以 135, 242, 192, 93, 244, 245, 19, 11 为例：
| 趟数 | 当前位 | 分配依据 | 收集后的序列特点 |
|---|---|---|---|
| 第 1 趟 | 个位 | 5、2、2、3、4、5、9、1 | 个位有序 |
| 第 2 趟 | 十位 | 根据第 1 趟结果继续分桶 | 十位优先，个位顺序在同桶内保留 |
| 第 3 趟 | 百位 | 无百位可视作 0 | 百位、十位、个位整体有序 |
课程里特别强调“按顺序放置”。例如个位同为 2 的 242 和 192，第 1 趟放入 2 号桶时要保持它们进入桶的先后顺序。否则后续高位排序可能被破坏。
为什么基数排序稳定
基数排序的每一趟分配收集都必须稳定：同一个桶内，先进入的元素先出来。这样在处理高位时，低位已经形成的顺序不会被随意打乱。
mermaid
flowchart LR
A["原序列"] --> B["按个位稳定分配/收集"]
B --> C["按十位稳定分配/收集"]
C --> D["按百位稳定分配/收集"]
D --> E["最终有序"]如果桶内不稳定，两个当前位相同的元素可能互换位置，前一趟已经建立的低位次序就丢失了。
复杂度与适用范围
基数排序的复杂度通常与三个量有关：
：记录个数。 ：关键字位数。 ：基数，即桶的个数。
常见教材会把时间复杂度写成：
含义是每一趟要把
| 优势 | 局限 |
|---|---|
| 不依赖两两比较，关键字范围合适时很快 | 要求关键字能拆位或映射到有限桶 |
| 稳定，适合多关键字排序 | 位数 |
| 对整数、定长字符串等结构化关键字友好 | 对一般对象排序不如比较排序通用 |
与计数排序的关系
字幕前面补充过计数排序：关键字只在 0..9，直接统计每个值出现次数。基数排序可以理解为把“有限桶”的思想扩展到多位关键字：每次只按一位分桶，重复多趟完成整体排序。
| 排序 | 适用对象 | 核心动作 |
|---|---|---|
| 计数排序 | 单个关键字范围很小 | 统计每个值出现次数 |
| 基数排序 | 关键字可分为多位，每位范围较小 | 按位分配与收集 |
考试判断
- “不是基于比较的排序”常指基数排序或计数排序。
- “分配和收集”是基数排序关键词。
- 十进制数按位排序，基数通常为 10。
- 三位数通常需要 3 趟；若有无百位数字，可按百位为 0 处理。
- 基数排序稳定，但时间/空间复杂度要看位数和基数。
采用低位优先的基数排序对三位十进制整数排序，通常需要进行几趟分配和收集？
本节小结
基数排序的关键是“按位分桶，稳定收集”。它用关键字结构换取效率，不像比较排序那样通用，但在关键字位数少、每位取值范围明确时非常有优势。