限制的工程实践指南)
1. 为什么数组排序存在“天花板”基数排序却能绕过去先别急着看代码。很多人学基数排序第一反应是“这玩意儿不和别人比大小怎么能把顺序排对”带着这个疑问去查资料看到的又是一堆“LSD、MSD、稳定排序、桶”等术语最后不了了之。我换个角度讲清楚两件事为什么基于比较的排序快不到哪去以及基数排序用什么办法绕开了这个限制。先说比较排序为什么会有天花板。原因在于每一次比较本质上是一次二元判断a 要么小于 b要么不小于 b。排序 n 个互不相同的元素所有可能出现的结果排列一共有 n! 种而排序算法要能区分出这 n! 种情况就必须在决策树上走到足够深的叶子节点。树高至少要达到 log2(n!) 这个量级结合斯特林公式展开以后就是 O(n log n)。换句话说只要你的排序还停留在“两个元素比大小”的思路上无论怎么优化常数、怎么改进交换策略渐进上限就死死地压在这里。基数排序的思路彻底换了一条路它不比较元素的大小而是把整数或者字符串看成“按位切开的一串数字”一位一位地处理。比如 321先把它的个位 1 拿出来分到 1 号桶再把十位 2 拿出来分到 2 号桶最后看百位 3。每一轮要做的事本质上是最简单的计数排序——统计 0 到 9 的每个桶里各有多少元素然后按桶的顺序把元素重新放回数组。全程没有一次“大于”“小于”的判断只有“这个位的数字是多少”所以它可以突破 O(n log n) 的限制。用一个不太严谨但很好记的类比比较排序像两个人见面要“比个身高”互相比很多轮才能确认队形基数排序则像是体育馆验票入场工作人员只看你手里的票号最后一位你不能进他再换一位看几位查完所有人的座位顺序自然就出来了。它借助的是“数字的位权重”这个先验信息而不是元素之间的大小关系。这也是为什么基数排序通常只对整数、定长字符串这类“可以按位分解”的数据有效对任意的对象就没法用。如果你只是想背一个结论那记住这句话比较排序的下限是 O(n log n)而基数排序在数据位数有限的条件下能做到近似 O(n)。但“位数有限”这四个字很关键后面复杂度那一节我会详细算这笔账。2. LSD 与 MSD两种完全不同的“位数游走”路线基数排序内部其实还分两大门派一个叫 LSD最低位优先Least Significant Digit first一个叫 MSD最高位优先Most Significant Digit first。绝大多数教材讲的、工程里常用的都是 LSD。我先从 LSD 讲起因为它的实现逻辑最简单也最能体现“稳定性”这个概念的威力。2.1 LSD从最不起眼的个位开始逐步建立全局序LSD 的处理顺序是从低位向高位推进每一轮都只按当前这一位的数字来把所有元素重新排列。关键点是每一轮采用的“重新排列”必须是一个稳定排序也就是说数字相同的元素在这一轮结束后必须保持上一轮留下的相对顺序。为什么必须稳定我拿一组经典数据一步步演算给大家看。待排序数组是[170, 45, 75, 90, 802, 24, 2, 66]。第一轮按个位分桶结果如下轮次排序后的数组原始数组170, 45, 75, 90, 802, 24, 2, 66按个位排序后170, 90, 802, 2, 24, 45, 75, 66按十位排序后802, 2, 24, 45, 66, 170, 75, 90按百位排序后2, 24, 45, 66, 75, 90, 170, 802注意看第二轮结束后的数组虽然整个数组当时还没有全局有序但所有元素的“十位数字”已经是从小到大排列的而十位数字相同的那几个元素呢比如 802 和 2十位都是 0它们之间的先后顺序完全由第一轮里个位数的比较结果决定。如果第二轮用的不是稳定排序把 802 和 2 的相对位置弄反了那么后续所有基于这个位置的排序都会跟着错。这就是 LSD 的命脉所在——每一轮都必须严格保持上一轮形成的次序。LSD 最大的优点是实现清晰、只需要循环 d 次不需要递归也不需要处理复杂的合并逻辑。缺点也很明显它必须完整处理完所有的位数即使大部分数据很短也得给位数最长的那个数买单。比如有一堆数据范围是 1 到 10 亿元素本身只有几十个LSD 仍然要老老实实跑 10 轮十进制位。2.2 MSD从最高位开始分类像构造一棵字典树MSD 的逻辑则更像我们查字典先看首字母首字母相同的再看第二个字母以此类推。放到数字上就是先按最高位把所有数据拆成一个个大组然后对每个大组单独递归排序。比如对[123, 135, 19, 12]排序先按百位分19的最高位是 012/123/135的最高位是 1于是先分成两组接下来对 1 开头的组再按十位去分以此类推。MSD 和 LSD 最大的不同在于它可以提前截止某个桶里只剩下一个元素或者这个桶内部已经有序就不需要再往里递归了。正因为如此MSD 在处理“位数参差不齐”的数据时往往比 LSD 更有优势。比如一组手机号码长短差别不大用 LSD 很合适但若是一组英文单词长度从 1 到 30 都有MSD 可以在短单词所在的桶里早早收工而 LSD 必须让所有字符串都填充到最大长度去处理。但 MSD 不是没有代价。它是天然递归的递归深度取决于数据的分布最坏情况下会引入不小的函数调用开销另外每一层递归都要重新计算分桶信息控制内存和缓存的难度比 LSD 更高。还有一个实现上的细节MSD 并不强依赖“稳定排序”来保证全局正确性因为不同桶之间的顺序是最高位直接决定的不需要借助上一次的相对位置来串联信息。只有当组内所有剩余位都完全相同时原始顺序才可能成为输出结果的一部分。2.3 LSD 与 MSD 的选型参考维度LSDMSD处理方向低位到高位高位到低位是否依赖稳定排序必须依赖不依赖但需要递归分桶实现难度低循环即可较高需要递归或显式栈停止条件必须跑完所有位桶内元素 ≤1 时提前结束内存常规表现每轮需要计数器加输出数组每层递归都可能消耗额外空间常见应用整数排序、后缀数组排序字符串排序、字典序排序我个人在工程里除非遇到很特殊的字符串批量排序需求否则默认都会先用 LSD。它更容易写出稳定、可预测、不容易踩内存递归坑的实现。MSD 适合那种“最高位就能干掉一大半数据”的场景但需要做的边界处理也更多。3. 手写基数排序从教学版到能上生产环境理论听再多不如自己敲一遍。这一节我会给两个版本的代码第一个版本是十几行就能跑通的教学版适合理解原理第二个版本是计数器复用、原地回写的工程改进版适合直接拿去改造。3.1 一个最简可运行的教学版下面这段 Python 代码是基数排序最朴素的形式基于 LSD 加十进制桶def radix_sort(nums): if not nums: return nums max_val max(nums) exp 1 # 当前处理的位1, 10, 100, ... while max_val // exp 0: buckets [[] for _ in range(10)] for num in nums: digit (num // exp) % 10 buckets[digit].append(num) nums [] for bucket in buckets: nums.extend(bucket) # 按桶顺序拼接保持稳定性 exp * 10 return nums这段代码的结构非常直白每一轮先按当前位的数字把所有元素放进 10 个桶里然后从桶 0 到桶 9 依次拼接。桶的遍历顺序天然从小到大所以这一轮的结果一定“按当前位有序”而桶内的元素顺序来自上一轮的排列又保证了稳定性。两句话就能解释清楚非常适合入门。但这个版本的问题也很致命它每一轮都在创建新列表然后大量的 append 和 extend会产生很高的对象分配开销。如果数据量到百万级别跑起来会比 C 里简单实现的基数排序慢上不少。Python 里尤其明显因为列表对象的动态扩容和引用计数本身就有成本。3.2 计数排序式分桶稳定且内存复用工程上更常见的做法是不真的“把元素放进桶里”而是先统计每个桶的元素个数通过前缀和直接算出每个元素在输出数组中的最终位置然后一次放到位。这就是计数排序的分桶方式也是基数排序在生产环境里的标准实现def counting_sort_by_digit(nums, exp): n len(nums) output [0] * n count [0] * 10 for num in nums: digit (num // exp) % 10 count[digit] 1 # 前缀和count[i] 表示“数字 i”的元素总数 for i in range(1, 10): count[i] count[i - 1] # 倒序遍历原数组保证稳定性 for i in range(n - 1, -1, -1): num nums[i] digit (num // exp) % 10 output[count[digit] - 1] num count[digit] - 1 nums[:] output def radix_sort_engineered(nums): if not nums: return nums max_val max(nums) exp 1 while max_val // exp 0: counting_sort_by_digit(nums, exp) exp * 10 return nums这里最值得琢磨的就是“为什么倒着遍历”。在计算完前缀和之后count[digit] - 1代表了当前位数字为digit的所有元素在输出数组里的最后一个空位。如果我从原数组末尾往前扫那么相同数字的元素靠后的那个会先被放进输出靠后的位置前面扫描到的相同数字元素会依次放到前面更靠前的位置。正着扫则会把整个桶内顺序反转破坏上一轮留下的相对顺序。这个版本比教学版快不少另外它每轮只使用两块定长内存一块output一块count。如果数据量很大、轮数又多可以在外层把output预先分配好再传入函数复用避免每轮重新建数组。对于追求极致性能的场景还可以考虑把十进制桶换成 256 进制桶这样处理 32 位整数只需要 4 轮省下大量全数组遍历的次数。3.3 负数、字符串与任意基数到底怎么处理很多教程直接省略负数处理导致读者复制代码跑负数数组时得到错误结果。负数的处理思路有两个第一种是整体平移。找到数组里的最小值min_val把所有元素都减去它让所有数变成非负整数做完基数排序后再统一加回去。这种方式实现最简单但缺点明显如果最小值很小、最大值很大数值范围会被拉得更开需要的轮数可能增加。第二种是正负分离。把负数取绝对值单独做基数排序后反转因为绝对值大的负数实际更小正数正常排序最后把负数部分接在正数部分前面。这个做法避免了整体平移带来的位数膨胀但是需要额外处理一个绝对值边界问题在某些固定位宽整数里-2147483648的绝对值会溢出。实际工程里通常会转成 64 位先处理或者用位运算处理符号位。字符串排序本质上和整数排序是同一套逻辑只是把“十进制位”换成“字符编码位”。比如对 ASCII 字符串可以按字符码点从高位到低位或者从低位到高位处理基数取 256。遇到长度不一的字符串LSD 处理起来比较麻烦一般需要补一个比任何真实字符都小的结束符MSD 处理则自然得多短字符串一旦在某一位上“没有字符”就直接进入一个独立的空桶不再参与后续递归。这也是为什么大多数真实世界的字符串排序算法比如字典序排序更倾向于 MSD 路线。顺便说一句基数不一定非得是 10。基数越大轮数 d 越小但每轮的桶数量 k 越大。例如 32 位无符号整数用 2 进制基数要跑 32 轮用 16 进制要跑 8 轮用 256 进制只要 4 轮。轮数和桶数量之间的平衡点通常要根据数据分布和内存层级来调后面第 4 节会继续讲。4. 复杂度、空间开销与稳定性的准确账本网上关于基数排序复杂度的说法非常鱼龙混杂。有人说它是 O(n)有人说它是 O(n log n)还有人说它比快排快三倍。这些说法都对但都是在不同前提下的结论。要看清这盘棋得把复杂度公式里的每个字母都拎出来。4.1 d、n、k 分别是什么公式为什么长这样基数排序的时间复杂度写作 O(d·(nk))。三个变量各管一摊n待排序元素个数k基数也就是每一轮有多少个桶d排序需要处理的位数轮数每一轮要干的事就是遍历一遍所有元素统计出 k 个桶的数量分布再遍历一遍输出数组写回结果所以单轮复杂度是 O(nk)一共 d 轮合起来就是 O(d·(nk))。这里要特别注意基数排序并不是“线性时间排序”它的线性只是假象。当数据是固定位宽的整数时比如 32 位 intd 是一个常数十进制下不超过 10256 进制下只有 4这时 O(d·(nk)) 可以被写成 O(nk)看起来就是线性的。但如果待排序的数字范围很大、位数很长比如几百万位的大整数d 就会随数据规模增长复杂度就不能再说成线性了。4.2 为什么说它“看着快用起来挑数据”要让基数排序真正快起来需要同时满足几个苛刻条件第一数据必须能按位分解并且位数 d 不能太大。对普通整数没问题但对高精度浮点数、随机生成的双精度浮点数按位分解需要先把它们映射成某种可排序的位模式处理不当很容易出错。第二基数 k 不能无限扩大。k 太大时每轮统计和清零桶的耗时会显著上升甚至超过遍历 n 的开销。例如 n 只有 100 个元素你却选了 65536 个桶那光是清空桶的成本就够喝一壶的。第三数据分布最好能让高位尽快“拉开差距”。对 LSD 而言这一点倒不那么敏感因为它必须做满 d 轮但对 MSD 而言如果大多数元素都在同一个高位桶里那么递归拆分几乎不节省任何工作量反而会带来额外递归开销。第四内存要够。基数排序的空间复杂度是 O(nk)绝大多数实现还需要额外的输出数组这意味着它无法做到原地排序。对 GB 级数据内存访问压力会直接决定性能。4.3 和快排、归并、计数排序放在一起看算法平均时间最坏时间额外空间稳定性最适合的数据基数排序O(d·(nk))O(d·(nk))O(nk)稳定整数、定长且位数小的字符串计数排序O(nk)O(nk)O(k)稳定值域很有限且集中的整数快速排序O(n log n)O(n²)O(log n)不稳定通用可比较对象归并排序O(n log n)O(n log n)O(n)稳定需要稳定且对内存不敏感的通用数据堆排序O(n log n)O(n log n)O(1)不稳定要求严格原地排序的场景从这张表能读出几层意思基数排序并不是要取代快排而是在特定的数据形态下它的常数可以远远小于比较排序。比如对 1000 万个 32 位整数排序基数排序跑 4 轮 256 进制的遍历每轮就是对数组读一遍写一遍而快排的 n log n 意味着大约 2.3 亿次比较即使每次比较的成本不高量级也差在那里。但要强调复杂度只是一个账本真实性能还受到缓存、分支预测、向量化等因素影响。比较排序库实现的优化已经极其变态尤其像 Python 的 TimSort、C 标准库的 IntroSort针对部分有序数据和现代 CPU 做了大量调优。单纯的渐进复杂度不能决定一切下面第 6 节我会给出一些实测体验。5. 真实的工程场景基数排序到底在哪里“封神”很多人以为基数排序只是教科书习题实际工作中根本用不上。这个观点至少错过了一半。在某些细分方向基数排序不但能用而且是性能的关键支撑。5.1 大规模整数 ID 排序如果你的数据是海量整数 ID、时间戳、订单号而且没有附属的复杂对象需要一起搬动基数排序几乎是最优选择。例如在数据清洗脚本里要对百万级别的用户 ID 做一次去重前的排序ID 是 int64用基数排序跑 8 轮 256 进制分桶性能好于绝大多数通用排序库而且稳定这一性质在后续“按原顺序恢复某字段”时很有用。我印象很深的一个场景是早年处理一批埋点日志每条日志有个自增序号和一个用户 ID需要按用户 ID 排序后做关联统计。当时直接调用编程语言自带的 sort内存占用高耗时到了无法接受的程度。后来换成基数排序每一轮只维护一个辅助数组稳定排序恰好保证了相同用户 ID 的日志仍然按时间序号排列。既完成了排序又免费获得了时间序的稳定性一举两得。5.2 后缀数组构建中的倍增排序后缀数组是字符串处理领域的核心数据结构常用于全文索引、重复子串检测和压缩算法。构建后缀数组的倍增法里每一轮都需要对一组二元组(rank[i], rank[istep])排序。这里的 rank 本身是范围在 0 到 n 之间的小整数完美契合基数排序。具体做法是先用计数排序对第二关键字整体排序再用一次计数排序对第一关键字稳定排序两遍之后二元组就排好了。因为 rank 的值域是连续的整数基数排序在这里几乎不需要额外处理就能提供线性级别的每轮复杂度。如果换成快排或者红黑树排序每轮成本直接变成 O(n log n)整体构建下来的差距会非常恐怖。可以这么说没有基数排序后缀数组的高效构建无从谈起。5.3 GPU 与大内存带宽场景下的排序现代 GPU 排序工具里基数排序是主流选择之一。原因在于它的数据访问模式非常适合并行化第一遍统计每个块内的桶计数第二遍通过前缀和计算出全局偏移第三遍直接把每个元素散写到目标位置。整个过程可以拆成互相之间几乎没有依赖的规约和扫描操作天然适合 SIMD 和大量计算单元的架构。相比之下快速排序在 GPU 上的实现要处理二叉树遍历和递归分支发散严重很难吃满硬件算力。所以在需要每秒排序数亿个元素的场景比如数据库向量化执行引擎、图计算预处理、大规模机器学习数据准备GPU 基数排序几乎是默认答案。CPU 端的基数排序也不是没有价值比如现代 CPU 的 SIMD 指令可以一次处理多个元素的取位、计数操作配合 cache 友好的内存布局依然能在整数排序领域占据一席之地。6. 工程调试中容易翻车的几个细节这一节是我自己真实踩过的坑写出来希望大家少走弯路。基数排序看起来简单但真要把它塞进生产代码里边界条件多到让你怀疑人生。6.1 取位数和取数字的边界负数、大数、浮点数最常见的坑就是没有考虑负数。我第一次写基数排序时直接用max_val判断循环终止结果负数数组完全乱序原因是负数的符号位导致其按位取模出来的数字和正数不处于同一可比序列。后来我改成正负分开排序。另一个坑是位数判断条件。我用while max_val // exp 0控制循环这个写法对非负整数没问题但如果你把exp换成字符串长度来算就要格外小心超大数的科学计数法精度问题。还有人会把max_val写成浮点数结果取模出来的“位”也是浮点导致比较逻辑混乱。一句话基数排序的输入必须是规整的整数形态其他类型要么先转换要么别用。6.2 桶数组复用与内存抖动很多教学版代码每轮都重新new一个 10 元素的小数组看起来没什么但放到大规模排序场景中频繁分配小对象会导致内存分配器的压力上升拖慢整体速度。生产环境里我一般会把计数数组count和辅助数组output分配一次在循环外传入排序函数复用。如果数据规模特别大还需要关注输出数组和输入数组的轮换问题。很多实现会在每轮结束后把output覆盖回原数组这会造成额外的拷贝开销。更高效的做法是设置一个布尔标志位来表示“当前有效数据在哪个数组里”每轮结束时交换角色最后一轮再将结果搬回调用者期望的数组。这种优化对内存带宽就是实打实的翻倍提升。6.3 实测体验什么时候它真的比库排序快我在自己的开发机上做过一个不严谨的小测试随机生成 100 万个 32 位非负整数分别用 Python 内置排序和手写基数排序跑。内置排序因为底层是 C 实现的 TimSort即使基数排序是线性复杂度在纯 Python 实现下也完全占不到便宜。而用 C 或 C 实现基数排序在同样数据下处理 256 进制只需要 4 轮确实能比标准库快出两到三倍。但有一个很重要的边界条件如果数据范围非常小比如所有整数都在 0 到 999 之间那么计数排序一轮就能完事反而比基数排序更好。如果数据是随机浮点数基数排序的按位分解处理起来很麻烦标准库排序会因为底层优化而胜出。如果数据已经接近有序标准库排序的特殊优化会更明显基数排序则一视同仁地跑满所有轮次。所以我的结论是基数排序不是一把万能锤子而是一件针对性极强的工具。它最适合整数为主、位数适中、数据量大、需要稳定排序的场景。当你面对这类需求时别急着调用通用排序函数先花几分钟评估一下基数排序是否合适往往能换来成倍的性能提升。就算最后不用它理解它的思维方式也值得——因为它打破了“排序必须比较大小”这个思维定式这在很多算法设计里都是很宝贵的启发。
