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(nd) 的操作最终在 O(nk) 时间内完成排序。读完后你将掌握第 k 位的提取公式、按位版计数排序的完整代码流程、为什么必须从最低位开始排序的原因以及基数排序的适用前提与边界。从计数排序的局限说起学号范围太大怎么办在 counting_sort.md 一节中计数排序需要创建一个长度为m1m 为数据范围的辅助数组counter。它适用于数据量 n 较大但数据范围 m 较小的情况。现在换一个场景假设需要对n 10^6个学号进行排序而学号是一个 8 位数字这意味着数据范围m 10^8非常大——直接套用计数排序需要分配大量内存空间。基数排序正是为解决这类问题而生。其核心思想与计数排序一致也通过统计个数来实现排序。在此基础上基数排序利用数字各位之间的递进关系依次对每一位执行一次计数排序从而得到最终的排序结果既然每一位的取值范围只是 0~9那么每轮计数排序都只需要长度为 10 的桶数组整个数据范围10^8带来的内存压力就被彻底化解了。算法流程k 轮按位计数排序以学号数据为例假设数字的最低位是第 1 位最高位是第 8 位基数排序的流程如下初始化位数k 1。对学号的第k位执行计数排序。完成后数据会根据第k位从小到大排序。将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 即可推进到位数 k1避免反复执行次方计算最大位数由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.pydef digit(num: int, exp: int) - int: 获取元素 num 的第 k 位其中 exp 10^(k-1) # 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算 return (num // exp) % 10C 语言版 radix_sort.c、Java 版 radix_sort.java、C 版 radix_sort.cpp 中对应的(num / exp) % 10逻辑与之完全一致。这里用整数除法天然实现了公式中的向下取整。代码剖析改造计数排序按第 k 位排序接下来需要小幅改动计数排序代码使之可以根据数字的第k位进行排序。以 Python 版counting_sort_digit为例它把按元素整体值计数替换为按元素第 k 位计数radix_sort.pydef 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的差异只有两点桶数量固定为 10d 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(nd) 时间排序所有 k 位使用 O((nd)k) 时间。通常情况下d 和 k 都相对较小十进制下 d10 是常数k 为位数时间复杂度趋向 O(n)。空间复杂度为 O(nd)、非原地排序与计数排序相同基数排序需要借助长度为 n 和 d 的数组res和counter。在源码中可以直接对应counter [0] * 10长度 d与res [0] * n长度 n。稳定排序当计数排序稳定时基数排序也稳定当计数排序不稳定时基数排序无法保证得到正确的排序结果——因为整个算法的正确性建立在后一轮稳定地覆盖前一轮之上一旦某一轮破坏了相等元素的相对顺序之前轮次的成果就会被错误覆盖。多语言实现与测试验证该算法在仓库codes/下以统一示例数据10 个 8 位整数提供了各语言版本可直接运行查看效果radix_sort.pyPython 版radix_sort(nums)原地排序radix_sort.javaJava 版radixSort(int[] nums)最大位数用手动遍历求Integer.MIN_VALUE起点的最大值实现radix_sort.cppC 版借助std::max_element求最大元素radix_sort.cC 版注意counter、res通过malloc分配并在函数末尾free释放radix_sort.go 及其测试 radix_sort_test.goGo 版提供了TestRadixSort单元测试运行go test即可验证对示例数组的排序结果。从源码结构看各语言版本在位数推进方式上略有差异Python 用while exp mJava 用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(nd) 空间完成非比较排序。仓库文档 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考