计数排序、桶排序、基数排序：三种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 的计数数组。第一遍扫描后得到：

如果只是把次数展开成[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_buckets=None): 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 = 256，d 变小但每组计数数组变长。这是时间和空间的权衡。

经典教科书里，如果输入是 32 位整数，最大位数 d 是一个固定常数，所以可以认为复杂度是 O(n)。但实际工程中，如果数据时从 1 到 10^18，d 可能是 19，这时候常数就不小了，可能和 O(n log n) 的常数差不多。所以不要把“常数”真当成零。

负数处理是基数排序的经典坑。按位取模时，负数的最低一位也是负数，直接进计数数组会越界。常见做法有两种：

一是把整个数组整体偏移，让最小值变成 0。比如最小值为 -500，把所有元素加 500 后排序，最后再减回来。这个方案简单，但会破坏数据本身的语义，适合纯数值排序。

另一种更规范的做法是把正数和负数分开，负数部分取绝对值后做基数排序，再反转顺序放到结果前面；非负数部分正常排序放到后面。因为对于负数来说，绝对值越大，原数越小。这个方案不改变数据，也保持了稳定性。我在自己的工具函数里更推荐第二种。

5. 怎么选、踩坑与实战建议

5.1 一张表理清选型

做技术选型时，我习惯先看数据范围，再看数据分布，最后看是否要求稳定性。三种线性排序的区别，浓缩成一张表：

这里的 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)。数据范围不够集中、分布不够均匀、位数不够固定，都可能让线性排序变成“耗时又耗内存”的负优化。所以每次动手前，先花一分钟看清数据和业务约束，再决定要不要用线性排序。这比多背几种排序模板更重要。