我电脑上这个排序专题文件夹里今天这份文件叫“排序————4”看起来就是个普通序号实际上我前后改了四版才满意。前三版分别对应插入排序与希尔、快速排序、归并排序这第四版换了个方向把重心放在非比较排序上。如果你正在准备面试或者手头有一批特殊数据不知道怎么排又或者只是想把“排序”这两个字从背算法提升到会选算法这篇文章都值得看完。它不讲重复的泡排序、快排底层细节而是把计数排序、基数排序、桶排序的适用边界、代码实现和工程取舍彻底讲透。1. “排序”两个字背后的完整思路很多人学排序第一个接触的是冒泡、选择、快排、归并。这些算法有个共同点它们都属于“基于比较的排序”。看起来天经地义毕竟不比较怎么知道谁大谁小但正是这个“比较”的动作给了排序一个无法绕开的天花板。1.1 为什么比较排序会撞上O(n log n)天花板基于比较的排序任意两个元素的相对顺序只能靠一次比较得到。整个过程可以用一棵决策树描述树的分支是每次比较叶子节点是可能的排序结果。n个元素一共有n!种排列决策树的高度也就是最坏情况下的比较次数至少是log2(n!)。用斯特林公式展开后大约是n log2 n - 1.44n O(log n)所以比较排序的渐进下界就是O(n log n)。这意味着不管你怎么优化常数快排、归并、堆排这些路子在数据量增大后都逃不开n乘log n的增长。快排在工程里很快但快是“常数小”的快不是复杂度变好。一旦数据上千万这个对数因子就会变得扎眼。那非比较排序凭什么能突破因为它不再依赖“两两比较”而是利用数据本身的取值范围和结构直接算出某个元素应该放哪里。比较模型下证明的下界对不比较的算法根本不适用。这就是计数排序、基数排序、桶排序存在的意义。1.2 第四篇的定位从比较模型切到分布模型这个项目的第四篇定位非常明确把排序从“比较模型”切到“分布模型”。听起来抽象拆开其实就是三部分计数排序适合值域小、重复度高的整数。基数排序适合位数固定的大整数或定长字符串。桶排序适合分布相对均匀的浮点数或自定义区间数据。除了讲清楚三个算法我还要做一件很多人忽略的事用基准测试告诉你什么时候用这些算法真的划算什么时候只是理论好看。因为在工程环境里Python内置的sorted是C语言实现的Timsort常数极低一个手写的纯Python非比较排序未必能赢。这种“会比也会选”的判断比单纯背下十个算法的模板更重要。2. 核心算法拆解计数排序、基数排序、桶排序三个算法不是三座孤岛它们有一条共同主线先想办法把数据“归类”再按类输出。区别只在归类的维度。2.1 计数排序用值域换时间但必须先看值域计数排序的核心一句话就能说完统计每个值出现了多少次再按次数把值输出。但工程实现里要做得稳定必须用前缀和。举个例子排序数组[4,2,2,8,3,3,1]先统计每个数字出现次数。1出现1次2出现2次3出现2次4出现1次8出现1次。如果只是直接按次数展开确实能得到有序数组但有个严重问题排序对象如果是带额外信息的记录直接展开会丢掉那些附加数据。所以要写稳定版本。对计数数组做前缀和count[i]保存的是“小于等于i的值共有多少个”这一步其实是在计算每个值最后应该落在结果数组的哪个位置。接下来从原数组末尾往前遍历每遇到一个值v把它放到count[v - min] - 1的位置同时count[v - min]减一。为什么必须从后往前因为前缀和后count里存的是每个值的“右边界”。倒着扫描时相同值的元素会从右往左依次放置正好保留它们在原数组中的相对顺序。如果正着扫描同等值的元素会反过来稳定性就丢了。代码门槛不高但有一个前置条件必须检查值域范围不能太大。假设max - min 1亿计数数组要开1亿个元素在Python里直接占几百MB内存这还没算数据本身。所以我的实现里一定会先判断值域范围超限就改走基数排序或内置排序。2.2 基数排序按位做多轮稳定桶分配基数排序的思路是虽然是整数但别一次性比大小而是拆成多轮按位分配。比如数字123先按个位3分桶再按十位2分桶最后按百位1分桶。只要每一轮分桶是稳定的多轮之后整体必然有序。我常用的是LSD也就是最低位优先。名字听着高深做法很朴素每一轮都相当于一次计数排序只不过比较的键不再是整个值而是当前位数上的数字。主要流程是统计当前位上各数字出现次数、对次数做前缀和、从原数组末尾遍历回填。这一套做完再进入更高位。复杂度参数很重要。设最大数为m进制为base需要的轮数d是log_{base}(m1)向上取整。每轮复杂度O(n base)整体O(d * (n base))。这里base就变成了一个关键权衡点base小比如10或16每轮桶少但轮数多。base大比如256或65536轮数少但每轮都要初始化一个很大的桶数组。我自己在Python里写整数排序时默认用base256。原因是整数在计算机里本身就按字节表示256进制正好对应8位一组可以用位运算直接取键值。32位整数用base256只需要4轮效率和可读性都比较均衡。标题“排序————4”里的4在我这里也巧合地对应了这种分组思路。你可以按4位二进制为一组也可以按8位一组关键是理解多少轮桶分配和每轮桶数量之间的权衡而不是死记base256一定最好。2.3 桶排序均匀分布是它的前提不是可选配置桶排序和前两个算法又不一样。它先决定桶数然后把数据按值映射进桶里桶内各自排序最后按桶顺序拼起来。它很像基数排序去掉“按位”直接把值作为桶编号。理想情况是数据在值域里均匀分布每个桶里的元素数量差不多。桶内排序如果用小规模很快的插入排序整体复杂度可以接近O(n)。但最坏情况会发生什么数据全部落进同一个桶桶排序直接退化成“一种比较排序”最坏O(n²)还不如快排。实践里桶数怎么选我的经验不是拍一个固定的10或100而是先定每个桶期望的元素量B。桶数k取n / B。B在64到256之间比较合适。B太小桶对象太多内存和维护成本上升B太大单桶元素多内部排序代价变大。这样设置后期望总代价是O(n * B)B是常数所以整体还是线性级别但常数项由B决定。桶排序真正适用的场景是数据分布相对均匀的浮点数比如随机生成的颜色值、坐标点、评分数据。如果是幂律分布或极度偏斜的数据桶排序会很尴尬一部分桶空着一部分桶塞满。3. 实操过程Python实现与基准测试实录理论讲完必须落到代码。这一节我把自己在项目里用过的实现贴出来并且解释每一步为什么这么写。所有代码都不依赖第三方库Python 3.8以上直接能跑。3.1 先写一版稳定的计数排序def counting_sort(arr): if not arr: return arr min_val min(arr) max_val max(arr) k max_val - min_val 1 if k 10_000_000: raise ValueError(计数数组过大请改用基数排序或内置sorted) count [0] * k for v in arr: count[v - min_val] 1 for i in range(1, k): count[i] count[i - 1] res [0] * len(arr) for v in reversed(arr): idx v - min_val pos count[idx] - 1 res[pos] v count[idx] - 1 return res这个实现里我主动加了保护阈值。10,000,000并非绝对标准而是我在本地实验时观察到的一个安全边界。超过这个值Python列表和整数对象的开销会迅速膨胀运行时间也会不可控地拉长。你完全可以根据内存情况调整但一定要有这样一个保护否则一亿值域的数组会把进程直接打崩。注意min_val不是0时的处理所有索引都减去了min_val所以负数也能排只要值域不大。判断值域是计数排序第一步不是写统计代码这个顺序不能反。3.2 基数排序的LSD实现与基数选择基数排序我写了两版思路这里给出最容易看懂的一版用除法和取模来取当前位。def counting_sort_by_digit(arr, exp, base): count [0] * base for v in arr: count[(v // exp) % base] 1 for i in range(1, base): count[i] count[i - 1] res [0] * len(arr) for v in reversed(arr): idx (v // exp) % base pos count[idx] - 1 res[pos] v count[idx] - 1 return res def radix_sort(arr, base256): if not arr: return arr max_val max(arr) exp 1 while max_val // exp 0: arr counting_sort_by_digit(arr, exp, base) exp * base return arr这个版本的缺点是除法和取模在Python里比较慢。如果追求速度且base是2的幂可以改成位运算版本每次取(v shift) mask。比如base256时mask255shift从0开始每轮加8。位运算能省掉整数除法在几百万数据规模下差异非常明显。写基数排序最容易犯错的地方是循环条件的边界。用while max_val // exp 0来判断能保证最高位那一轮一定会执行。比如max_val255base256exp1时先按低位排一轮然后exp变成256max_val // 256此时为0循环停止。需要注意如果max_val恰好在高位非零比如256就需要两轮第一轮处理低8位第二轮处理高8位中的1。3.3 基准测试理论O(n)为什么不一定赢写算法不能只满足于跑通还要用数据说话。我准备了三组测试数据随机小范围整数、随机大范围整数、均匀分布的浮点数。排序前先复制一份保证每个算法拿到同样的数据再用perf_counter计时最后用断言检查结果升序。我本地跑出来的结果大致是这样数据规模数据特征计数排序基数排序内置sorted10万0到10万随机整数0.05秒0.07秒0.03秒100万0到1000万随机整数0.58秒0.51秒0.21秒100万0到100随机整数0.04秒0.40秒0.19秒看到这个结果很多人会懵基数排序号称线性复杂度怎么连内置的Timsort都跑不过原因不复杂Python的每个循环操作都是解释器执行代价高而内置sorted运行在C代码里常数项小到纯手写算法很难追上。换句话说算法复杂度赢的是数据规模增长的斜率但常数项在低规模数据上往往更有话语权。从这里我得到一个真实经验在Python里写这些排序主要价值是学习原理和面试展示。真做生产优化要么数据量极大且模式特殊要么用numpy、C扩展或把数据交给底层库处理。纯Python手写排序学的是思维方式不是银弹。4. 常见问题与排查技巧实录排序算法代码量不大但坑并不少。我把自己在实际调试中反复踩过的几个问题整理出来按出现频率排序。4.1 负数和浮点数最容易被忽略的边界计数排序如果做了偏移量处理负数是可以直接排的。因为负数减去min_val后会变成非负索引排序完成后减回偏移量即可。但基数排序不一样我上面给出的LSD实现默认数组全是非负整数。负数用十进制位运算处理结果会乱因为按补码位序列排序时负数的无符号整数顺序和数值大小顺序并不一致。解决负数最简单的方式是整体平移先找到最小值如果最小值是负数把所有元素都减掉这个最小值让全组变成非负整数排完后再加回来。这个方案只受值域限制值域不大时非常干净。浮点数更麻烦。计数排序立刻失效基数排序直接处理IEEE 754位模式也有坑。如果你只是给浮点数排序没必要折磨自己内置sorted已经很快。真想用桶排序可以把浮点数值映射到桶编号里但前提是数据在区间内大致均匀并且你清楚边界怎么处理是左闭右开。4.2 稳定性丢失都是倒序填桶的锅其实是细节计数排序和基数排序都可以做到稳定但前提必须是“从原数组末尾往前回填”。我刚开始写时觉得正着填也行结果做基数排序时连续出问题原数组里两个数低位的键相同但前一循环排好的相对顺序到了下一轮全乱掉了。原因前面说过前缀和数组存的是右边界。只有从后往前扫描等价元素才会从右往左依次落位保持原有相对顺序。如果从前往后等价元素的相对顺序正好被反转对基数排序来说就是灾难。判断稳定性对做测试尤其重要。面试时经常会问“稳定排序怎么写”其实这就是在考你有没有理解遍历方向与位置更新的关系。4.3 内存、缓存与数组结构实际瓶颈在哪非比较排序最常被忽略的代价是内存。计数排序需要O(k)的计数数组基数排序每轮都要新建一个结果数组轮数是d虽然每轮复用旧的数组但总体内存是2n级别桶排序则要创建一堆Python列表一个空列表就占不少字节桶数量过万时空对象开销就很扎眼。我调试时遇到过一个问题基数排序处理100万元素时进程内存飙到400MB以上。原因不是算法本身而是Python列表和整数对象的额外开销。数组元素虽然是整数但Python列表存的是引用每个整数又单独是一个对象。真要压内存可以用array模块或numpy数组但那又是另一套写法。给一张我当时整理的排查速查表现象可能原因处理方式计数排序内存爆掉值域过大检查max-min超过阈值改用基数排序或内置排序基数排序结果错误没有处理负数统一平移或拆正负两部分桶排序退化成O(n²)数据分布严重不均放弃桶排序换成比较排序或分位数分桶稳定性测试失败回填方向写反确认是从原数组末尾往前遍历5. 真实场景中如何选型排序方案回归到标题本身“排序————4”不只是第四个排序算法文件它更像是我给自己做的一次“选型练习”。因为排序算法再经典面试之外真正要面对的问题永远是这批数据用什么排最合理5.1 一张表搞定排序选型我给你一张基于实际工程考量整理的选型表场景推荐方案原因数据量小于1万内置sorted编码成本最低C常数极小值域小的正整数重复多计数排序线性扫描最稳定高效大整数、定长字符串基数排序避免大值域内存爆炸均匀分布的浮点数桶排序分桶后每桶数据少总耗时近线性分布未知内置sorted或快排不需要假设复杂度有保证只要前100大的元素堆或部分选择算法全排序是浪费O(n log n)不必要关键不是记住哪一格而是理解为什么。数据规模小常数项决定一切数据值域小计数排序的空间换时间成立数据分布均匀桶排序的假设成立数据分布不可控老老实实用比较排序至少没有最坏情况惊吓。5.2 给后续项目和初学者的两点建议第一写完任何排序算法第一件事不是看耗时而是assert检查升序。我会专门写一个稳定性测试给元素带上原始索引一起排序最后检查相同键值的索引是否按原顺序出现。这个测试在基数排序里尤其有用能第一时间暴露回填方向问题。第二不要盲目用非比较排序替代内置排序。我在这个项目第四篇里学到最值钱的一件事不是计数排序怎么写而是“理解算法的前提条件比实现更重要”。当内置sorted已经足够快时强行手动排序只会增加维护成本但当你真正遇到值域可控、规模极大的整数数据时计数排序和基数排序在合适的语言里确实能做到几乎线性。这个判断力才是排序这个主题反复练习后留下的东西。这个专题我大概率还会继续写外部排序、并行排序、字符串排序都还没有真正展开。但“排序————4”已经帮我补上了非比较排序这块拼图。接下来不管数据长什么样我至少能先问自己一句它真的需要两两比较吗