Appearance
基数排序
为什么需要基数排序
前面学过的排序算法（快排、归并、堆排等）都依赖元素之间的比较，时间复杂度下界为 O(n log n)。但如果关键字可以被拆分成若干"位"（如整数的个位、十位、百位），我们可以不做任何比较，仅通过对各位的"分配"与"收集"就完成排序——这就是基数排序。
基数排序特别适合关键字位数少但记录数量多的场景，例如对大量手机号、身份证号、扑克牌进行排序。408 考研中，基数排序是非比较排序的代表，常与计数排序一起考查。
核心思想
基数排序的核心特点：
- 非比较排序：不比较关键字大小，而是按关键字的每一"位"做分配与收集
- 多关键字排序：将单个关键字拆分为 d 位，每一位看作一个子关键字
- 借助稳定的"分配-收集"：对每一位使用桶（队列）完成一趟排序，经过 d 趟后整体有序
以三位十进制整数为例，关键字可拆为个位、十位、百位共 d=3 位，每位的取值范围为 0~9，即基数 r=10。排序时依次按个位、十位、百位进行分配与收集，共 3 趟即可完成排序。
交互可视化
通过下方的交互动画，你可以逐步观察基数排序的执行过程：
操作详解
算法思路
基数排序每一趟包含两个步骤：
- 分配（Distribute）：扫描待排序序列，根据当前位的值将每个元素放入对应的桶（队列 Q₀~Q_{r-1}）中
- 收集（Collect）：按桶编号 0→r-1 的顺序，依次将各桶中的元素取出，串接成新的序列
重复上述过程 d 趟（从最低位到最高位），排序完成。
LSD vs MSD
| 方式 | 全称 | 处理顺序 | 特点 |
|---|---|---|---|
| LSD | Least Significant Digit first | 从最低位到最高位 | 实现简单，每趟对全部元素做分配收集，408 考试默认方式 |
| MSD | Most Significant Digit first | 从最高位到最低位 | 需要递归地对每个桶内部继续排序，实现较复杂 |
408 考研中提到的基数排序一般指 LSD 方式，下面的排序过程也以 LSD 为例。
排序过程详解
以序列 {278, 109, 063, 930, 589, 184, 505, 269, 008, 083} 为例（d=3, r=10）：
第 1 趟——按个位分配与收集：
| 桶编号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | 930 | 063, 083 | 184 | 505 | 278, 008 | 109, 589, 269 |
收集结果：930, 063, 083, 184, 505, 278, 008, 109, 589, 269
第 2 趟——按十位分配与收集：
| 桶编号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | 505, 008, 109 | 930 | 063, 269 | 278 | 083, 184, 589 |
收集结果：505, 008, 109, 930, 063, 269, 278, 083, 184, 589
第 3 趟——按百位分配与收集：
| 桶编号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | 008, 063, 083 | 109, 184 | 269, 278 | 505, 589 | 930 |
收集结果：008, 063, 083, 109, 184, 269, 278, 505, 589, 930 —— 排序完成。
关键点：每趟分配时元素进桶的顺序保持前一趟收集的相对顺序，这正是基数排序要求稳定性的原因。
复杂度分析
设 n 为元素个数，d 为关键字位数，r 为基数（每位的取值范围）。
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(d(n+r)) | 与数据初始顺序无关 |
| 最坏时间 | O(d(n+r)) | 与数据初始顺序无关 |
| 平均时间 | O(d(n+r)) | 每趟分配 O(n)，收集 O(r)，共 d 趟 |
| 空间复杂度 | O(r) | 需要 r 个队列（桶）作为辅助空间 |
| 稳定性 | 稳定 | 分配和收集均保持相对顺序 |
与比较排序的对比：当 d 较小且 r 不大时，O(d(n+r)) 近似为 O(n)，优于基于比较的排序的 O(n log n) 下界。但当关键字位数 d 很大时，基数排序反而不如快排等算法。
考研高频考点
- ⭐ 基数排序是非比较排序，不受 O(n log n) 下界限制（选择题高频）
- ⭐ 时间复杂度 O(d(n+r)) 中各参数的含义及计算（填空题/选择题）
- ⭐ 基数排序是稳定的排序算法（判断题/简答题必考）
- ⭐ LSD 方式的分配与收集过程手动模拟（大题常考）
- 空间复杂度为 O(r)，需要 r 个队列辅助
- 适用场景：关键字位数少、记录数量多（如多关键字排序、链式存储场景）