排序算法聊到尽头总有那么几个“跟别人不在一个赛道”的存在。比如我经常跟人聊你用快排、归并、堆排本质上都在干同一件事——两两比较大小然后搬位置。而基数排序完全绕开了“比较”这条路它看的是数字的“形状”一位一位地分配进桶里再按顺序倒出来。这件事在Python里写起来特别有乐趣因为Python的列表操作和稳定排序特性能让基数排序的实现有两种截然不同的思路一种是最正统的“建桶收集”另一种是剑走偏锋的“直接用sort”的极简版。如果你只是背过口诀“LSD从低到高每个位做一次稳定排序”那我建议你停下来花十分钟亲手把流程和代码过一遍。这篇内容适合想彻底吃透基数排序原理的朋友也适合面试前临时抱佛脚、或者想在竞赛里用Python手写一个能跑的版本的同学。我尽量把原理、代码、避坑、性能实测都揉在一起讲不讲废话。1. 先想明白一件事基数排序不是在“比较”大小而是在“分配”次序1.1 比较排序的“天花板”为什么在O(n log n)这里卡住常见的高效排序算法比如快速排序、归并排序、堆排序全部都是基于“比较”的每两个元素比大小根据结果决定谁在前谁在后。数学上有个结论基于比较的排序最坏情况下至少需要 O(n log n) 次比较这叫“比较排序下界”。原因是每次比较最多产生两个分支你最终要区分 n! 种可能的排列信息论一算就卡死了。基数排序从根上就不是这么玩的。它不比较元素之间的相对大小而是把数字拆成一位一位每一位都当成一个新的“排序关键字”来处理。你可以把基数排序理解为“多轮桶排序的组合”每个数字先看个位、放进对应的桶再看十位放进对应的桶一直进行到最高位。我第一次接触的时候总觉得这事不可能每个位只排一次加起来真的能保证全局有序吗后来才体会到这里面藏着一个很关键的前提——每一轮都必须用稳定排序。这个“稳定”两个字就是灵魂后面我会单独花一章讲透。1.2 从“权重”的角度理解位与位之间的关系数字之间的顺序是由高位决定的比如 305 和 512个位分别是5和2但没人会认为512排在305前面因为百位3 5胜负在最高位就分了。那为什么LSD基数排序偏偏要从最低位开始而不是从最高位开始因为如果从最高位开始每个桶内部还要再递归地按次高位排序处理起来非常啰嗦这是MSD最高位优先的玩法。而如果从最低位开始借助“稳定”这个魔法后一轮的高位排序会自动保留上一轮已经排好的低位顺序。每一轮都在不停地“覆盖”优先级最后一轮结束优先级最高的那个位成为主导整个数组就全局有序了。1.3 一句话概括多趟稳定计数排序的叠加我把基数排序的实质简化成一句话基数排序 多趟稳定计数排序。每一趟只关注一个位计数排序负责统计该位每个取值有多少个元素再把这些元素按序放回数组。因为每一趟都是稳定的前面落下的顺序不会被破坏。这样就不需要做真正意义上的“比较”时间复杂度可以做到 O(d×(nk))其中 d 是最大位数k 是基数大小当 d 和 k 都相对常数时它就成了一台速度机器。2. 从最低位到最高位LSD流程手把手拆解2.1 一个非负整数的走位过程光说理论不好记直接拿个例子走一遍。假设我们要排[170, 45, 75, 90, 802, 24, 2, 66]第一轮看个位个位是0的170, 90个位是2的802, 2个位是4的24个位是5的45, 75个位是6的66按桶编号0→9依次收集得到[170, 90, 802, 2, 24, 45, 75, 66]第二轮看十位没有十位的当做0处理十位是0的802, 2十位是1的170十位是2的24十位是4的45十位是6的66十位是7的75十位是9的90收集得到[802, 2, 170, 24, 45, 66, 75, 90]第三轮看百位百位是0的802, 2, 170, 24, 45, 66, 75, 90 这些里面百位全是0或不存在百位是1的170咦但这个位置不对我故意把这里写模糊一点让你思考第三轮收集时百位是0的桶里会装一堆数但它们不是随便装的——顺序是“上一轮十位排好的顺序”。这就是稳定排序的功劳最终结果应该是[2, 24, 45, 66, 75, 90, 170, 802]你可以对照着代码自己推一遍感觉会完全不同。2.2 为什么不存在的位要当成0数字“45”只有两位但排序时最高位是百位。每一位都要参与所以短的数字轮到没有的那一位时要当作0处理。在Python里直接用(num // exp) % 10就能自动实现这一点因为整除后小数部分没了。比如45 // 100结果是0自然就落在0号桶。这也是基数排序对整数特别友好的原因之一有标准整除兜底。2.3 基数的选择是怎样影响轮数的上面的例子是十进制每一位有10种可能所以每轮建10个桶。如果改成二进制位一次只看一个bit那么每轮只需要2个桶但要循环的轮数会变多一个10位的数字要跑10轮。如果一次性看8个bit256进制每轮要256个桶轮数变成约总位数除以8。基数越大桶越多轮数越少。这个trade-off在后面性能部分非常关键。3. Python代码怎么写从教学版到工程版再到“作弊版”3.1 教科书版最直白的建桶收集先写一个最干净、最容易对照原理的版本def radix_sort_lsd(nums): if not nums: return nums max_val max(nums) exp 1 # 从个位开始 while max_val // exp 0: buckets [[] for _ in range(10)] for num in nums: digit (num // exp) % 10 buckets[digit].append(num) nums [x for bucket in buckets for x in bucket] exp * 10 return nums这段代码的逻辑非常直白每次取出当前位放进10个桶然后按桶顺序重新拼起来。注意buckets[digit].append(num)的append保证了先进先出这就是稳定性的实现基础——如果改成insert(0, num)或者从尾部弹出去收集就全乱了。测试一下data [170, 45, 75, 90, 802, 24, 2, 66] print(radix_sort_lsd(data)) # [2, 24, 45, 66, 75, 90, 170, 802]3.2 工程版换成256进制直接用位运算每次用10进制取余对于Python解释器来说要反复做除法和取模运算慢不说还意味着最多要循环“十进制位数”那么多轮。工程上更常用的做法是让基数为2的幂比如2^8256然后用位运算提取每一位。def radix_sort_bits(nums, bits8): if not nums: return nums max_val max(nums) mask (1 bits) - 1 shift 0 while (max_val shift) 0: buckets [[] for _ in range(1 bits)] for num in nums: idx (num shift) mask buckets[idx].append(num) nums [x for bucket in buckets for x in bucket] shift bits return nums这里核心是(num shift) mask它提取的是一个8bit块。对32位整数固定跑4轮就结束了不需要知道具体数字有几位。桶数量从10个变成256个内存大了但轮数从最多10轮变成固定4轮算法更粗暴高效。3.3 “作弊版”利用Python内置sort当稳定桶收收集器这是我特别喜欢的一个版本。Python的list.sort()是Timsort它是稳定排序。假设我们先按个位排一遍再按十位稳定排一遍重复几次效果等价于基数排序。代码短得惊人def radix_sort_pythonic(nums): if not nums: return nums max_val max(nums) width len(str(max_val)) for i in range(width): nums.sort(keylambda x: (x // 10**i) % 10) return nums每次调用sort(key...)Timsort都会按照当前位对数组做一次稳定划分。因为排序是稳定的上一轮排好的低位顺序会原样保留在key相同的组里。连续做d轮就完成了LSD基数排序。这种写法在讲原理和面试手写演示时特别好用它从侧面印证了一个观点稳定排序是基数排序的完美载体。但要说速度那就是另一回事了——Timsort本身是O(n log n)你做了d次理论上比真正的基数排序慢。实际数据也不理想我后面实测给你看。3.4 处理负数首先要解决“桶索引不能为负”的问题上面的代码都不支持负数因为(-3 // 10) % 10在Python里是7不是我们想要的“3”。一个优雅的通用方案是把整个数组先做一次线性平移找到最小值把所有数变成非负排序完再平移回去。def radix_sort_all_integers(nums): if not nums: return nums offset -min(nums) if min(nums) 0 else 0 shifted [x offset for x in nums] max_val max(shifted) exp 1 while max_val // exp 0: buckets [[] for _ in range(10)] for num in shifted: digit (num // exp) % 10 buckets[digit].append(num) shifted [x for bucket in buckets for x in bucket] exp * 10 return [x - offset for x in shifted]注意一个细节如果原数组里只有一个极小值或数字范围特别大平移可能导致大整数不过对于一般业务数据问题不大。追求极致的人会直接用符号位拆分或补码改造但那是另一个故事了。4. 稳定性是命根子一个顺序错乱就满盘皆输4.1 稳定到底是什么意思稳定排序的定义很简单值相等的两个元素排序后它们在数组里的相对顺序不变。举个例子有两个数值都是“42”的记录如果原来A在B前面排完还是A在B前面这个排序就是稳定的。很多教程把“稳定性”当成一个可有可无的加分项来讲但在基数排序里不是这样稳定性是它正确性的基石。为什么因为我们每一轮只关心“当前位”如果这一轮把上一轮排好的东西打乱了那最终结果就废了。4.2 一个反例第二轮不稳定的灾难现场假设数组是[23, 22, 31]第一轮按个位排个位131个位222个位323收集得到[31, 22, 23]这时十位都是2的两元素22和23它们之间按个位1、2排列好了。第二轮按十位排十位一样都是2按说桶内顺序应该保持[22, 23]。但如果这轮用了不稳定的收集方式比如把桶内元素逆序放入结果变成[23, 22, 31]你看全局顺序就错了22和23之间的个位序被颠倒了。所以你会发现一个规律LSD每一轮都在利用上一轮遗留下来的顺序而不是从头开始独立处理。每一轮的稳定输出是在为下一轮铺路。4.3 为什么最终能正确逐步归纳经过第一轮数组按照个位升序排列。进入第二轮所有数的十位成为主键。因为第二轮稳定因此十位相同的组内部保持“个位升序”的排列。这样数组就变成按十位升序为主十位相同时按个位升序——这不就是全体排序第三轮同理百位相同的组内部保持“十位为主、个位为辅”的排序。所有位都处理完全数组自然有序。这个归纳过程是理解基数排序的钥匙也是面试最容易问的点。下次别人问“基数排序为什么能排对”你就可以从“稳定性的归纳”去答。4.4 写代码时哪些细节会不小心破坏稳定性收集桶时用了bucket.pop()从尾部取顺序全反。用了无序的字典或set来存桶内容顺序不可控。在Python里调sort(reverseTrue)来做子排序那会把整个桶反转。用生成器yield from reversed(bucket)而不是yield from bucket。我写过一个看起来很优雅但跑出来全错的版本后来查了半天发现就是收集桶的时候想省一次遍历用了栈的弹出方式。记住桶里是队列不是栈。5. 性能实测与场景判断不要被“O(n)”冲昏头5.1 先给结论纯Python手写基数排序打不过内置sort很多人在算法课上听到基数排序是O(n)兴奋得不行觉得这是排序界的火箭炮。我一开始也这么想直到我拿Python实际测试了一把。下面是我在一台普通笔记本上的大致耗时随机生成的整数范围在0到10万之间取多次平均值结果会有浮动但比例关系稳定数据规模Python内置list.sort()教学版LSD10进制桶位运算版256进制桶作弊版多次sort1万约0.001秒约0.02秒约0.01秒约0.01秒10万约0.02秒约0.3秒约0.15秒约0.2秒100万约0.3秒约4-6秒约1.5-2秒约3-4秒为什么会这样核心原因是Python的循环和列表创建成本很高。内置sort用C语言实现每次操作都在编译器级别执行而手写的基数排序每一轮都要在Python解释器里跑for num in nums、append、列表表达式展开这些操作的常数因子太大了。复杂度再优秀也扛不住常数因子的压制。但这不是基数排序本身的问题是Python的问题。同样一套算法换到C、Rust或者对向量化友好的环境里表现会完全不同。这一点要分清楚。5.2 什么场景下基数排序才值得用我总结了几种实际值得用基数排序的场景固定宽度键排序。比如电话号码、身份证号、IP地址、时间戳长度都一样d是固定的基数排序的表现非常稳定轮数不会随数据规模增长。内存可控且追求稳定。如果你希望排序是稳定的、不引入比较开销同时数据取值范围有限基数排序比基于比较的稳定排序比如归并排序更有优势。并行或GPU环境。基数排序每轮分桶时各个桶是互相独立的天然适合并行处理。很多并行排序库底层用的就是基数排序的变种。嵌入式或FPGA场景。当排序单元硬件化时按位分桶的逻辑比大规模比较网络省资源得多。对于普通Python业务代码我的建议是老老实实用内置sort。除非你手头有百万级以上的固定宽度键并且愿意用更高阶的库来做向量化否则手写的纯Python基数排序只能作为教学和训练思维的工具。5.3 时间复杂度里藏着什么坑基数排序的时间复杂度写作 O(d × (n k))。看着是线性的但d和k都不是免费午餐。d是最大键长度如果数字有100位d就是100k是基数大小你选256进制每轮就要初始化256个空桶列表。对Python而言初始化桶列表本身就要遍历k次还要分配内存。数据量小、键很短的时候老实用内置sort反而更快。还有内存。每轮都要生成一个全新的数组和多个桶列表对于100万元素一轮就能吃掉几十MB内存GC压力也不小。你能接受吗如果数字范围特别大比如大整数几百位d会变得很高性能优势就没了。6. 踩坑记录负数、字符串、内存峰值与基数选择6.1 负数排序的三个坑第一个坑是刚开始提到的桶索引负数问题解决办法之一是整体加偏移。但偏移做法有个隐藏问题如果原数组很稀疏但跨度极大比如最小值-1000000最大值0平移后数字长度不平衡会导致多余的轮数和内存浪费。更稳的做法是先把正负数分开各自排序再合并负数部分取绝对值后排序最终倒序接在前面。这个方法对整数数组来说最直观def radix_sort_with_negative(nums): neg [-x for x in nums if x 0] pos [x for x in nums if x 0] neg_sorted radix_sort_lsd(neg) pos_sorted radix_sort_lsd(pos) return [-x for x in reversed(neg_sorted)] pos_sorted这个版本思路清晰只要你的radix_sort_lsd本身是稳定的正负合并后依然稳定。我实际测试过比加偏移方案更不容易出Bug。6.2 字符串能不能用基数排序可以但注意对齐和字典序。用LSD排字符串时短字符串需要补齐成最长长度。补什么字符很关键如果排的是纯小写字母补最小的字符并不总对因为你要考虑空位应该排在最前面还是最后面。我建议把字符串先转成元组或列表把缺失位置约定成一个明确的哨兵值。比如按ASCII排序时短字符串在高位缺失可以补一个小于所有合法字符的值这样“abc”会排在“abcd”前面符合自然词典序。如果想让长字符串在前则补一个大于所有合法字符的值。粗放一点的做法是keylambda s: s.ljust(max_len, \0)但不同的编码环境下空字符行为会有差异最好先用ord()拿到编码值再补桶而不是真塞\0。6.3 大整数与浮点数位模式对于大整数位数d可能非常长你要吗如果数字长度不均匀可以考虑MSD先切高位对桶递归避免浪费轮数。而对浮点数有个很有意思的技巧IEEE 754的位表示按整数来排序时正整数浮点的位序和数值序一致负浮点是反的。业内常用“符号位翻转”的技巧把浮点数改成可排序模式然后在整数的基数排序里直接跑。不过这个实现细节不少真要写还得仔细测试边界值NaN、Infinity这些特殊值会捣乱。6.4 内存峰值Python实现的隐形炸弹上面的代码有个通病每轮nums [x for bucket in buckets for x in bucket]会创建一个新列表同时原来的列表和桶列表在垃圾回收前仍然占内存。峰值大约是“原数组 新数组 所有桶列表”的总和。如果你排100万数据内存峰值能到好几百MB。想缓解常见做法是提前算好每个桶的大小直接复用同一个临时数组避免频繁分配。使用array模块或者numpy来存储数据减少Python对象的开销。减少桶的数量比如从256变到16以空间换轮数。我写过一个低内存版本做法是两趟第一趟统计每个桶里元素数量第二趟根据偏移直接填回原数组学的是计数排序的思路。这样就不需要真的建那么多桶列表但代码复杂度也随之上升。对纯教学来说上面这版简洁的更好但对于生产环境的排序内存占用和GC压力确实需要提前评估。6.5 基数选择10进制只是习惯不是最优十进制进制只是人最容易理解的结构不代表它在计算机里最优。我在同一组随机整数上分别用bits3、bits8、bits11实测结论大致是基数bits桶数量32位整数所需轮数实测表现1位232巨慢循环过多4位168中等8位2564通常较快内存适中11位20483桶多初始化开销变大8位通常是平衡点。桶太少轮数太多、桶太多初始化桶列表的时间又太贵。数据规模越大越值得调大基数来减少轮数。7. 还能往哪扩展MSD、浮点数位模式与并行思路7.1 MSD与字典序的关系LSD是从低到高处理代码直观但有一个局限它要求每个关键字长度一致或者至少要补齐。要是处理长度不一致的字符串数组MSD最高位优先更自然。MSD从最高位开始分桶每轮递归处理每个桶内部。这种思路跟我们查字典的过程很相似先看首字母决定进哪一区再看第二个字母确定更细的位置。写MSD时要注意递归深度和桶内元素过少时的停止问题。元素少的时候直接用简单插入排序反而更快这是工程优化的常用手段。7.2 基数排序和计数排序、桶排序是亲戚关系很多人把三种“非比较排序”搞混计数排序适合取值范围很小的情况它把每个值当成一个桶桶排序是把范围切成若干连续区间常用在均匀分布的数据基数排序则是把每个数字拆成若干位每轮做一次“按位的桶分配”。从某种意义上说基数排序是数次计数排序的嵌套也可以看成桶排序在“位”这个维度上的展开。理解这三者之间的关系比背下每种排序的伪代码要重要得多。因为很多面试题本质是“把数据特征梳理清楚选择合适的分配策略”而不是套模板。7.3 并行化的天然优势基数排序每轮分桶各个桶之间互不依赖天然可以并行。在实际系统里常见做法是主线程分桶然后把每个桶丢给不同的worker继续下一轮更进一步桶内如果键还有剩余位后续的轮次也可以完全并行处理。在高性能计算领域人们甚至会用“基数排序 GPU并行归约”的组合处理海量固定长度键。这个方向如果你感兴趣可以先从“统计桶大小”这一步并行化开始尝试效果立竿见影。7.4 我的实际体会手写基数排序的最大价值其实不在于“让程序跑得更快”而在于彻底改变你对“排序”二字的理解。以前我看到排序就想到比较写完基数排序之后我看到数据会先问它有没有稳定的位结构它能不能拆成若干个独立的关键字这个思维迁移到很多场景里都能用。比如对两个字段的业务记录排序你可以先按次要字段稳定排一次再按主要字段稳定排一次这本质上就是基数排序思想在现代工程里的日常版。我个人的建议是如果你在学算法花一个下午把教学版、位运算版、作弊版各写一遍再故意制造几个破坏稳定性的Bug看看结果有多离谱比看十篇教程都管用。真正到生产环境里Python排序第一选择永远是内置sort但理解了基数排序你会对“排序的极限在哪里”这件事有一个全新的坐标。