Hello 算法基数排序Radix Sort原理与 Python 完整实现详解【免费下载链接】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本文基于《Hello 算法》仓库中的基数排序 Python Tutor 逐步执行源码radix_sort.md与配套教程系统讲解基数排序的适用场景、算法流程、取位公式以及digit/counting_sort_digit/radix_sort三个核心函数的完整实现。读完后你能够独立写出基于逐位计数排序的基数排序理解为什么必须从最低位开始排、它的稳定性从何而来并掌握其时间与空间复杂度的分析方法和适用边界。适用场景为什么需要基数排序上一节的计数排序适用于数据量 $n$ 较大但数据范围 $m$ 较小的场景。但实际场景往往相反假设要对 $n 10^6$ 个学号排序而学号是 8 位数字数据范围 $m 10^8$ 非常大直接分配长度为 $m1$ 的计数桶会消耗大量内存计数排序不再可行。**基数排序radix sort**正是为此设计它的核心思想与计数排序一致同样通过统计个数实现排序区别在于它不直接对整数值统计而是利用数字各位之间的递进关系把一个大范围问题拆解为 $k$ 个单 digit 位0~9的小范围问题依次对每一位执行计数排序从而得到最终排序结果。这样桶的大小始终只需 $d 10$与数据范围无关。算法流程以学号数据为例假设数字的最低位是第 $1$ 位、最高位是第 $8$ 位基数排序的流程如下初始化位数 $k 1$对学号的第 $k$ 位执行一次计数排序。完成后数据会按第 $k$ 位从小到大排列将 $k$ 增加 $1$返回步骤 2 继续迭代直到最高位排序完成。提取第 k 位的数学公式对于一个 $d$ 进制数字 $x$要获取其第 $k$ 位 $x_k$计算公式为$$ x_k \lfloor\frac{x}{d^{k-1}}\rfloor \bmod d $$其中 $\lfloor a \rfloor$ 表示对 $a$ 向下取整$\bmod\ d$ 表示对 $d$ 取模。对十进制学号$d 10$$k \in [1, 8]$。实现上的一个关键优化函数参数传入 $exp d^{k-1}$ 而不是 $k$主循环中让 $exp$ 依次取 $1, 10, 100, \dots$每轮乘 $d$从而避免在每轮排序中对每个元素重复执行昂贵的次方运算。这一点在 Python 实现中体现为def digit(num: int, exp: int) - int: 获取元素 num 的第 k 位其中 exp 10^(k-1) # 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算 return (num // exp) % 10对应上面的公式//是整数向下取整% 10是模 $d$。例如num 356, exp 10即第 2 位(356 // 10) % 10 35 % 10 5正确取出十位上的 5。完整 Python 实现以下是 radix_sort.md 中用于 Python Tutor 逐步执行的完整源码该源码与 codes/python/chapter_sorting/radix_sort.py 的算法结构完全一致仅驱动数据不同def digit(num: int, exp: int) - int: 获取元素 num 的第 k 位其中 exp 10^(k-1) # 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算 return (num // exp) % 10 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] 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 Driver Code if __name__ __main__: # 基数排序 nums [105, 356, 428, 348, 818] radix_sort(nums) print(基数排序完成后 nums , nums)逐位计数排序counting_sort_digit 的四个阶段与标准计数排序相比这里只做了两处小幅改动桶长度固定为 $10$因为十进制 digit 只有 0~9以及待统计的值从整个元素换成了digit(nums[i], exp)取出的第 $k$ 位。其内部流程分为四个阶段阶段代码说明1. 计数counter[d] 1遍历一次数组统计 0~9 各 digit 在本轮中的出现次数2. 前缀和counter[i] counter[i - 1]将出现个数转换为尾索引即counter[d] - 1是 digit 为 $d$ 的元素在结果数组中最后一次应放的索引3. 倒序回填for i in range(n - 1, -1, -1)从后往前遍历把nums[i]放入res[counter[d] - 1]并令counter[d] - 1为下一个同 digit 元素腾位4. 覆盖原数组nums[i] res[i]用结果数组res原地覆盖nums下一轮更高一位排序直接在此基础上进行其中倒序回填正是稳定性的来源相同 digit 的元素原数组中靠后者先被放入更靠后的位置相对顺序得以保持。主流程radix_sort 的位数判定radix_sort的主循环用最大元素 $m \max(nums)$ 决定循环次数exp从 $1$ 起每轮乘 $10$直到 $exp m$ 为止。也就是说循环恰好执行 $\lceil \log_{10}(m1) \rceil$ 次——即最大元素有多少位就执行多少轮逐位排序。例如对驱动数据[105, 356, 428, 348, 818]最大元素 818 为 3 位数因此依次按个位exp1、十位exp10、百位exp100各做一轮计数排序输出为[105, 348, 356, 428, 818]。在仓库的 Python 正式实现 radix_sort.py 中主循环以while exp m形式实现驱动数据换成了 8 位学号[10546151, 35663510, 42865989, 34862445, 81883077, 88906420, 72429244, 30524779, 82060337, 63832996]正好对应教程中对 $10^6$ 量级大范围数据排序的动机Go 语言测试 radix_sort_test.go 也使用了同一组 8 位学号数据从源码结构看各语言版本共用同一组标准测试数据便于跨语言验证行为一致。为什么必须从最低位开始排序这是基数排序最容易被问到的问题。在连续的排序轮次中后一轮排序会覆盖前一轮的相对顺序若第一轮低位结果满足 $a b$而第二轮高位结果 $a b$那么最终顺序以第二轮为准。由于数字的高位权重天然高于低位百位不同十位个位就无所谓了所以必须先排低位、再排高位高位排序时高位相同或更小的元素组内部再被低位排序结果细排逐层叠加后高位顺序不会被低位推翻。反之若先排高位再排低位低位排序会把高位刚建立的顺序打乱得到错误结果。这也引出了一个重要结论当计数排序是稳定排序时基数排序才是正确且稳定的如果改用不稳定的单 digit 排序同一 digit 组内的前一轮相对顺序会被破坏最终无法保证正确结果。实现中的倒序遍历 前缀和尾索引正是保证每一轮计数排序稳定的关键细节。算法特性与复杂度相较于计数排序基数排序适用于数值范围较大的情况但前提是数据必须可以表示为固定位数的格式且位数 $k$ 不能过大。例如浮点数不适合直接使用基数排序因为其位数 $k$ 过大可能导致 $O(nk) \gg O(n^2)$反而劣于常规比较排序。时间复杂度 $O((n d)k)$非自适应排序设数据量为 $n$、数据为 $d$ 进制、最大位数为 $k$则对某一位执行计数排序需要遍历数组$O(n)$与前缀和/回填$O(d)$ 与 $O(n)$共 $O(n d)$排序全部 $k$ 位即 $O((nd)k)$。通常情况下 $d 10$ 和 $k$如 32 位整数的 10 位都相对较小且可视为常数时间复杂度趋向 $O(n)$这是它能突破比较排序 $O(n \log n)$ 下界的关键。非自适应指其耗时与输入是否已有序无关。空间复杂度 $O(n d)$非原地排序与计数排序相同需要长度为 $n$ 的结果数组res与长度为 $d$ 的桶数组counter本实现中即res [0] * n与counter [0] * 10。稳定排序由上述分析其稳定性继承自每一轮的计数排序counting_sort_digit中倒序遍历 前缀和的组合是稳定性的工程保障。多语言实现对照与运行验证同一算法在仓库中提供了十余种语言实现核心结构digit取位、按位计数排序、主循环按位推进完全一致可以互相印证。以 Java 版本 radix_sort.java 为例可以看到两个实现差异点取位函数用整除代替地板除(num / exp) % 10与 Python 的(num // exp) % 10等价正整数场景最大元素 $m$ 的求法Java 中手动遍历取最大值Python 直接用内置max(nums)主循环写法Java 用for (int exp 1; exp m; exp * 10)Python 用while exp mexp * 10语义相同。各语言版本的驱动/测试数据统一为同一组 8 位学号因此任何一份实现都可以作为其他语言的标准答案做输出比对。在仓库中查看这些实现的入口Python 可运行实现radix_sort.pyPython Tutor 逐步执行源码本文主体radix_sort.mdJava 实现radix_sort.javaGo 实现与测试radix_sort.go、radix_sort_test.go配套中文教程radix_sort.md直接运行 Python 版即可复现结果python codes/python/chapter_sorting/radix_sort.py # 输出基数排序完成后 nums [10546151, 30524779, 34862445, 35663510, # 42865989, 63832996, 72429244, 81883077, 82060337, 88906420]使用边界小结关注点结论适用数据非负整数等可表示为固定位数格式的数据位数 $k$ 应相对较小数据范围适合范围 $m$ 大如 $10^8$而 $n$ 也大的场景桶大小恒为 $d 10$时间复杂度$O((nd)k)$$d$、$k$ 较小时趋向 $O(n)$非自适应空间复杂度$O(n d)$需要额外的res与counter数组非原地稳定性稳定前提是每轮单 digit 排序稳定本实现由倒序遍历 前缀和保证不适用浮点数等位数过大的数据$k$ 过大时 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法：基数排序（Radix Sort）原理与 Python 完整实现详解
Hello 算法基数排序Radix Sort原理与 Python 完整实现详解【免费下载链接】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本文基于《Hello 算法》仓库中的基数排序 Python Tutor 逐步执行源码radix_sort.md与配套教程系统讲解基数排序的适用场景、算法流程、取位公式以及digit/counting_sort_digit/radix_sort三个核心函数的完整实现。读完后你能够独立写出基于逐位计数排序的基数排序理解为什么必须从最低位开始排、它的稳定性从何而来并掌握其时间与空间复杂度的分析方法和适用边界。适用场景为什么需要基数排序上一节的计数排序适用于数据量 $n$ 较大但数据范围 $m$ 较小的场景。但实际场景往往相反假设要对 $n 10^6$ 个学号排序而学号是 8 位数字数据范围 $m 10^8$ 非常大直接分配长度为 $m1$ 的计数桶会消耗大量内存计数排序不再可行。**基数排序radix sort**正是为此设计它的核心思想与计数排序一致同样通过统计个数实现排序区别在于它不直接对整数值统计而是利用数字各位之间的递进关系把一个大范围问题拆解为 $k$ 个单 digit 位0~9的小范围问题依次对每一位执行计数排序从而得到最终排序结果。这样桶的大小始终只需 $d 10$与数据范围无关。算法流程以学号数据为例假设数字的最低位是第 $1$ 位、最高位是第 $8$ 位基数排序的流程如下初始化位数 $k 1$对学号的第 $k$ 位执行一次计数排序。完成后数据会按第 $k$ 位从小到大排列将 $k$ 增加 $1$返回步骤 2 继续迭代直到最高位排序完成。提取第 k 位的数学公式对于一个 $d$ 进制数字 $x$要获取其第 $k$ 位 $x_k$计算公式为$$ x_k \lfloor\frac{x}{d^{k-1}}\rfloor \bmod d $$其中 $\lfloor a \rfloor$ 表示对 $a$ 向下取整$\bmod\ d$ 表示对 $d$ 取模。对十进制学号$d 10$$k \in [1, 8]$。实现上的一个关键优化函数参数传入 $exp d^{k-1}$ 而不是 $k$主循环中让 $exp$ 依次取 $1, 10, 100, \dots$每轮乘 $d$从而避免在每轮排序中对每个元素重复执行昂贵的次方运算。这一点在 Python 实现中体现为def digit(num: int, exp: int) - int: 获取元素 num 的第 k 位其中 exp 10^(k-1) # 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算 return (num // exp) % 10对应上面的公式//是整数向下取整% 10是模 $d$。例如num 356, exp 10即第 2 位(356 // 10) % 10 35 % 10 5正确取出十位上的 5。完整 Python 实现以下是 radix_sort.md 中用于 Python Tutor 逐步执行的完整源码该源码与 codes/python/chapter_sorting/radix_sort.py 的算法结构完全一致仅驱动数据不同def digit(num: int, exp: int) - int: 获取元素 num 的第 k 位其中 exp 10^(k-1) # 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算 return (num // exp) % 10 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] 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 Driver Code if __name__ __main__: # 基数排序 nums [105, 356, 428, 348, 818] radix_sort(nums) print(基数排序完成后 nums , nums)逐位计数排序counting_sort_digit 的四个阶段与标准计数排序相比这里只做了两处小幅改动桶长度固定为 $10$因为十进制 digit 只有 0~9以及待统计的值从整个元素换成了digit(nums[i], exp)取出的第 $k$ 位。其内部流程分为四个阶段阶段代码说明1. 计数counter[d] 1遍历一次数组统计 0~9 各 digit 在本轮中的出现次数2. 前缀和counter[i] counter[i - 1]将出现个数转换为尾索引即counter[d] - 1是 digit 为 $d$ 的元素在结果数组中最后一次应放的索引3. 倒序回填for i in range(n - 1, -1, -1)从后往前遍历把nums[i]放入res[counter[d] - 1]并令counter[d] - 1为下一个同 digit 元素腾位4. 覆盖原数组nums[i] res[i]用结果数组res原地覆盖nums下一轮更高一位排序直接在此基础上进行其中倒序回填正是稳定性的来源相同 digit 的元素原数组中靠后者先被放入更靠后的位置相对顺序得以保持。主流程radix_sort 的位数判定radix_sort的主循环用最大元素 $m \max(nums)$ 决定循环次数exp从 $1$ 起每轮乘 $10$直到 $exp m$ 为止。也就是说循环恰好执行 $\lceil \log_{10}(m1) \rceil$ 次——即最大元素有多少位就执行多少轮逐位排序。例如对驱动数据[105, 356, 428, 348, 818]最大元素 818 为 3 位数因此依次按个位exp1、十位exp10、百位exp100各做一轮计数排序输出为[105, 348, 356, 428, 818]。在仓库的 Python 正式实现 radix_sort.py 中主循环以while exp m形式实现驱动数据换成了 8 位学号[10546151, 35663510, 42865989, 34862445, 81883077, 88906420, 72429244, 30524779, 82060337, 63832996]正好对应教程中对 $10^6$ 量级大范围数据排序的动机Go 语言测试 radix_sort_test.go 也使用了同一组 8 位学号数据从源码结构看各语言版本共用同一组标准测试数据便于跨语言验证行为一致。为什么必须从最低位开始排序这是基数排序最容易被问到的问题。在连续的排序轮次中后一轮排序会覆盖前一轮的相对顺序若第一轮低位结果满足 $a b$而第二轮高位结果 $a b$那么最终顺序以第二轮为准。由于数字的高位权重天然高于低位百位不同十位个位就无所谓了所以必须先排低位、再排高位高位排序时高位相同或更小的元素组内部再被低位排序结果细排逐层叠加后高位顺序不会被低位推翻。反之若先排高位再排低位低位排序会把高位刚建立的顺序打乱得到错误结果。这也引出了一个重要结论当计数排序是稳定排序时基数排序才是正确且稳定的如果改用不稳定的单 digit 排序同一 digit 组内的前一轮相对顺序会被破坏最终无法保证正确结果。实现中的倒序遍历 前缀和尾索引正是保证每一轮计数排序稳定的关键细节。算法特性与复杂度相较于计数排序基数排序适用于数值范围较大的情况但前提是数据必须可以表示为固定位数的格式且位数 $k$ 不能过大。例如浮点数不适合直接使用基数排序因为其位数 $k$ 过大可能导致 $O(nk) \gg O(n^2)$反而劣于常规比较排序。时间复杂度 $O((n d)k)$非自适应排序设数据量为 $n$、数据为 $d$ 进制、最大位数为 $k$则对某一位执行计数排序需要遍历数组$O(n)$与前缀和/回填$O(d)$ 与 $O(n)$共 $O(n d)$排序全部 $k$ 位即 $O((nd)k)$。通常情况下 $d 10$ 和 $k$如 32 位整数的 10 位都相对较小且可视为常数时间复杂度趋向 $O(n)$这是它能突破比较排序 $O(n \log n)$ 下界的关键。非自适应指其耗时与输入是否已有序无关。空间复杂度 $O(n d)$非原地排序与计数排序相同需要长度为 $n$ 的结果数组res与长度为 $d$ 的桶数组counter本实现中即res [0] * n与counter [0] * 10。稳定排序由上述分析其稳定性继承自每一轮的计数排序counting_sort_digit中倒序遍历 前缀和的组合是稳定性的工程保障。多语言实现对照与运行验证同一算法在仓库中提供了十余种语言实现核心结构digit取位、按位计数排序、主循环按位推进完全一致可以互相印证。以 Java 版本 radix_sort.java 为例可以看到两个实现差异点取位函数用整除代替地板除(num / exp) % 10与 Python 的(num // exp) % 10等价正整数场景最大元素 $m$ 的求法Java 中手动遍历取最大值Python 直接用内置max(nums)主循环写法Java 用for (int exp 1; exp m; exp * 10)Python 用while exp mexp * 10语义相同。各语言版本的驱动/测试数据统一为同一组 8 位学号因此任何一份实现都可以作为其他语言的标准答案做输出比对。在仓库中查看这些实现的入口Python 可运行实现radix_sort.pyPython Tutor 逐步执行源码本文主体radix_sort.mdJava 实现radix_sort.javaGo 实现与测试radix_sort.go、radix_sort_test.go配套中文教程radix_sort.md直接运行 Python 版即可复现结果python codes/python/chapter_sorting/radix_sort.py # 输出基数排序完成后 nums [10546151, 30524779, 34862445, 35663510, # 42865989, 63832996, 72429244, 81883077, 82060337, 88906420]使用边界小结关注点结论适用数据非负整数等可表示为固定位数格式的数据位数 $k$ 应相对较小数据范围适合范围 $m$ 大如 $10^8$而 $n$ 也大的场景桶大小恒为 $d 10$时间复杂度$O((nd)k)$$d$、$k$ 较小时趋向 $O(n)$非自适应空间复杂度$O(n d)$需要额外的res与counter数组非原地稳定性稳定前提是每轮单 digit 排序稳定本实现由倒序遍历 前缀和保证不适用浮点数等位数过大的数据$k$ 过大时 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考