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

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

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

基数排序（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 位提取公式到完整可运行代码的全链路实现，适合作为学习"以空间换时间、以统计代比较"这一类非比较排序（计数排序、桶排序、基数排序）的收尾范例。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo