计数排序、桶排序、基数排序：三种O(n)线性排序算法详解

如果只学到快排、归并和堆排你大概率会觉得 O(n log n) 已经是排序算法的天花板了。毕竟算法课上讲过基于比较的排序最优下界就是 O(n log n)。但真到业务里你会碰到一批时间复杂度 O(n) 的排序算法比如计数排序、桶排序和基数排序。这三个算法最大的共同点是不再依赖元素之间两两比较而是利用数据本身的范围和分布特征来直接放置元素。这篇是排序算法系列第三篇主要聊清楚这三种线性排序的原理、实现、适用场景以及我在工程和面试里踩过的坑希望你看完能知道什么时候该用、怎么写出稳定版本而不是只会背模板。1. 线性排序到底是怎么回事1.1 比较排序为什么有天花板先说一个很多人都听过但未必真正理解的结论任何基于比较的排序时间复杂度都不可能低于 O(n log n)。这里的“基于比较”指的是冒泡、选择、插入、快排、归并、堆排这类通过两两比较元素大小来决定顺序的算法。它们的共同点是每轮操作只能获得“a 大于 b”或“a 小于 b”这样一个二选一的信息。可以用决策树来理解。n 个元素的排列一共有 n! 种可能排序算法本质上是在这 n! 种排列中找出正确的那一个。每次比较相当于走一次“是/否”的分支一棵高度为 h 的二叉树最多能区分 2^h 种结果。所以要想覆盖 n! 种排列必须满足 2^h ≥ n!于是 h ≥ log2(n!)。根据斯特林公式log2(n!) 大约是 n log2 n 量级。也就是说只要算法还在“比较”就绕不开这个下限。这个下限不是数学游戏它直接影响你的选型思路。在真实业务里如果数据本身没有额外特征内置的快速排序已经是工程最优解但如果你知道数据是某个范围内的整数、分布比较均匀或者是一组固定位数的编号那么就可以跳出“比较”的框架用空间换时间把复杂度压到 O(n)。1.2 三种 O(n) 排序的共同前提计数排序、桶排序、基数排序能够做到 O(n)并不是因为它们违反了比较排序的下界而是因为它们处理问题的方式变了不是每次问“谁大谁小”而是直接把数据放到它应该待的位置上。这有点像整理名片。如果让人对着一堆名片两两比较生日工作量自然随人数增长但如果你准备一个带 12 个月份标签的盒子看到一月份的名片就扔进一月那格整个过程是线性的。之后每个格子里再按日期排一下仍然很快。线性排序的核心就是利用“数据本身的位置信息”减少比较次数。不过这三个算法的前提各不相同计数排序要求数据是值域不大的整数或者可以离散成整数桶排序要求数据在区间内大致均匀分布基数排序要求数据可以拆成若干位比如整数、日期、字符串。所以不要把 O(n) 理解成“万能超越”。它们更适合特定场景在场景不匹配时反而可能比快排慢得多甚至内存爆掉。后面每一节我都会把适用边界和实现细节一起讲清楚。2. 计数排序最简单的空间换时间2.1 核心思路先数数再放回计数排序的思路朴素到有点“暴力”如果输入是取值范围很小的整数那就直接用数组下标代表数值统计每个数值出现了多少次然后按顺序把元素填回去。举个例子现在要对[4, 2, 2, 1, 3, 1, 0]排序。最小值是 0最大值是 4所以准备一个长度为 5 的计数数组。第一遍扫描后得到值01234次数12211如果只是把次数展开成[0, 1, 1, 2, 2, 3, 4]那就得到了排序结果。但这里有个问题如果输入元素不是单纯整数而是带有其他信息的对象这个“展开”方式会丢掉稳定性。所谓稳定性指排序后相同关键字的元素保持原来的相对顺序。很多场景下这是硬需求比如按“分数”排序学生记录分数相同的同学希望维持原先的先后顺序。为了保留稳定性标准做法是用“前缀和 反向填充”。将次数数组转成前缀和表示“小于等于当前值的元素共有多少个”。然后从原数组末尾向前遍历每遇到一个元素就根据前缀和确定它应该放到输出数组的哪个位置同时把前缀和减一。从后往前遍历保证相同值的元素会从后往前放置不会互相穿位因此稳定。2.2 带偏移的完整实现实际写代码时不能直接假设数据从 0 开始。可能是负数也可能最小值是 100。所以要先求出最小值和最大值再按value - min作为计数数组下标这样能把值域压缩到max - min 1。def counting_sort(arr): if not arr: return arr min_val min(arr) max_val max(arr) k max_val - min_val 1 count [0] * k for v in arr: count[v - min_val] 1 # 前缀和 for i in range(1, k): count[i] count[i - 1] output [0] * len(arr) # 反向填充保证稳定性 for v in reversed(arr): idx v - min_val count[idx] - 1 output[count[idx]] v return output这里的核心细节就是两个偏移处理以及反向填充。偏移处理解决负数和非零起始值的问题反向填充解决稳定性问题。如果不要求稳定直接用展开法也可以写法会更简单但作为通用排序模板稳定版本更实用。2.3 什么时候该用计数排序计数排序的时间复杂度是 O(n k)其中 k 是值域范围空间复杂度也是 O(n k)。当 k 的规模和 n 差不多时整体才是真正的 O(n)如果 k 比 n 大很多比如数据范围是 0 到 10 亿但样本只有一万个直接分配一个长度十亿的计数数组内存当场就崩了。适合计数排序的场景在业务里其实不少。比如按 0-100 的成绩排序、按年龄段统计后排兵布阵、按状态码聚合接口耗时、按 IP 段的某个部分做分组都是值域有限且离散的整数。只要“范围小、样本大”计数排序通常比快排快一个量级。有一个常见误区浮点数能不能用计数排序严格说不行因为浮点值太多任何区间内都可能出现无数取值。但如果浮点数精度固定比如保留了两位小数先乘 100 转成整数再按整数做计数逻辑上也可以只是范围可能变得很大。总体而言浮点排序优先考虑桶排序。3. 桶排序把问题切成小块3.1 思路让区间天然有序再整理桶内桶排序是三种线性排序里最“工程”的一个。它先把数据分成若干个区间每个区间对应一个桶然后按数值把元素放进不同的桶里。因为区间是单调递增的所以桶与桶之间天然就是有序的第一个桶里的所有元素一定小于第二个桶里的所有元素。接下来只需要在每个桶内部排序最后按桶的顺序拼接起来即可。这里要明确一点桶排序整体上不是靠比较来排序的它靠的是“分区间放置”的线性过程但每个桶内部可以使用任意排序方法。如果数据均匀分布每个桶里的元素数量很少桶内排序的代价趋近于常数。于是总复杂度可以近似写成分桶遍历O(n)每个桶内排序假设 n 个元素分到 B 个桶每个桶平均 n/B 个桶内排序成本约为 O((n/B) log(n/B))总成本 O(n log(n/B))合并O(n)当 B 取得接近 n也就是每个桶平均只有常数个元素时总成本退化为 O(n)。这就是桶排序能在平均情况下达到线性的原因。现实里的例子也很多按用户 ID 哈希分桶统计按小时切分日志再各自排序把 GPS 坐标按经纬度分块处理。桶排序的价值不只是纯排序它本身就是一种“分摊计算”思想。3.2 桶数量和映射函数怎么定桶排序写起来不复杂但两个参数选不好性能差距会非常大。第一个参数是桶数量 B。最常见的经验值是 B n也就是元素有多少个桶就开多少个。这样平均每个桶里只有一个或少数几个元素桶内排序几乎是 O(1)。如果内存紧张也可以用 B sqrt(n) 或 B n/10但桶内元素变多总复杂度会向 O(n log n) 回退。反过来B 不能无限大否则大量空桶浪费内存和遍历时间。第二个参数是映射函数。假设已知数据最小值 min_val 和最大值 max_val区间宽度为width (max_val - min_val) / B那么元素 v 对应的桶下标可以这样算idx int((v - min_val) / width) if idx B: idx B - 1这里int()是向下取整确保 v 落在[min, max]区间时下标不会越界。但最后一个边界值 max_val 可能正好算出idx B所以要强制拉回 B-1。这个小细节写漏了线上数据一多就会报数组越界。一个容易忽略的问题映射函数必须保持单调。也就是说如果一个元素小于另一个元素那它所在桶的下标不能更大。用线性映射天然满足这个条件但如果你用某种哈希函数来做桶映射那只是把数据打散并不能保证桶间有序那种做法叫哈希分桶和排序桶不是一回事别搞混了。3.3 完整实现和桶内排序选型下面是一个用 Python 实现的桶排序桶内直接用 Python 自带的 Timsort 排序。这是最简单也最稳的写法def bucket_sort(arr, num_bucketsNone): if len(arr) 1: return arr min_val min(arr) max_val max(arr) if min_val max_val: return arr b num_buckets or len(arr) width (max_val - min_val) / b buckets [[] for _ in range(b)] for v in arr: idx int((v - min_val) / width) if idx b: idx b - 1 buckets[idx].append(v) for bucket in buckets: bucket.sort() return [x for bucket in buckets for x in bucket]你可能会问桶内用bucket.sort()不还是基于比较的排序吗没错但这个不冲突。桶排序能称得上 O(n)不是因为桶内完全不用比较而是因为均匀分布假设下每个桶的规模很小小规模排序的耗时可以当成常数。如果你想要更纯粹的线性实现桶内元素超过阈值时再把桶递归成桶排序而不是直接快排这也是允许的。那什么时候选插入排序而不是内置 sort如果桶的个数等于 n每个桶里基本只有 0 到几个元素手写插入排序比调用通用排序更省开销因为没有函数调用和临时对象构造的成本。但如果桶内可能有几十上百个元素直接用内置排序更安全它在工程上做了大量优化普通手写插入排序不一定比它快。桶排序最怕的是数据分布不均匀。比如有一万个数据理论上分布在 0 到 100 之间结果 99% 的数据都落在 80 附近那它们会全部挤进同一个桶桶内排序直接退化成 O(n log n)甚至更差。遇到这种场景比较稳妥的做法是先采样估计分布再按分位数切桶而不是简单等宽分桶。还有一种思路是“递归桶排序”某个桶元素太多就对这个桶的数据再次分桶直到每个桶足够小。这样可以在一定程度上抵抗不均匀数据。4. 基数排序按位处理低调优雅4.1 从低位到高位为什么最后一定有序基数排序的直觉很有意思不一次比较完整的数而是把数拆成多位逐位排序多轮最后整体有序。通常用的是 LSD最低位优先版本也就是先按个位排再按十位排再按百位排。关键在于每一轮都必须使用稳定的排序算法。稳定排序保证上一轮排好的低位顺序在进入到更高位时不会被破坏。举个例子对[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可以看到三轮之后所有数字完全有序。整个过程没有出现一次“两个完整数字比大小”这就是基数排序能绕过比较下限的原因。只要最大数的位数 d 是常数总复杂度就是 O(d * (n k)) ≈ O(n)。位数少的时候你会发现基数排序非常“稳”。它不像快排那样依赖枢轴选得好不好也不像桶排序那样依赖数据是否均匀。它对数据的唯一硬要求就是能拆成若干独立的位。4.2 用计数排序做稳定子过程每一轮“按某一位排序”最理想的子算法就是计数排序。因为某一位的取值只有 0 到 9 十种可能正好是计数排序最舒服的值域。代码写起来也不长def counting_sort_for_radix(arr, exp): n len(arr) output [0] * n count [0] * 10 for v in arr: digit (v // exp) % 10 count[digit] 1 for i in range(1, 10): count[i] count[i - 1] for v in reversed(arr): digit (v // exp) % 10 count[digit] - 1 output[count[digit]] v return output def radix_sort(arr): if not arr: return arr max_val max(arr) exp 1 while max_val // exp 0: arr counting_sort_for_radix(arr, exp) exp * 10 return arr这里exp代表当前处理的位权1 是个位10 是十位100 是百位。每一轮都重新统计 0-9 的次数然后反向填充保证稳定性。外层循环的次数就是最大值的位数。如果你有 C 或 C 背景可能会想原地修改数组避免拷贝。实际上每轮生成新的output数组更清晰因为上一轮的数组在下一轮中已经没有复用价值。真要在原地优化可以复用两个数组做 ping-pong 切换但在 Python 里这样做收益不高反而容易引入 bug。4.3 位数、进制和复杂度以及负数问题基数排序的时间复杂度一般写作 O(d * (n k))。d 是最大数的位数k 是基数范围。对十进制整数k 10如果把每一位扩展成 256 种可能比如按字节排序k 256d 变小但每组计数数组变长。这是时间和空间的权衡。经典教科书里如果输入是 32 位整数最大位数 d 是一个固定常数所以可以认为复杂度是 O(n)。但实际工程中如果数据时从 1 到 10^18d 可能是 19这时候常数就不小了可能和 O(n log n) 的常数差不多。所以不要把“常数”真当成零。负数处理是基数排序的经典坑。按位取模时负数的最低一位也是负数直接进计数数组会越界。常见做法有两种一是把整个数组整体偏移让最小值变成 0。比如最小值为 -500把所有元素加 500 后排序最后再减回来。这个方案简单但会破坏数据本身的语义适合纯数值排序。另一种更规范的做法是把正数和负数分开负数部分取绝对值后做基数排序再反转顺序放到结果前面非负数部分正常排序放到后面。因为对于负数来说绝对值越大原数越小。这个方案不改变数据也保持了稳定性。我在自己的工具函数里更推荐第二种。5. 怎么选、踩坑与实战建议5.1 一张表理清选型做技术选型时我习惯先看数据范围再看数据分布最后看是否要求稳定性。三种线性排序的区别浓缩成一张表算法平均时间复杂度最坏时间复杂度空间复杂度稳定性最适用场景计数排序O(n k)O(n k)O(n k)稳定值域小的整数比如成绩、年龄、状态码桶排序O(n)O(n^2)O(n)取决于桶内排序范围大但分布均匀的数据尤其是浮点数基数排序O(d * (n k))O(d * (n k))O(n k)稳定固定位数的整数、字符串、日期这里的 k 在不同算法里含义不太一样计数排序的 k 是值域范围基数排序的 k 是每一位的基数十进制是 10桶排序不受值域范围直接影响但受分布影响。面试时如果考官追问“你这个 k 是什么”一定要先说清楚。实际选择时可以按这个顺序判断如果是整数且最大值减最小值不大优先计数排序如果是浮点数或整数范围很大但分布均匀优先桶排序如果位数固定比如订单号、身份证号、日期时间优先基数排序如果数据没有明显特征用内置排序别为了炫技硬套线性排序。5.2 我在实际项目中踩过的三个坑先说第一个坑计数排序忘记处理偏移。有一次我需要给一批包含负数的埋点数据进行排序直接按原始值当下标代码一执行就报list index out of range。后来统一改成v - min_val才解决。这个问题看起来 trivial但在线上数据范围不稳定时会反复出现尤其是你无法提前保证数据非负时。第二个坑桶排序的最大值越界。等宽分桶时最大值通过int((v - min) / width)会得到B而不是B - 1。如果忘了判断最后一个元素会被放到不存在的桶里。这个 bug 很奇怪因为大部分数据都正常只有最大值那一个元素出问题。后来我把边界判断加在映射函数里同时也提醒自己写分桶逻辑时先想清楚闭区间还是开区间。第三个坑基数排序对负数直接失效。我最初以为取每一位的绝对值就行了结果排出来的负数顺序是反的。后来改成先分正负两组负数取绝对值排序后反转再拼接问题才彻底解决。这个改造会让代码变长但换来了正确的负数排序。5.3 工程里的实用建议如果你只是想快速解决一个排序需求不要一上来就自己写线性排序先用list.sort()或内置的sorted()它们经过大量优化对小数据和中型数据快得惊人。线性排序的优势要在数据量足够大、场景特征明显时才能体现出来。我自己的习惯是写一个统一的排序入口根据数据特征自动选择算法。比如先判断数据类型和值域值域小于样本量一个量级时用计数排序浮点或大范围整数且分布大致均匀时用桶排序固定长度的数字字符串或大整数时用基数排序其他情况回退到内置排序。这套逻辑写成一个函数后续再接新数据时只需要传数组不用每次重新分析。说到字符串排序基数排序也适用不过要先把字符串补齐到同样长度。短字符串可以认为尾部是空字符排序时空字符排在最前。处理方式是按字符的 Unicode 编码作为“位”每一轮从左到右或者从右到左都行LSD 版本一般从最后一位开始。面试里出现过“给十万个长度相同的字符串排序”的题答案就是用基数排序。还有一种很常见的结合玩法桶排序和基数排序混用。第一轮用高位分桶把数据粗分成几个大区间第二轮在每个桶内做基数排序或计数排序。这种组合在分布式场景中特别实用比如需要把海量数据按范围分片到不同机器排序再用桶间的天然顺序做全局 merge。思想还是线性排序那一套利用数据的位置而不是把时间全耗在比较上。从我个人经验来看真正写出一个能稳定跑在 O(n) 的排序并不难难的是确认当前场景配得上这个 O(n)。数据范围不够集中、分布不够均匀、位数不够固定都可能让线性排序变成“耗时又耗内存”的负优化。所以每次动手前先花一分钟看清数据和业务约束再决定要不要用线性排序。这比多背几种排序模板更重要。