1. 概述
在本篇文章中，我们将介绍 Radix Sort（基数排序），这是一种非比较型排序算法，其最坏时间复杂度为 **O(n)**。
与常见的比较排序算法（如 QuickSort 和 Merge Sort）不同，Radix Sort 不通过比较元素大小来决定顺序，而是基于数字的每一位进行排序。它特别适合处理整数数组的排序场景。
2. 线性时间排序简介
在排序问题中，我们通常面对的是一个包含 n 个对象的数组 a，并有一个排序关系 ≤。我们的目标是将数组按照非递减顺序排列。
对于整数数组来说，比较排序算法（如 QuickSort、Merge Sort）的时间复杂度下限为 **Ω(n log n)**。而 Radix Sort 通过利用数字的位数特性，可以在某些条件下实现 线性时间排序。
3. Radix Sort 算法原理
✅ Radix Sort 的核心思想是：
从最低有效位（个位）到最高有效位依次进行排序，每轮使用稳定的排序算法（如 Counting Sort）来确保排序的稳定性。
3.1 示例说明
假设我们有如下数组：
[170, 45, 75, 90, 802, 24, 2, 66]
我们按位排序的过程如下：
- 个位排序：根据个位数排序
- 十位排序：根据十位数排序（保持个位已排序顺序）
- 百位排序：根据百位数排序（保留前两轮的顺序）
最终数组会完全有序。
⚠️ 注意：每一轮排序必须使用 稳定排序算法，否则前面的排序结果会被破坏。
3.2 时间复杂度分析
假设每个整数有 d 位，每轮使用 Counting Sort，其复杂度为 O(n + k)（k 是当前位的可能取值数量，比如 0~9）。
那么 Radix Sort 的总复杂度为：
O(d * (n + k))
在大多数实际应用中，k 是常数（如 10 或 256），所以整体复杂度简化为：
✅ O(dn)
如果 d 是常数（例如所有数字位数相同），则复杂度为 **O(n)**。
3.3 伪代码实现
algorithm RadixSort(a, n, d):
// a: 待排序数组，每个元素有 d 位
// n: 数组长度
// d: 每个整数的位数
for i from 1 to d:
a = 使用 Counting Sort 按第 i 位排序 a
return a
3.4 正确性证明（简要）
我们使用数学归纳法证明每轮排序后，前 i 位构成的子数组保持有序。由于 Counting Sort 是稳定的，所以在处理更高位时不会破坏低位已排序的顺序。
最终，当处理完最高位后，整个数组就是有序的。
4. Radix Sort 中的“位”定义
Radix Sort 的灵活性在于：“位”不一定是指单个数字。我们可以将整数拆分成多个连续的“块”（chunks），每个块包含多个数字。
例如，一个 10 位数可以拆成 5 个块，每个块两位：
x9 x8 | x7 x6 | x5 x4 | x3 x2 | x1 x0
如果整数用二进制表示，我们也可以按 bit 分组。例如，将 32 位整数拆成 4 个 8 位的“数字”，然后按这些数字排序。
在这种情况下，Radix Sort 的复杂度为：
Θ( (b/r) * (n + 2^r) )
其中：
b是整数的总位数r是每次处理的位数
为了最小化运行时间，我们需要选择合适的 r 值。通常选择 r = log₂n 可以取得最佳性能。
5. 从高位到低位排序（递归方式）
除了从低位到高位排序，我们也可以从高位开始排序，然后对相同高位的子数组递归排序。
伪代码如下：
algorithm RadixSortRecursion(a, i):
if i == 0:
return a
a = 按第 i 位使用 Counting Sort 排序
for 每个不同的第 i 位值 k:
a[k] = RadixSortRecursion(a[k], i - 1)
return a
⚠️ 缺点：Counting Sort 不是原地排序算法，每次递归都会产生新的数组副本。如果 d 较大，会导致 额外 O(dn) 的内存消耗。
✅ 适用场景：该方式适合小规模数据或内存不敏感的场景，但不适用于内存受限的系统。
6. 排序非整型数据
Radix Sort 不仅适用于整数，也可以扩展到字符串、日期等类型，只要我们能定义出“位”的概念。
例如：
- 字符串可以按字符顺序排序
- 日期可以按年、月、日分别排序
- IP 地址可按四段数字分别排序
⚠️ 限制：
- 每一位的取值范围不能太大（否则 Counting Sort 占用内存过高）
- 需要设计合理的“位”映射方式
- 如果某位取值范围极大（如百万级别），则 Counting Sort 效率极低
7. 总结
✅ Radix Sort 的优点：
- 时间复杂度为 O(n)，适合大规模整数排序
- 稳定排序，适合需要保持原顺序的数据
❌ 缺点：
- 不是原地排序，需要额外空间
- 仅适用于可以拆解为“位”的数据
- 对非整型数据支持有限，需要特殊处理
⚠️ 实践建议：
- 当数据量大且位数固定时，优先考虑 Radix Sort
- 如果内存受限，或数据类型复杂，建议使用 QuickSort 或 MergeSort
✅ 适用场景：
- 大数据处理
- 图像像素排序
- 数据库索引构建
- 网络日志按 IP 排序等
🔚 一句话总结：
Radix Sort 是一种基于数字位的线性排序算法，适用于整数或可结构化为“位”的数据，但需权衡内存和性能。