Hello 算法中的基数排序：按位执行计数排序，O(nk) 时间搞定大整数范围排序

基数排序（radix sort）是《Hello 算法》（hello-algo）排序章节中"非比较排序"的收官算法。本文基于仓库文档 radix_sort.md 及多语言源码实现展开，讲清基数排序如何把"学号范围高达 10^8"这类计数排序搞不定的场景，通过"逐位做计数排序"拆解为 k 轮 O(n+d) 的操作，最终在 O(nk) 时间内完成排序。读完后，你将掌握第 k 位的提取公式、"按位版"计数排序的完整代码流程、为什么必须从最低位开始排序的原因，以及基数排序的适用前提与边界。

从计数排序的局限说起：学号范围太大怎么办

在 counting_sort.md 一节中，计数排序需要创建一个长度为 m+1（m 为数据范围）的辅助数组 counter。它适用于数据量 n 较大但数据范围 m 较小的情况。

现在换一个场景：假设需要对 n = 10^6 个学号进行排序，而学号是一个 8 位数字，这意味着数据范围 m = 10^8 非常大——直接套用计数排序需要分配大量内存空间。

基数排序正是为解决这类问题而生。其核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位执行一次计数排序，从而得到最终的排序结果：既然每一位的取值范围只是 0~9，那么每轮计数排序都只需要长度为 10 的桶数组，整个数据范围 10^8 带来的内存压力就被彻底化解了。

算法流程：k 轮"按位计数排序"

以学号数据为例，假设数字的最低位是第 1 位，最高位是第 8 位，基数排序的流程如下：

1. 初始化位数 k = 1。
2. 对学号的第 k 位执行"计数排序"。完成后，数据会根据第 k 位从小到大排序。
3. 将 k 增加 1，然后返回步骤 2 继续迭代，直到所有位都排序完成后结束。

对 8 位学号来说，整个排序就是"个位 → 十位 → 百位 → … → 千万位"共 8 轮计数排序。仓库中各语言实现的 radix_sort 入口函数都遵循这一骨架：先求出数组最大元素 m 以推断最大位数，再以 exp = 1, 10, 100, ...（即 exp = 10^(k-1)）逐位推进。以 Python 实现 radix_sort.py 为例：

def radix_sort(nums: list[int]):
    """基数排序"""
    # 获取数组的最大元素，用于判断最大位数
    m = max(nums)
    # 按照从低位到高位的顺序遍历
    exp = 1
    while exp <= m:
        # 对数组元素的第 k 位执行计数排序
        # k = 1 -> exp = 1
        # k = 2 -> exp = 10
        # 即 exp = 10^(k-1)
        counting_sort_digit(nums, exp)
        exp *= 10

注意两个实现细节，它们在多语言版本中保持一致：

• 用 exp 而不是 k 作为循环变量：exp 直接就是 10^(k-1)，每轮乘以 10 即可推进到位数 k+1，避免反复执行次方计算；
• 最大位数由 max(nums) 动态决定，而非固定 8 位——即使数据只是三位数，算法也只跑 3 轮，不会浪费。

关键数学工具：如何提取数字的第 k 位

对于一个 d 进制的数字 x，要获取其第 k 位 x_k，可以使用以下计算公式：

$$x_k = \left\lfloor \frac{x}{d^{k-1}} \right\rfloor \bmod d$$

其中 floor(a) 表示对浮点数 a 向下取整，mod d 表示对 d 取模（取余）。对于十进制学号数据，d = 10 且 k ∈ [1, 8]。

翻译成代码就是一行取整除加取模。各语言实现中的 digit 函数完全同构，例如 Python 版（radix_sort.py）：

def digit(num: int, exp: int) -> int:
    """获取元素 num 的第 k 位，其中 exp = 10^(k-1)"""
    # 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
    return (num // exp) % 10

C 语言版 radix_sort.c、Java 版 radix_sort.java、C++ 版 radix_sort.cpp 中对应的 (num / exp) % 10 逻辑与之完全一致。这里用整数除法天然实现了公式中的向下取整。

代码剖析：改造计数排序，按第 k 位排序

接下来需要小幅改动计数排序代码，使之可以根据数字的第 k 位进行排序。以 Python 版 counting_sort_digit 为例，它把"按元素整体值计数"替换为"按元素第 k 位计数"（radix_sort.py）：

def counting_sort_digit(nums: list[int], exp: int):
    """计数排序（根据 nums 第 k 位排序）"""
    # 十进制的位范围为 0~9 ，因此需要长度为 10 的桶数组
    counter = [0] * 10
    n = len(nums)
    # 统计 0~9 各数字的出现次数
    for i in range(n):
        d = digit(nums[i], exp)  # 获取 nums[i] 第 k 位，记为 d
        counter[d] += 1  # 统计数字 d 的出现次数
    # 求前缀和，将"出现个数"转换为"数组索引"
    for i in range(1, 10):
        counter[i] += counter[i - 1]
    # 倒序遍历，根据桶内统计结果，将各元素填入 res
    res = [0] * n
    for i in range(n - 1, -1, -1):
        d = digit(nums[i], exp)
        j = counter[d] - 1  # 获取 d 在数组中的索引 j
        res[j] = nums[i]  # 将当前元素填入索引 j
        counter[d] -= 1  # 将 d 的数量减 1
    # 使用结果覆盖原数组 nums
    for i in range(n):
        nums[i] = res[i]

这段代码与标准计数排序（见 counting_sort.md）的差异只有两点：

• 桶数量固定为 10（d = 10），因为十进制每一位的取值只有 0~9，与数据总量、数据范围都无关；
• 计数对象从元素本身变为 digit(nums[i], exp)，即元素的第 k 位。

其余流程——统计频次、求前缀和把"出现个数"转换为"数组索引"、倒序遍历填充结果数组 res——原样保留。其中"倒序遍历 + 前缀和"这一步不只是工程习惯，它是稳定性的来源：相等元素（第 k 位相同的元素）之间不会改变相对顺序。C 语言版在 radix_sort.c 中额外体现了 malloc/free 成对出现的内存管理写法，逻辑流程完全相同。

为什么必须从最低位开始排序？

这是基数排序最容易被忽视、也最关键的性质。在连续的排序轮次中，后一轮排序会覆盖前一轮排序的结果。举例来说，如果第一轮排序结果 a < b，而第二轮排序结果 a > b，那么第二轮的结果将取代第一轮的结果。

由于数字的高位优先级高于低位（千位不同则个位多大都不影响整体大小），所以只有先排低位、再排高位，才能保证高位排序确立的顺序不被后续轮次破坏；若反过来从高位排起，低位轮次会把高位已排好的顺序打乱。

算法特性与适用前提

相较于计数排序，基数排序适用于数值范围较大的情况，但前提是数据必须可以表示为固定位数的格式，且位数不能过大。例如，浮点数不适合使用基数排序，因为其位数 k 过大，可能导致时间复杂度 O(nk) >> O(n^2)，反而不如比较排序。

• 时间复杂度为 O(nk)、非自适应排序：设数据量为 n、数据为 d 进制、最大位数为 k，则对某一位执行计数排序使用 O(n+d) 时间，排序所有 k 位使用 O((n+d)k) 时间。通常情况下，d 和 k 都相对较小（十进制下 d=10 是常数，k 为位数），时间复杂度趋向 O(n)。
• 空间复杂度为 O(n+d)、非原地排序：与计数排序相同，基数排序需要借助长度为 n 和 d 的数组 res 和 counter。在源码中可以直接对应：counter = [0] * 10（长度 d）与 res = [0] * n（长度 n）。
• 稳定排序：当计数排序稳定时，基数排序也稳定；当计数排序不稳定时，基数排序无法保证得到正确的排序结果——因为整个算法的正确性建立在"后一轮稳定地覆盖前一轮"之上，一旦某一轮破坏了相等元素的相对顺序，之前轮次的成果就会被错误覆盖。

多语言实现与测试验证

该算法在仓库 codes/ 下以统一示例数据（10 个 8 位整数）提供了各语言版本，可直接运行查看效果：

• radix_sort.py：Python 版，radix_sort(nums) 原地排序；
• radix_sort.java：Java 版，radixSort(int[] nums)，最大位数用手动遍历求 Integer.MIN_VALUE 起点的最大值实现；
• radix_sort.cpp：C++ 版，借助 std::max_element 求最大元素；
• radix_sort.c：C 版，注意 counter、res 通过 malloc 分配并在函数末尾 free 释放；
• radix_sort.go 及其测试 radix_sort_test.go：Go 版提供了 TestRadixSort 单元测试，运行 go test 即可验证对示例数组的排序结果。

从源码结构看，各语言版本在"位数推进方式"上略有差异：Python 用 while exp <= m，Java 用 for (int exp = 1; exp <= m; exp *= 10)，C 版则写成 for (int exp = 1; max >= exp; exp *= 10)——三者语义等价，均为"exp 从 1 起每次乘 10，直到超出最大元素为止"，轮数恰好等于最大元素的位数。

小结

基数排序把"排序大范围的整数"这一难题，转化为 k 轮"排序 0~9 的小范围整数"，每轮复用稳定的计数排序，从而在数据可表示为固定位数（且位数不过大）的前提下，用 O(nk) 时间与 O(n+d) 空间完成非比较排序。仓库文档 radix_sort.md 与多语言源码（Python/Java/C/C++/Go）给出了从第 k 位提取公式到完整可运行代码的全链路实现，适合作为学习"以空间换时间、以统计代比较"这一类非比较排序（计数排序、桶排序、基数排序）的收尾范例。