基数排序（Radix Sort）
基数排序按数字位依次排序，依赖稳定排序保持低位排序结果，是计数排序在多位整数上的扩展应用。
定义
基数排序（Radix Sort）是一种非比较排序算法。它将待排序元素按“位”拆解，从低位到高位依次进行稳定排序，最终得到整体有序结果。
这里的“基数”（radix）指进制。例如十进制整数的基数是 10，二进制整数的基数是 2。
核心特性
| 特性 | 说明 |
|---|---|
| 排序类型 | 非比较排序 |
| 基础子过程 | 通常使用稳定版 计数排序 |
| 稳定性要求 | 每一位排序都必须稳定 |
| 数据要求 | 整数，或可以映射成整数的值 |
| 时间复杂度 | O(d * (n + k))，d 为位数，k 为基数 |
| 空间复杂度 | O(n + k) |
基本原理
以十进制整数为例：
- 按个位数稳定排序
- 按十位数稳定排序
- 按百位数稳定排序
- 重复直到最高位
由于每一轮排序都是稳定的，高位排序不会破坏低位已经建立好的相对顺序。
原始数据: 329, 457, 839, 439, 720, 355, 350
个位排序: 720, 350, 355, 457, 329, 839, 439
十位排序: 720, 329, 839, 439, 350, 355, 457
百位排序: 329, 350, 355, 439, 457, 720, 839
与计数排序、桶排序的关系
| 维度 | 基数排序 | 计数排序 | 桶排序 |
|---|---|---|---|
| 核心思路 | 按位多轮排序 | 统计每个值出现次数 | 将元素映射到桶中 |
| 典型数据 | 多位整数 | 范围较小的整数 | 分布较均匀的数据 |
| 稳定性要求 | 必须稳定 | 可实现为稳定 | 取决于桶内排序 |
| 关系 | 常用计数排序作为每一位的子过程 | 基数排序的常用子过程 | 常被拿来对比，但不是同一思路 |
注意事项
- 基数排序不是通用比较排序，输入必须能按位拆解或映射为整数
- 每一位排序必须稳定，否则低位顺序会被破坏
- 处理负数、不同位数、字符串等场景时需要额外映射策略
- 当位数 d 较大时，复杂度优势会下降
应用场景
- 整数排序
- 固定位数编号排序
- 可以映射为整数键的字符串或对象排序
- 需要线性级排序且数据形态适合按位处理的场景