如果你已经习惯了快速排序和各种比较排序第一次看到基数排序Radix sort时往往会觉得它不像排序从头到尾没有一次“比较”只靠按位分桶和收集就能把一堆整数排得明明白白。这篇就是专门聊聊基数排序的核心思路、完整实现、工程改造和选型心得。它适合三类人看一是面试前想搞懂非比较排序的学生二是需要用大量定长整数做排序的工程师三是单纯想拓展排序算法视野的开发者。很多人被“基数排序是线性复杂度”这句话吸引却忽略了它适用的前提。基数排序本质上是把排序拆成多轮“按位计数”每一轮都只关注某一位上的数字。因为位数有限单轮复杂度是 O(n)总轮数由数据的最大位数决定所以它可以在合适条件下突破 O(n log n) 的下界。但突破有代价需要额外内存、要求键值能拆成固定或可处理的“位”还得保证每轮排序稳定。这几条一个都不能少少了就容易写出正确但极其慢的版本。1. 基数排序是怎么来的排序世界观里的“非主流”1.1 比较排序的天花板为什么快排无法做到 O(n)先说说基数排序存在的意义。所有基于“两个元素比大小”的排序算法都存在一个理论下界平均情况和最坏情况至少是 O(n log n)。原因很直观如果你只靠比较每次比较最多产生一个大小关系而一个数组的正确排列有 n! 种可能性你需要至少 log₂(n!) 次比较才能区分所有可能。log₂(n!) 近似等于 n log₂ n这就是比较排序的天花板。快速排序、归并排序、堆排序全都在这个框架里。它们的差距只在常数因子和工程细节。快排之所以在工程里几乎无敌是因为比较和交换的局部性好、缓存命中率高而且对于随机数据表现极稳。但不管怎么优化它都无法在理论上变成线性复杂度。要打破这个局限就得跳出“比大小”的框架。基数排序就是典型的代表我不需要知道 170 和 45 谁大谁小我只需要知道 170 的个位是 045 的个位是 5第二轮再看十位第三轮看百位。信息不靠两两比较获取而是靠“按位分类”获取。1.2 基数排序的核心思路不比较直接归类你可以把基数排序想象成图书馆整理书籍书脊上都贴着分类号先按第一位数字粗分再按第二位细分最后按第三位精确到架位。整理的人根本不比较两本书的书名谁大谁小只看号码当前位是多少就丢进对应的格子里。整数排序也一样。我把每个数字从低位到高位拆开每一轮只处理一位具体动作是三个步骤统计当前位上每个数字0 到 9出现的次数。根据统计结果算出每个数字在下一轮输出数组中的起始位置。按顺序把元素放进临时数组收集起来。这里有一个关键概念基数radix。十进制数字每一位的范围是 0 到 9所以基数是 10。如果改成二进制位每一位只有 0 和 1基数是 2。如果一次处理 8 个二进制位那一轮的取值范围就是 0 到 255基数是 256。基数越大总轮数越少但每一轮需要的桶数组也越大这是一个典型的空间换时间问题。1.3 LSD和MSD两条路线先排低位还是先排高位基数排序有两条路线LSDLeast Significant Digit从最低位开始排MSDMost Significant Digit从最高位开始排。LSD 的思路最反直觉先看个位再看十位最后看百位。个位排完时数组并不是有序的只是“个位有序”十位排完后数组变成“十位优先个位在次位也保持有序”等到最高位处理完所有高位的相对顺序就主导了最终结果。这个过程能成立依赖的是稳定排序低位的次序不会在后续处理中被破坏。MSD 则是从最高位开始先按最高位分桶然后每个桶内递归处理下一位。它更符合人类直觉也更适合字符串排序但缺点是需要递归、可能碰到空桶导致递归深度和分桶数量不稳定。工程上实现 LSD 比 MSD 简单得多所以下面从 LSD 入手。2. 手写一个LSD基数排序完整实操2.1 为什么选LSD而不是MSD入门LSD 最好写也最好调试。每一步只需要对当前位做一次“稳定计数排序”不需要递归不需要处理桶内再分桶的复杂逻辑。MSD 看起来漂亮实际写一遍就会撞上各种边界条件和递归层级问题比如处理完高位桶后怎么保证桶内的低位顺序不丢、怎么处理空桶、怎么避免递归过深。新手入门我强烈建议先把 LSD 吃透。另外LSD 天然适合整数的按位拆分也适合后面讲到的二进制基数排序。理解了 LSD 的稳定排序思想再回去看 MSD 会容易得多。2.2 第一步先确定最大位数实现 LSD 之前先要知道总共要跑多少轮。用最大值的位数决定轮数这是最常见也最省事的做法。def get_max_digits(arr): if not arr: return 0 max_val max(arr) digits 0 while max_val 0: max_val // 10 digits 1 return digits if digits 0 else 1 # 处理全为0的情况注意如果数组里全是 0max 是 0循环一次都不会进digits 会变成 0。后续排序循环就一次也不执行结果看似没问题但如果函数依赖轮数来初始化临时数组就会出现意外。所以这里显式返回 1保证至少处理一轮。2.3 第二步按位分配保持稳定大多数教程会直接把“桶”实现成列表的列表每一轮创建 10 个空列表然后往里 append。这个写法最容易理解但不是最优实现。每轮大量创建列表、销毁列表不仅慢而且会产生很多内存碎片。更推荐的做法是“计数数组 前缀和 临时数组”本质上就是调用一次稳定的计数排序。为什么要保持稳定LSD 的灵魂就在这里。假设上一轮我们完成了“个位排序”现在处理十位。如果十位相同的元素在计数排序过程中可以保持原来的顺序那它们在最终数组里就会继续保持“个位有序”的相对关系。最后处理百位时百位相同的一组元素内部仍然是“十位优先、个位其次”的有序状态。只要每一轮都稳定低位信息就会一层层传递上来。稳定排序的实现有一个很经典的细节统计完每个数字的出现次数后计算前缀和作为“每个数字的起始插入位置”然后从原数组的尾部开始往前遍历逐个把元素放到正确的位置。这里一定要从后往前遍历否则相同数字的内部顺序会被反转。2.4 完整代码与输出验证下面是一个可以直接跑的 Python 版本def radix_sort(arr): if not arr: return arr max_val max(arr) exp 1 # 当前处理的位权1、10、100... while max_val // exp 0: # 当最高位仍存在时继续 n len(arr) output [0] * n count [0] * 10 # 1. 统计当前位上每个数字的出现次数 for num in arr: digit (num // exp) % 10 count[digit] 1 # 2. 计算前缀和count[i] 表示数字 i 最后一次出现的存放位置 for i in range(1, 10): count[i] count[i - 1] # 3. 从后往前遍历保持稳定性 for num in reversed(arr): digit (num // exp) % 10 count[digit] - 1 output[count[digit]] num arr output exp * 10 return arr用经典测试数据[170, 45, 75, 90, 2, 24, 802, 66]跑一遍手动验算第一轮个位个位分别为0、5、5、0、2、4、2、6计数数组count[0]2, count[2]2, count[4]1, count[5]2, count[6]1前缀和后count[0]2, count[2]4, count[4]5, count[5]7, count[6]8逆序遍历原数组66 (digit 6): count[6] 减 1 变 7放到 output[7]802 (digit 2): count[2] 减 1 变 3放到 output[3]24 (digit 4): count[4] 减 1 变 4放到 output[4]2 (digit 2): count[2] 减 1 变 2放到 output[2]90 (digit 0): count[0] 减 1 变 1放到 output[1]75 (digit 5): count[5] 减 1 变 6放到 output[6]45 (digit 5): count[5] 减 1 变 5放到 output[5]170 (digit 0): count[0] 减 1 变 0放到 output[0]第一轮结果[170, 90, 2, 802, 24, 45, 75, 66]。注意这里 45 和 75 的先后顺序因为是逆序放置后出现的 75 先被放到了较大的索引先出现的 45 后面又被放到了较小索引所以它们保持了原数组中的相对顺序。第二、三轮跑完后得到[2, 24, 45, 66, 75, 90, 170, 802]这就是最终结果。2.5 复杂度拆解设数据量是 n最大位数是 d基数十进制下是 10是 k。每一轮内部就是一次计数排序复杂度 O(n k)。总共 d 轮所以整体复杂度是 O(d(n k))。这个公式很关键。如果 d 是常数比如 32 位整数按 8 位一组处理d 只有 4那么复杂度就是 O(4n)等价于线性。如果 d 会随着 n 增长比如你排序几万个大整数每个数有几万位那么 d 可能远大于 log n这种情况下基数排序不一定比快排快。数值范围瞎设的另一个问题是当键长增长到 n 的数量级时复杂度会退化。空间复杂度是 O(n k)。n 来自临时数组k 来自计数数组。基数选 10 时k 很小选 256 时k 是 256也完全可以接受。它不是原地排序想省内存的场合要慎重。3. 从玩具到工程处理负数/字符串/浮点数的改造3.1 负数偏移量是最简单粗暴的方案(num // exp) % 10在 Python 里对负数取模会得到非负余数比如(-45 // 10) % 10的结果是 5看似能处理但如果遇到负数和正数混排单纯的按位拆分会破坏符号优先级。比如 -2 和 1 比较你按个位处理-2 的个位是 81 的个位是 1会错误地把 -2 排到 1 后面。最稳妥的办法是先把整个数组做偏移把最小值变成 0排序完再恢复def radix_sort_with_negative(arr): if not arr: return arr offset -min(arr) # 保证所有元素非负 arr [x offset for x in arr] max_val max(arr) exp 1 n len(arr) output [0] * n while max_val // exp 0: count [0] * 10 for num in arr: digit (num // exp) % 10 count[digit] 1 for i in range(1, 10): count[i] count[i - 1] for num in reversed(arr): digit (num // exp) % 10 count[digit] - 1 output[count[digit]] num arr output[:] exp * 10 return [x - offset for x in arr]这个方案最简单但要注意几点偏移后最大值和最小值之间的跨度可能很大如果原数组里有非常大的负数那么位数自然会增加轮数也会变多。Python 的大整数可以随便加偏移不会溢出如果换成 C必须用更长整型否则最小值恰好是 INT_MIN 时-min(arr)本身就溢出了。如果不想做整体偏移可以另一种思路先单独把负数取绝对值排序再反转拼接最后合并正数。但这样会破坏稳定性而且处理起来更容易出错。实际工程里“偏移 一次排序”更干净。3.2 变长字符串从末尾补位到字典序基数排序不只处理整数字符串也可以。一个常见的场景是定长字符串比如序列号、身份证号、Md5 摘要。此时每个字符都可以看作一位直接按 ASCII 码分桶处理即可。变长字符串麻烦在长度不一致。LSD 的处理方式是从最后一个字符开始向开头逐位处理短的字符串在缺少字符的位置要补一个“最小字符”。这样短串天然会被排在长串前面符合字典序直觉。但补位字符必须是真正的最小值。比如 ASCII 环境下你可以用\0作为补位字符因为任何普通字符的 ASCII 码都大于 0。如果直接用空格字符补位而数据里又有比空格小的控制字符结果就会出错。对于字符串MSD 其实比 LSD 更常用。MSD 从字符串开头分桶天然不需要补位到最长遇到空桶还能剪枝。它的问题是每个桶内还要递归排序如果开头分布很不均匀递归深度和空间开销会有波动。所以字符串场景不少人会干脆走快速排序或三向快速排序基数排序只适合定长字符串。3.3 浮点数先转IEEE 754整数浮点数也能用基数排序秘诀是把 IEEE 754 的位模式转换成一个“保序的整数”。S、E、M 三个部分组合后只要符号位和阶码顺序一致整数的比较顺序就和浮点数一致但负数例外负浮点数转换成大整数后绝对值大的负数的整数反而更大。解决方法是做一个位级变换import struct def float_to_sortable_int(f): bits struct.unpack(q, struct.pack(d, f))[0] if bits 0: return bits ^ 0x7fffffffffffffff # 翻转所有位 return bits | (1 63) # 符号位置1原理很简单对于负浮点数把所有位翻转后它的整数顺序从“按绝对值反向”变成了“按绝对值正向”而且会落在所有正浮点数对应的整数区间之下。这样转换完的整数和浮点数的大小顺序完全一致。排序结束后再逆变换回来即可。我不推荐在生产环境里用这个方法去排浮点数因为 NaN 的存在会打破所有排序语义。但如果你的数据保证没有 NaN想榨干性能这确实是一个可行的选项。3.4 直接按二进制排序更底层的优化思路十进制基数的优点是直观缺点也很明显32 位整数最大到 10 亿差不多 10 轮每一轮还只能利用 0 到 9 这十个桶浪费了桶数组的宽度。更贴近计算机的做法是把整数看成二进制流一次处理 8 个 bit基数就是 256count 数组长度 256。32 位整数只需要 4 轮比十进制 10 轮快得多。因为每轮处理的数据量相同轮数越少总的时间开销越低。处理有符号整数时要注意补码问题。通常的做法是在排序前把符号位翻转排序后再翻转回来。下面是一个高效的实现def radix_sort_binary(arr): if not arr: return arr INT_BITS 32 SHIFT 255 # 0xFF # 符号位翻转让负数落在正数前面 shifted [x ^ (1 (INT_BITS - 1)) for x in arr] n len(arr) for offset in (24, 16, 8, 0): count [0] * 256 for x in shifted: count[(x offset) SHIFT] 1 for i in range(1, 256): count[i] count[i - 1] output [0] * n for x in reversed(shifted): k (x offset) SHIFT count[k] - 1 output[count[k]] x shifted output return [x ^ (1 (INT_BITS - 1)) for x in shifted]这个版本每轮只走 4 次循环即使 n 很大内存访问也基本是线性的缓存表现很好。我在实际对比中这种二进制版本跑整数的速度明显优于十进制版本。如果数据是 64 位整数就把轮数改为 8 轮offset 从 56 开始每次减 8。4. 基数排序的性能调优和面试/工程中的选型4.1 内存占用 vs 速度的真实关系基数排序性能上限很大程度上受内存访问模式影响。你每轮要把所有元素读一遍、写一遍整个数组的数据要多次读写内存。内存带宽是所有基数排序实现的核心瓶颈。几个调优经验尽量不要每轮都新建output数组。可以一开始就申请两个数组轮与轮之间交换角色避免反复分配和回收。上面的 Python 示例虽然可读性好但严格来说不是最优。count 数组的宽度要适合 CPU 缓存。基数选 256 时count 只有 256 个元素完全放得进 L1 缓存基数选 65536 时count 是 256KB可能放不进 L1反而因为缓存压力大导致性能下降。我实测很多机器上 256 是一个甜点值。访问数组时尽量从低地址往高地址顺序访问。LSD 天然符合这一点因为它每一轮按元素在原数组中的顺序统计再按顺序输出。如果数据分布极端比如大量元素的最高位是 0可以在处理高轮时提前判断如果当前位对 count 没有任何贡献可以提前终止。但要注意提前终止条件必须建立在所有元素当前位都相同不能只看最大值。4.2 和快排、计数排序、归并的对比做技术选型时通常拿这几个算法一起看。算法平均复杂度最坏复杂度空间稳定性适用场景快速排序O(n log n)O(n²)O(log n)不稳定通用场景、随机数据归并排序O(n log n)O(n log n)O(n)稳定需要稳定、链表计数排序O(n k)O(n k)O(k)稳定非负整数且值域小基数排序O(d(n k))O(d(n k))O(n k)稳定定长整型、定长字符串快排在数据量小、键没法拆位、比较器便宜时最合适。归并在稳定排序需求下很难被替代。计数排序和基数排序是同族思想区别在于计数排序直接按“完整值”分桶基数排序按“位”分多轮。当 k值域很大而 d 很小时基数排序可以做到比计数排序更节能。4.3 什么时候该用基数排序什么时候别用适合用基数排序的场景有三个特点键值能稳定地拆成若干位且位数可预测。整数、固定长度字符串、时间戳、IP 地址都满足。数据量足够大。数据量小的时候快排的常数因子和递归开销已经很小基数排序多轮扫描并不会占便宜。比较器本身很贵。如果每次比较两个对象都要做复杂计算基数排序能绕开比较器收益更明显。不适合的场景也很明确键值不定长、需要完全字典序但还要求动态增长的场景。比如变长字符串LSD 补位方案会浪费空间。内存极其受限。基数排序需要 O(n) 的额外空间如果系统只能给几 KB 内存这种方案直接出局。键值本身没有可拆分的位比如自定义对象只能通过 compareTo 比较。Python 这种纯解释型语言里大规模数据排序直接用内置函数往往更快。内置函数是 C 级别的纯 Python 循环写的基数排序会慢到让你怀疑人生。4.4 并行化从多线程到GPULSD 基数排序天然适合并行。每一轮的统计阶段可以并行扫描多个数据块每个线程算出局部计数再合并成全局计数分配阶段根据全局前缀和把每个数据块映射到输出位置。这个过程几乎没有数据竞争也没有复杂的锁非常适合多核 CPU 和 GPU 加速。很多大数据框架里的高性能排序底层用的就是并行基数排序而不是并行快排。当然并行化并不是免费的午餐。数据量小时线程创建和同步的开销会盖过收益数据量大时内存带宽又会成为新的瓶颈。实际项目中我会用一句话判断如果排序时间已经接近“读一遍数据 写一遍数据”的最短时间再优化就别只盯着算法了去看硬件瓶颈吧。5. 踩坑实录常见问题与排查技巧5.1 稳定性的坑内部顺序反转我在给一个模拟项目加排序模块时第一次写 LSD 基数排序时用了“先正序填充再通过布尔额外处理”结果 170 和 90 这类个位相同的数字第二轮十位排序时顺序随随便便就反了。原因很简单第 4 步如果从前往后遍历原数组并填充同一个桶内的元素会顺序反转。排查方法也直接每轮结束后打印数组然后拿原始数组手算一轮对比低位相同的元素相对顺序是否保持一致。只要发现不一致优先检查填充顺序是不是反向的。5.2 前缀和索引算错的坑很多人为了省事会跳过前缀和直接用一个 list 当桶或者count还没累加就用来写索引。最典型的结果是数组越界、部分元素被覆盖、最终结果乱序。正确顺序是先统计 count再原地累加成前缀和最后放入 output 时对 count 做自减。这个“先累加、再自减”的模式是整个算法最容易被抄错的地方。我建议把它当成固定模板背下来不要灵机一动改结构。5.3 负数偏移和溢出问题负数偏移的方案虽然好用但隐藏一个边界如果最小值是-2147483648在 C 的 32 位 int 里-min_value直接溢出结果还是负数整个排序全部报废。在 C 里正确处理方式不是直接arr[i] - min_value而是先判断符号把数据拆成两个数组分别处理或者转成unsigned int再算。Python 没有原生溢出问题但如果你在用位运算模拟无符号整数也要小心 32 位整数翻转符号后变成大正数不要硬塞进窄类型。5.4 提前剪枝的坑提前结束循环确实能提升性能但剪枝条件要写对。比如以下错误写法while max_val // exp 0: ...这个条件是“最高位仍然存在位数”的意思没问题。但如果你改写成“当前所有元素除以 exp 都为 0 就退出”就要先确认数组里没有负数。负数的存在会让这个判断失效因为你可能提前退出导致负数的符号位还没排。更稳妥的剪枝方式是在 count 统计后判断如果 count 数组中只有一两个非零位置且它们代表的是同一位值可以早停。这种提前终止不会破坏排序结果。5.5 性能调试为什么我的基数排序比快排慢我在用 Python 做对比测试时先写了纯 Python 的基数排序然后和内置排序比结果差了十几倍。这个结论一度让我觉得基数排序是伪线性。后来才反应过来内置排序是 C 语言写死的而我的 Python 循环每一轮都在解释器里逐字节执行几十万次循环累积下来解释器开销早就超过了算法本身的复杂度优势。基数排序想要真正跑赢快排最好用编译型语言实现或者用高度向量化的库。在 C 里基数排序对随机整数往往有明显优势在 Java 里数组大时也能看到效果在 Python 里除非用 NumPy 手动向量化否则演示概念可以追求速度还是直接用内置排序吧。如果非要在 Python 里实现一个工程可用的版本建议把核心逻辑尽量放进列表推导、内置函数或者 NumPy 操作里减少纯 Python 循环的层数。比如每轮用np.bincount做计数、用np.argsort做索引排序但这样写出来的已经不太像“手写基数排序”了更像是在借框架实现思路。最后分享一个我这些年调基数排序的习惯先把正确性测试跑到最小数据量再谈优化优化指标永远盯“轮数”和“内存访问次数”而不是代码行数。任何号称“一行实现基数排序”的写法要么是玩具要么是混淆思路。如果你第一次接触这个算法老老实实把 LSD 版本写通再思考二进制优化你会比直接抄高端实现的人更快理解它到底为什么快。