1. 基数排序是怎么一回事如果你刷过排序算法大概率会觉得“快排、归并、堆排”已经够用了为什么还要专门搞一个基数排序我第一次接触它时也是这种想法。后来遇到一批固定位数的整数排序数据量几百万级快排虽然也还行但基数排序那种“用空间换轮次、避开比较”的思路确实眼前一亮。更重要的是它背后“稳定排序 桶分配”的组合思想在很多实战场景里都藏得很深比如数据库的排序实现、后缀数组的构建甚至在某些高性能计算库里都能看到影子。基数排序属于典型的非比较排序它不靠两两元素之间比大小来决定顺序而是按“位”来处理。你可以把它理解成整理一副扑克牌先按花色分成四堆再在每个花色里按点数排好或者反过来先按点数分成十三堆再按花色排。无论哪种顺序只要每轮分组是稳定的最终都能得到有序结果。1.1 比较排序与非比较排序的本质区别常规排序算法比如快速排序、归并排序核心操作是比较两个元素的大小单次比较的时间复杂度是 O(1)所以总复杂度下界是 O(n log n)。这里有一个信息论的解释n 个元素的排列有 n! 种可能每次比较只能得到“大于/小于/等于”三种结果因此需要至少 log2(n!) 次比较约等于 n log2 n。基数排序绕开了比较。它假设待排序的数据可以拆分成若干个“位”每一位的取值是有限集合。比如十进制整数每一位只有 0~9 十种情况那么就可以准备 10 个桶。每一轮按某一位把元素放进对应桶里再按桶的顺序收集回来。整个过程没有比较只有“分配”和“收集”所以时间复杂度可以直接写成 O(k·n)其中 k 是位数或者说轮数。1.2 LSD 与 MSD两种完全不同的拆解路径基数排序有两条路线从最低有效位开始排的叫 LSDLeast Significant Digit从最高有效位开始的叫 MSDMost Significant Digit。LSD 的实现符合直觉先按个位排序再按十位排序依此类推。它的优势是每轮都用稳定排序最终结果自然全局有序不需要递归逻辑非常线性。MSD 则复杂一些先按最高位分桶高位相同的元素会落到同一个桶里然后对每个桶递归地按次高位分桶。它适合处理字符串排序尤其是可变长字符串因为可以先比较首字母首字母不同的单词根本不需要看后续字符能省掉大量浪费。实际工程里LSD 更常见实现也简单。Python 里手写基数排序我基本都推荐从 LSD 入手。1.3 时间复杂度与空间复杂度别被 O(nk) 骗了很多人背过“基数排序时间复杂度 O(nk)”但这里的 k 不是常数它取决于数据的范围和进制选择。比如排序范围是 0 到 99999 的整数十进制需要 5 轮二进制需要 17 轮。轮数 k log_r(max_value)r 是基数大小。所以时间复杂度更严谨地说是 O(n · log_r(max))。空间复杂度方面每轮需要额外的桶空间。如果用链表桶需要 O(n) 存储元素本身加上桶头部指针总空间 O(n r)。如果用计数排序来实现稳定桶还需要两个辅助数组一个计频次一个定位元素输出位置总空间同样是 O(n r)。r 通常远小于 n可以粗略认为空间 O(n)。需要注意当 max 非常大时比如排序 64 位整数用二进制要排 64 轮每轮都要重新分配和收集整体效率不一定比优化过的快排强。所以基数排序不是银弹它适合“值域有限、位数有限”的场景。2. 稳定排序在基数排序中的重要性我一直觉得理解“为什么基数排序要求稳定排序”比写代码本身更重要。这个问题也是面试官最爱挖的坑。先做一个简单实验假设有一组两位数 [23, 21, 31] 按个位排得到序列 [21, 31, 23]。注意21 和 31 个位都是 1它们的相对顺序是原先 [21, 31] 中的顺序。如果这里桶收集时不保持稳定比如桶内用了不稳定排序那么十位排序时原本靠前的 21 可能跑到 31 后面最终结果就错了。换句话说LSD 的每一轮实际上是在前面低位已经有序的前提下对当前位做“改进”。如果不能保持前一轮的相对顺序那么低位信息在更高位排序时就会丢失整个排序逻辑就崩塌了。2.1 用计数排序实现稳定桶实现稳定桶最简单有效的方法是计数排序。Python 里可以用一个长度等于基数通常是 10的 count 数组先统计当前位每个数字出现的次数再算前缀和这个前缀和直接决定了每个元素在输出数组中的目标位置。只要从后往前遍历原始数组就能保证相同数字的元素按照原始顺序进入输出数组从而保持稳定性。为什么不直接用列表当桶理论上当然可以遍历元素按当前位 append 到对应的子列表再依次拼接。这种方法写起来直观但 Python 里频繁创建子列表、拼接列表的开销非常大而且每轮都要新建 10 个空列表内存碎片化严重。计数排序方式使用预先分配的数组一次遍历两次循环搞定性能和稳定性都更好。2.2 获取指定位的经典方法拿到一个整数 xx怎么取其第 k 位如果从最低位开始第 0 位是个位第 1 位是十位通用公式是digit (x // (base ** k)) % base不过每次算 base 的幂开销不小。工程上更常见的做法是每轮维护一个 divisor初值为 1每轮结束后乘以 base然后通过(x // divisor) % base获取当前位。这样避免了重复计算幂。还有一个小技巧如果你知道数据范围不超过某个值可以直接用位运算比如按 2 进制分组时(x shift) mask比取模快得多。在 Python 里整数除法加取模其实不慢但如果你追求极致性能可以考虑用位掩码方式。2.3 负数的处理一个必须提前想清楚的坑很多网上的基础版实现根本不处理负数。如果你直接拿负数套公式(-123) % 10在 Python 里结果是 7 而不是 3因为 Python 的取模运算遵循“结果符号与除数相同”的规则。这会导致排序完全错乱。处理负数有几种方案分离正负数分别排序再合并。负数部分可以取绝对值后加一个偏移量或者专门按符号位处理。全体加偏移量。先找到最小值把所有数加上-min_value转成非负数排完再减回来。代价是多一轮遍历但逻辑最简单。按补码思想处理。二进制位运算下负数参与移位和掩码也能得到正确结果但涉及 Python 整数无限精度的问题处理起来有点绕。我常用方案二因为它通用性强不依赖进制。具体操作是第一遍遍历找最小值第二遍遍历生成新数组num offset排序后再把 offset 减掉。注意这一步会在“数值大小相等”时保持稳定性吗其实影响不大因为所有元素加了同一个常数相对大小完全不变。2.4 基数选择10 进制是最优解吗很多人默认十进制因为生活中最熟悉。但在计算机里二进制或十六进制往往更快。假设数据范围是 0 到 10 万十进制需要 5 轮二进制需要 17 轮十六进制只需要 4 轮因为 10 万小于 0xFFFF但 4 位十六进制能表示到 65535不够得用 5 轮。所以十六进制在轮数上并不占优。更实际的选择是 256 进制也就是按字节排序。一个 32 位整数拆成 4 个字节只排 4 轮。每轮基数 r256计数数组长度 256也很小。Python 中可以通过x 0xFF、(x 8) 0xFF这类位运算取字节速度极快。如果目标平台内存很紧张用链表桶方式、基数取 10 也许能省内存但 Python 本身就不是省内存的语言不如干脆用数组。2.5 字符串能不能用基数排序可以而且很合适。字符串本质上可以看作一个字符序列每个字符都有对应的 Unicode 码点基数可以取 256 或更大。但需要注意长度不一致的情况短字符串需要补一种排在所有字符之前的“空字符”。LSD 对字符串排序时需要先统一长度从最后一个有效字符往前排。这里有一个麻烦如果某条字符串长度不足它在对应位应视为“最小”但直接取码点会造成越界。常见的做法是把字符串逆序后按字符码点排序或者在每轮判断索引是否越界越界按 -1 处理。MSD 处理变长字符串其实更自然但从工程角度看如果只是普通需求Python 内置的sorted已经优化得很好了手写基数排序来排字符串更多是面试和学习用途。3. Python 实现从零开始写一个可用的 LSD 基数排序有了前面原理铺垫代码写起来就顺畅了。我先给一个最基础、适用于非负整数的版本然后逐步加强。所有代码基于 Python 3.8。3.1 基础版非负整数排序def radix_sort_base(nums): if not nums: return nums max_num max(nums) base 10 divisor 1 while max_num // divisor 0: # 计数数组存储 0~base-1 每个数字出现次数 count [0] * base for x in nums: digit (x // divisor) % base count[digit] 1 # 前缀和转换为每个数字最后一个位置1 for i in range(1, base): count[i] count[i - 1] # 从后往前遍历保持稳定性 output [0] * len(nums) for x in reversed(nums): digit (x // divisor) % base count[digit] - 1 output[count[digit]] x nums output divisor * base return nums注意这里reversed(nums)不是颠倒原列表而是返回反向迭代器不会创建新列表空间性能友好。如果你用的是普通列表遍历再手动倒序也能达到同样效果但会多一次 O(n) 的复制。3.2 支持负数的通用版本在基础版上加入偏移量处理。我们先找到最小值如果最小值小于 0就把所有元素加上-min_value。排序完成后还需要再把偏移减回去。为了保证函数返回值与输入列表相互独立我建议生成新列表而不是原地修改。def radix_sort_with_negative(nums): if not nums: return nums min_val min(nums) if min_val 0: offset -min_val arr [x offset for x in nums] else: offset 0 arr list(nums) max_val max(arr) base 10 divisor 1 while max_val // divisor 0: count [0] * base for x in arr: digit (x // divisor) % base count[digit] 1 for i in range(1, base): count[i] count[i - 1] output [0] * len(arr) for x in reversed(arr): digit (x // divisor) % base count[digit] - 1 output[count[digit]] x arr output divisor * base if offset: return [x - offset for x in arr] return arr这个版本能覆盖绝大多数整数排序需求包括全负数、正负混合、重复值等情况。3.3 按字节优化的版本如果你排序的整数都是 Python int并且范围不大但数量很大我们可以用字节位运算来做。假设只考虑非负 32 位整数基数取 256需要 4 轮。def radix_sort_byte(nums): if not nums: return nums arr list(nums) # 先处理非负情况负数后面再讨论 for shift in (0, 8, 16, 24): count [0] * 256 for x in arr: byte (x shift) 0xFF count[byte] 1 for i in range(1, 256): count[i] count[i - 1] output [0] * len(arr) for x in reversed(arr): byte (x shift) 0xFF count[byte] - 1 output[count[byte]] x arr output return arr这里 shift 从 0 开始每次加 84 轮之后 32 位整数全部处理完。如果数据范围只用得到低两个字节可以只跑两轮提前结束。注意这个版本不能直接处理负数。如果输入包含负数需要先加偏移量或者采用符号位调整。在 Python 中负数的右移是带符号的(-1 8) 0xFF不会得到你期望的 255而是因为 Python 整型无限长得到 0xFFFFFFFF。所以更稳妥的方案还是偏移量法。3.4 正确性测试与随机验证写完排序函数务必要用随机数据验证。我通常会写一个小测试脚本对比sorted()的结果import random def test_radix_sort(sort_func, n10000, max_abs100000, trials20): for _ in range(trials): data [random.randint(-max_abs, max_abs) for _ in range(n)] expected sorted(data) got sort_func(data) if got ! expected: print(Error on trial, _) print(data[:20]) print(got[:20]) print(expected[:20]) return False return True print(test_radix_sort(radix_sort_with_negative))这个测试代码能快速排除绝大多数实现错误。我第一次写基数排序时就是栽在负数取模上后来加了偏移量才通过。3.5 性能对比基数排序 vs Python 内置排序很多初学者会好奇手写基数排序能不能打得过sorted()。直接说结论在 Python 中纯手写基数排序在大多数情况下都打不过内置的 Timsort。Timsort 是 Python 排序的底层算法它结合了归并排序和插入排序针对现实数据做了大量优化而且在 C 语言层实现常数极小。基数排序虽然在渐进时间复杂度上看着更好但 Python 层的循环开销、数组分配开销会吃掉优势。我做过一个小实验随机生成 100 万个 0 到 10 万的整数内置sorted()大约耗时 0.2 秒我的十进制基数排序版本大约耗时 0.6 秒。换成按字节优化的版本能降到 0.4 秒左右但仍然比不上内置。那基数排序是不是没用不是。它在某些特定场景下有意义比如硬件层面实现、C/C 里处理固定宽度数据、GPU 并行计算或者需要对大规模整数做稳定排序且位数固定时。在 Python 里学习基数排序的意义更多在于理解算法思想以及应对面试中的手写代码题。3.6 一个优化思路提前终止轮次如果你的数据最大值的位数很小可以提前结束。比如最大数是 999十进制只需 3 轮。基础版用while max_num // divisor 0已经实现了这一点。但注意如果数据包含负数偏移之后的最大值位数变大了怎么办比如原数据范围是 [-100000, 100000]加上偏移后变成 [0, 200000]位数反而增加一轮。这是一种取舍可以用按字节版本减轮数但负数的存在确实让基数排序在 Python 里稍显笨拙。4. 实际应用场景与避坑经验总结4.1 哪些场景值得用基数排序在 C/C 或者底层开发中基数排序常见的应用包括大规模整数排序内存中几十亿个 64 位整数按位排序比快排更容易做数据局部性优化容易向量化。GPU 并行排序基数排序天然适合并行因为每轮的分桶可以分成“统计频次”和“全局定位”两个阶段很适合 SIMD 或 SIMT 架构。数据库索引构建有些数据库在长整数键排序时会使用基数排序的思想尤其是排序键是复合码多个字段拼接成一个大整数的情况。文本处理和后缀数组构建后缀数组时对字符串后缀按字典序排序常用倍增 基数排序来优化复杂度。如果你在 Python 业务代码里想排序整数建议直接用sorted(),除非你正在学习或面试否则手写基数排序没有实际收益。这一点必须坦白讲清楚避免读者掉进“自己造轮子”的坑。4.2 踩坑记录内存与可变对象问题基数排序的输入类型最好是普通整数或固定长度字符串避免传递可变对象。如果元素是自定义对象按某个字段排序输出时需要把整个对象一起移动稳定性依然保持但内存使用双倍。如果对象很大内存开销可能很吓人。另外不要试图修改输入列表再返回它否则很容易出现 bug。我通常返回一个新列表让原列表保持不变这样更容易测试和调试。4.3 面试中常见的追问面试官问“请实现基数排序”时通常还会追加几个问题为什么要从最低位开始答LSD 每轮借用稳定排序不需要递归简单直接MSD 需要递归分桶。基数排序是稳定的吗答取决于每轮桶内排序是否稳定。用计数排序实现时天然稳定。如何处理负数答偏移量方案或者正负数分开排。时间复杂度的 k 怎么理解答k 是位数与数据范围和基数有关不是常数。为什么基数排序不能替代快排答需要额外的空间并且对数据类型有限制。面试手写时我推荐写最精简的非负整数版本然后在注释里说明负数处理方案。不要一上来写几百行复杂版本面试官主要看思路。4.4 与计数排序、桶排序的关系基数排序可以看作是迭代执行“计数排序”的过程。计数排序适合值域小的情况比如成绩 0~100直接开一个 101 大小的数组记录频次再展开。但如果值域达到 1e9计数排序就废了。基数排序把大值域拆成多个小块每块用一次计数排序用轮次换取可控的空间。桶排序则是把数据均匀分布到若干桶里然后对每个桶单独排序如果数据分布不均匀复杂度会退化。基数排序的桶是“按位强制分配的”不管数据分布如何每轮桶大小总和都为 n不存在某个桶过大的问题只要不是所有元素同一位相同但这种情况下一轮只是保持原序不会退化到 O(n²)。4.5 常见错误速查表错误现象原因解决办法负数排序结果错乱Python 取模规则导致负数取余异常整体平移偏移量到非负区间结果不稳定收集时从前向后遍历导致相同数字顺序反转必须从后往前遍历原数组内存爆炸直接对每个数字创建桶列表使用计数数组一次定位结果包含前导零干扰字符串或进制处理不规范补最小占位符或严格按位截取排序速度比sorted()慢Python 层循环开销大放弃手写使用内置排序或改用位运算优化5. 扩展思路从 LSD 到 MSD 再到并行如果你已经理解了 LSD 实现可以进一步拓展自己的知识边界。5.1 MSD 递归实现的基本框架MSD 按最高位分桶后递归处理每个桶。伪代码如下def msd_sort(arr, digit): if len(arr) 1 or digit 0: return arr buckets [[] for _ in range(base)] for x in arr: d (x // (base ** digit)) % base buckets[d].append(x) result [] for bucket in buckets: if len(bucket) 1: result.extend(msd_sort(bucket, digit - 1)) else: result.extend(bucket) return result这个版本比 LSD 更容易实现字符串排序但递归深度和数据相关。最坏情况所有元素高位都相同递归深度就是位数可能超过 Python 默认递归限制需要手工处理。5.2 并行化统计频次阶段可以拆开在大数据处理中基数排序非常适合分块并行。第一遍把数据拆分到多个 worker各自统计每个 bucket 的频次然后汇总计算每个 bucket 的全局偏移第二遍把数据重新映射到正确位置。这种两阶段“各统计各的 汇集写入”的模式非常类似 MapReduce。Python 里用 multiprocessing 做这种并行会损失一部分性能但思想上值得了解。如果你用 Cython 或 Numba 实现加快循环速度后基数排序的威力才能真正体现出来。5.3 外部排序场景如果需要排序的数据量超过内存基数排序可以结合分块处理。假设你有 10 亿个整数完全放不进内存可以先读入若干固定大小的块对每块按基数排序后写到临时文件最后做多路归并。虽然基数排序本身不是外部排序算法但它可以作为一种每块内部的快速排序方案。这里要注意外部归并阶段需要稳定合并如果各个块内部有序归并时只需比较当前块的最小元素即可。如果多个块的最小元素相等需要维护稳定性不过大多数场合下这不是硬性要求。6. 写在最后我在实际测试中的体会对基数排序我个人的体会是不要只在教科书里理解它一定要亲手写一遍、测一遍、踩一遍坑。第一次写出来被负数搞挂、被稳定性搞错这些都是宝贵的记忆比看十遍原理都深刻。Python 里做实验很合适因为代码量小、调试直观你可以在五分种内验证自己对稳定排序的理解。如果你真的想在 Python 里追求排序性能老老实实用内置sorted()。但如果你要深入理解底层排序、后续准备学习 C/C 或 GPU 算法那么基数排序是一个绕不开的经典案例。从十进制基础版到按字节优化版再到 MSD 递归版每往前一步你对“数据如何移动”的认知都会更透彻。最后再分享一个小技巧调试基数排序时我习惯打印每一轮“分配前”和“收集后”的数组在数据量不超过 20 个时非常直观。不要只依赖最终正确性验证过程可视化能让你快速定位是哪一轮出错节省大量排查时间。