非比较排序突破O(n log n)：计数、基数、桶排序详解与实战

前两篇文章我们聊完了插入排序、快速排序这类基于“比较”的算法，也给出了各自的复杂度结论。这第三篇我想换个完全不同的角度：既然比较排序的最优下界是 O(n log n)，那有没有办法直接绕开“比较”这件事，把时间复杂度拉到 O(n)？答案是肯定的，而且不止一种。计数排序、基数排序、桶排序就是三种典型的非比较排序，它们的共同特点是利用数据本身的分布特征，把元素直接送到“该去的位置”上，而不是靠两两比较来寻找顺序。这篇文章适合已经掌握基础排序、但想知道“O(n) 排序到底怎么实现、有什么限制、实战里怎么选”的读者，我会把原理、完整代码、复杂度推导和踩坑经验一次讲透。

1. “O(n log n) 天花板”成立的前提：只要你不去比较，就能绕过去

1.1 决策树结论的正确打开方式

很多教程都会告诉你：基于比较的排序算法，最好也就是 O(n log n)。这个结论本身没问题，但它有一个非常容易被忽略的前提——“基于比较”。如果算法每一步都通过“a 和 b 谁大谁小”来获取信息，那么信息量就只能靠二元比较来积累，而 n 个元素可能的排列一共有 n! 种，一颗二叉树至少要 log2(n!) 层才能区分所有这些情况，所以下界是 O(n log n)。

我见过不少初学者被这句话吓住，以为“排序不可能更快”是物理定律。其实它只是描述了一类算法的极限，就像你不坐飞机就没办法几小时横跨大洋一样，但你可以坐飞机。非比较排序就是那架飞机：它不依赖“比较”来传递大小信息，而是利用数据的“地址特性”，直接把每个元素放到它该在的位置上。

所以下次再有人说“排序不可能突破 O(n log n)”，你可以先问一句：允许用非比较算法吗？允许的话，计数、基数、桶排序都能在不同条件下达成线性复杂度。关键不再是“能不能 O(n)”，而是“你的数据是什么形态”。

1.2 非比较型算法的共同套路：直接把数据放到“该去的位置”

如果我们要给一队人按身高排队，比较型算法是让两个人两两比身高、然后交换位置。非比较型算法则更像是：先量好每个人的身高，然后告诉每个人“你站到第 X 号位去”。只要“X 号位”能算得出来，一次放置就能得到一个有序序列。

这里有三个典型的“定位方式”：

• 计数排序：值的范围很小，那就把值本身当作下标。数值是 5，就往数组下标 5 的位置放。
• 基数排序：值范围太大，但位数有限，于是按位分组，先放低位再放高位，每一轮都是一次轻量级的计数放置。
• 桶排序：值范围很大且连续，但分布均匀，就把整个区间切成若干个桶，先按大小丢进对应桶，再对桶内做常规排序。

这三个算法没有一个是在“比较大小”，它们做的是“映射 + 放置”。这也是它们能突破 O(n log n) 的根本原因。但请注意，“放置”的前提是有一个可以计算的映射关系，这就引出了每个算法的适用边界。

1.3 三个算法的入场券：范围小、位数少、分布均匀

光说“不比较”还不够，你得清楚每个算法的数据前提是什么，否则写出来不是报错就是退化成套娃式排序。

• 计数排序要求数据是有限范围内的整数，最好范围 k 和元素个数 n 在同一量级。如果 k 是 10^9，你总不能开一个 10 亿长度的数组。
• 基数排序要求数据能拆成固定位数的“位”（或字符），并且每一位的基数有限。比如十进制整数每一位只有 0~9，那基数就是 10。它通过“多轮小计数”来解决“范围大”的问题。
• 桶排序要求数据在区间内大致均匀分布。你按 n 个桶切分区间，均匀分布时每个桶里大约只有一个元素，桶内排序成本很低，总代价接近线性。如果数据全挤在同一个桶里，桶排序就退化成了“一次快排加一个循环”，复杂度跟着桶内算法走。

我把这三个前提编成一句话：小范围找计数，大范围按位拆，连续均匀拿桶装。后面每一节我都会围绕这句话展开细节。

2. 计数排序：把数值当数组下标，代价是内存换时间

2.1 先说清楚它到底解决了什么问题

计数排序最典型的场景是：对一批成绩（0~100 分）做排名，或者给一批年龄（0~120）做统计。这些数据的特点是取值范围很小、可以天然映射成数组下标。你不需要知道元素之间的大小关系，只需要数一数“每个值出现了多少次”，然后再把这些次数“展开”成有序序列。

我最早接触这个算法时有一个困惑：单纯统计频次之后，怎么还原成有序数组？比如 [3, 1, 3, 2]，统计结果是 1 出现 1 次，2 出现 1 次，3 出现 2 次，那我当然可以输出 [1, 2, 3, 3]。但如果待排序对象不是单纯数字，而是“数字加上一堆附属信息”的记录，比如每个成绩对应一个学生姓名，我就不能只输出数字列表，我必须保证“同名次的记录，在排序前后相对顺序不变”。这就是计数排序要引入前缀和的原因，也是它相对“统计后直接展开”的高级之处。

此外，计数排序并不是只能排从 0 开始的正整数。通过对整体做偏移，它可以处理负数；通过对每个值保存“卫星数据”，它可以排序结构化记录。它的本质是：用一块长度为数值范围的计数数组，记录每个值的出现次数，然后利用前缀和确定每个元素的最终位置。

2.2 稳定版计数排序的实现：前缀和不是可有可无的东西

先说结论：如果只是给整数排序，不要求稳定，那么统计频次后直接展开就够用了。但实际工程里“稳定性”常常很重要，尤其是用非比较排序做基数排序的轮子时，我不知道你有没有写过这样的版本：

def counting_sort(nums): if not nums: return nums max_val = max(nums) min_val = min(nums) # 处理负数：整体平移，让最小值映射到 0 offset = -min_val k = max_val - min_val count = [0] * (k + 1) for x in nums: count[x + offset] += 1 # 计算前缀和 for i in range(1, len(count)): count[i] += count[i - 1] res = [0] * len(nums) # 反向扫描保证稳定性 for x in reversed(nums): idx = x + offset count[idx] -= 1 res[count[idx]] = x return res

这里最关键的一步是前缀和。count[i] 经过累加之后，表示“小于等于 i 的元素一共有多少个”。假设 count[i] = 5，那就说明值加偏移量为 i 的元素，在结果数组里的最后位置应该是下标 4（因为还有 4 个比它小的元素排在前面）。

此时如果你正着扫描原数组，同一个值的多个元素会把位置“从后往前”占用还是“从前往后”占用？答案是：如果你在放置后立即把 count[i] 减一，那么后面再遇到同值元素时，它会放在前一个元素的前面，相对顺序就反了。而反向扫描则保证：先处理靠后的元素，让它占住靠后位置；再处理靠前的元素，放在它前面。这样相同值的元素保持了原有的前后顺序，也就是稳定排序。

为什么要纠结稳定性？因为在基数排序里，每一轮对“某一位”的排序都必须稳定，否则上一轮排好的低位顺序会被这一轮打乱。计数排序的稳定性就是基数排序的基石。

2.3 实际写码会遇到的三件事：负数、大范围、重复值

计数排序的代码看上去很短，但实际使用时坑不少，我把几个高频问题列出来：

第一，负数怎么处理。最简单的办法是整体平移，把所有数映射到非负整数域。上面的代码里我用 offset 把最小值平移为 0，排序结束后如果需要原始值，再减回 offset 即可。注意如果原数组同时存在几十万和负几百万，平移后的范围会很大，这时你要考虑是否该换基数排序。

第二，大范围怎么防内存爆炸。我见过有人给一批 32 位整数做计数排序，max_val 是 21 亿，于是 count 数组开到 21 亿长度。一个 32 位整数的 count 数组占 8GB 内存，瞬间把某台开发机搞崩了。核算公式很简单：count 数组长度是 max-min+1，每个元素如果是 4 字节，那么大约 4 × k / 1024 / 1024 = MB 数。k 到 1000 万时就已经接近 40MB，还能接受；k 到 1 亿就是 400MB，绝大多数服务端场景已经扛不住。所以当 k 远大于 n 时，计数排序不划算，这是选择算法时首先要算的账。

第三，重复值多的场景要检查边界。如果所有元素都相同，count[0] 会累加到 n，反向扫描时 count 逐步减到 0，恰好把所有元素放在 res 前 n 个位置。这个逻辑本身没错，但如果你在别处加了“如果 count[i] > 0 就输出”的展开写法，就要小心别把空位置输出来。我建议统一用“前缀和 + 反向放置”这版实现，既保证稳定，又天然处理重复值。

3. 基数排序：用“多轮小数范围的稳定排序”拼出大范围有序

3.1 LSD 思路：先排低位，为什么最后一定是整体有序

基数排序有两种方向：从最高位开始（MSD）和从最低位开始（LSD）。工程里更常用 LSD，因为实现简单且稳定性有保证。它的核心思路是：先按个位排序，再按十位排序，再按百位排序……每一轮都基于上一位排好的顺序，做一次稳定排序。等所有位都处理完，整个数组就是有序的。

初看这个流程会觉得反直觉：先排低位有什么意义？个位小的数未必整体小啊。这里的奥妙在于“多轮稳定排序的累加效果”。用一个例子说明：假设要排序 12、34、23。

• 第一轮按个位排：2、4、3，所以顺序是 [12, 23, 34] 按个位看是 [2, 3, 4]。
• 第二轮按十位排：1、2、3，稳定排序会保持上一轮个位相对顺序。结果是 [12, 23, 34]，正好有序。

再看一个稍微复杂的例子：11、13、21、23。

• 个位排序后：[11, 21, 13, 23]
• 十位排序后：十位为 1 的有 11 和 13，它们保持个位排序后的相对顺序（11 在前）；十位为 2 的有 21 和 23，也保持原相对顺序。结果 [11, 13, 21, 23]。

为什么 LSD 正确？因为每一轮都处理更高一位，而这一轮是稳定的，所以对于高位数相同的元素，它们之间的顺序由低位已经排好的顺序决定。等最高位排完，高位数不同的一定按高位数分开，高位数相同的内部又已经有序，全局自然有序。这个正确性靠的是“稳定”这个性质的逐轮累积，不是靠某个位置上的直觉。

3.2 复杂度细算：为什么是 O(d(n+k))，而不是 O(n)

很多地方直接写基数排序复杂度是 O(d(n+k))，这里的 d 是位数，k 是基数。以十进制整数为例，基数 k = 10，每一轮相当于对 n 个元素做一次计数排序，代价 O(n + k)。总共有 d 轮，所以整体 O(d(n + k))。如果数据范围是 0 到 99999，d = 5，k = 10，那么 O(5n)，确实线性。

但要注意，如果你把基数从 10 改成 256，k 会变大到 256，但 d 会变小。比如 32 位无符号整数，基数为 10 时需要约 10 轮；基数为 256 时只需要 4 轮。这里就出现了“轮数与基数”的权衡：基数越大，一轮代价越高，但轮数越少。理论上如果 k 过大，基数排序会退化成近似计数排序；如果 k 太小，轮数又太多。实际工程里，基数设为 2 的幂（比如 256 或 65536）最省时间，因为位运算比取模快得多，同时每轮内存占用也可控。

我实际写的时候习惯用按 256 处理，原因是可以用(x >> (8 * shift)) & 0xFF拿到当前位，速度明显优于(x // (10**shift)) % 10。这里需要说清楚：所谓“O(n)”，是假设 d 和 k 都是常数。如果输入数据的位数随数据规模增长，比如排任意长的大整数，那 d 就不是常数，整体就不是严格 O(n) 了。所以基数排序一个隐藏前提是“位数有限且可预测”。

3.3 代码之外的问题：负数、字符串、基数怎么选

以下是一个可运行的优化版基数排序，我用按字节处理的方式避免取模：

def counting_sort_by_byte(nums, byte_idx): # 统计各字节值出现次数 cnt = [0] * 256 for x in nums: shift = byte_idx * 8 d = (x >> shift) & 0xFF cnt[d] += 1 for i in range(1, 256): cnt[i] += cnt[i - 1] res = [0] * len(nums) for x in reversed(nums): shift = byte_idx * 8 d = (x >> shift) & 0xFF cnt[d] -= 1 res[cnt[d]] = x return res def radix_sort(nums): if not nums: return nums min_val = min(nums) # 整体偏移，处理负数 shifted = [x - min_val for x in nums] max_val = max(shifted) total_bytes = (max_val.bit_length() + 7) // 8 if total_bytes == 0: total_bytes = 1 arr = shifted for byte_idx in range(total_bytes): arr = counting_sort_by_byte(arr, byte_idx) return [x + min_val for x in arr]

这里有两个容易踩的坑：

负数处理。我一开始直接对负数做移位，结果发现 -1 的二进制补码是 0xFFFFFFFF 这种形式，按字节排序会把负数排到正数后面。简单避开的方法是先把所有数整体平移到非负区间，排序后再平移回来。要注意平移之后数值可能超出 32 位范围，但在 Python 这种任意精度整数面前没有溢出问题，其他强类型语言要小心选大整数类型。

字符串能不能排？可以。字符串相当于“字符位的基数排序”，从最后一个字符往前排，每个字符用 Unicode 码点或字节值作为基数。但变长字符串要先统一长度（填充到最长长度或按终止符处理），否则长度短的会被当成有特殊终止符，这是个经典易错点。如果只是排一批固定长度的字符串，基数排序非常快；对变长字符串，我一般先按长度分桶，再在每个长度组内做基数排序，两头都能保证线性。

4. 桶排序：分布式思维的线性期望，前提是数据足够“雨露均沾”

4.1 分桶逻辑与桶内排序选型

桶排序的思路和计数排序有点像：都是“先把元素分配到不同的容器里”。但计数排序的容器是“每个值一个位置”，桶排序的容器是“每个区间一个桶”。你先根据数据的取值范围切出 n 个等宽区间，然后遍历元素，把它丢进对应的桶。等所有元素都进桶后，每个桶内部做一次排序，最后按桶的顺序拼起来就是整体有序。

分桶逻辑很简单：遍历数组，对每个 x，令bucket_idx = int((x - min_val) / width)，width 是区间宽度。这里最容易出问题的是边界落在桶档上的问题：一个元素刚好等于某个桶的上界，应该放到哪个桶？如果某个桶区间是 [min + i*w, min + (i+1)*w)，那么元素等于右边界时会被分到下一个桶，但最大值 max_val 本身呢？如果不做处理，max_val 会被分到下标等于桶数量的索引，直接越界。我习惯用min(int((x - min_val) / width), n - 1)这种写法把最大值强制落到最后一个桶。

桶内排序选哪种？理论分析通常假设桶内用插入排序，因为桶内预期元素数量很少，插入排序常数极小。但工程上我直接调用语言内置排序会更稳，内置排序在小数组上通常足够优秀。要注意的是：如果数据分布不均匀，某个桶里塞了成千上万个元素，桶内排序的开销就会暴涨。所以桶排序的“均匀性假设”是所有细节里最重要的一条。

4.2 期望复杂度的直觉推导：为什么说平均是 O(n)

很多人不理解：桶排序内部还要对每个桶做排序，怎么就是 O(n) 了？关键在“每个桶里元素数量期望是常数”。假设 n 个元素均匀随机地落在 [min, max] 区间，切成 n 个等宽桶，那么每个桶收集到的元素数量大致服从二项分布，期望值是 1。这个“1”是 O(n) 的来源。

我们来算一笔账：假设每个桶内用插入排序，单个桶里有 b_i 个元素，桶内排序代价 O(b_i²)。总代价是 sum(b_i²)，而均匀分布下 b_i 的期望是 1，二阶矩也是常数，所以 sum(b_i²) 的期望是 O(n)。如果再平衡一点，用“分桶后直接按顺序拼接”的应用场景（比如浮点数均匀分布），甚至桶内可以不做排序或者只做很少的比较。

但这里必须诚实地说：最坏情况不是 O(n)。如果所有元素落在同一个桶里，那 sum(b_i²) = n²，复杂度退化到 O(n²)。所以桶排序在理论分析中常被描述为“平均 O(n)，最坏 O(n²)”。这也是它和计数排序、基数排序最大的差别：后两者在满足整数位数条件下是严格的线性最坏情况，桶排序只能保证期望线性。如果你的数据分布不可控，或者你没法提前估计分布形态，桶排序风险很大。

4.3 一个浮点数的可运行示例与调参记录

下面这段代码适合排[0.3, 0.1, 0.7, 0.5, 0.9]这类浮点数组：

def bucket_sort(nums): if not nums: return [] n = len(nums) if n == 1: return nums min_val = min(nums) max_val = max(nums) if min_val == max_val: return nums span = (max_val - min_val) / n buckets = [[] for _ in range(n)] for x in nums: idx = min(int((x - min_val) / span), n - 1) buckets[idx].append(x) for b in buckets: b.sort() res = [] for b in buckets: res.extend(b) return res

我实测的一个小例子：给 20 个 0~1 之间的随机浮点数排序，桶数为 20，最大桶内元素是 3 个，桶内排序几乎瞬间完成。但如果我把输入换成一堆 0.01、0.02、0.03……这种等差数据，再按等宽分桶，每个桶里也还是均匀分布，反而很快。真正让它变慢的是“大量元素集中在一个窄区间”，比如 90% 的数都在 0.45~0.55 之间，此时绝大多数元素挤进 1~2 个桶，桶内排序反而成为瓶颈。

所以我的建议是：用桶排序前，先想清楚输入分布到底长什么样。如果分布未知，用基数排序或直接快排更稳。如果分布相对均匀（随机数、测量值、模拟数据），桶排序往往能在同样 10 万级数据上比标准库快排快 20%~40%，因为没有那么多递归比较开销。内存方面，桶排序需要额外 O(n) 的空间存桶，而且每个桶又是动态数组，实际峰值内存比理论 O(n) 更大，这也是一个常被忽略的点。

5. 场景对照与实测踩坑：别再对着理论复杂度直接选算法

5.1 三个典型业务场景，分别该用谁

理论讲完了，回到真实工程里最常见的几个需求。我挑三个最近做过的项目场景来说。

• 场景 A：给 300 万条学生成绩排序，成绩范围固定 0~100 分整数。这种场景计数排序是最优解。k 只有 100，count 数组 400 字节，内存忽略不计，时间复杂度 O(n)。我实际跑下来，300 万数据计数排序耗时大概是快速排序的 60%，而且代码稳定不需要递归，还能顺带统计成绩分布直方图，一鱼两吃。
• 场景 B：给一批 15 位手机号排序。这是典型的固定长度字符串/整数场景，基数排序就好用。每一位按 0~9 分 10 个桶，但更省内存的做法是按 3 位数字一组用 1000 作为基数，或者按字节处理 15 位字符串。我用基数排序处理 100 万手机号，耗时远低于快速排序因为每轮都是顺序扫描加轻量计数。
• 场景 C：给 50 万个 float 类型的相似度分数排序，分数来源是模拟系统产生的随机相似度，分布相对均匀。这是桶排序的主场。我把区间按桶数切成 50 万个桶，绝大多数桶里只有 1~2 个元素，桶内排序开销可以忽略。如果分数分布高度偏斜，我会立刻换成基数排序处理浮点数的字节表示或退化到快排。

场景选型表可以总结成下面这样：

5.2 内存峰值和缓存不友好：理论 O(n) 反而更慢的现场

我以前总觉得 O(n) 算法肯定比 O(n log n) 快，直到有一次给一台老机器排 500 万个随机 32 位整数，基数排序居然比快速排序还慢。排查后发现两个问题。

第一个是内存峰值。基数排序每一轮都需要一个等长的临时数组，算上计数数组和原数组拷贝，峰值内存是 2n 以上。500 万整数本身约 20MB，临时翻倍后 40MB，看起来不多，但频繁分配和拷贝触发了垃圾回收，直接拖慢速度。后来我复用同一个临时数组，每轮只在两个数组间交换数据，内存峰值降到 n 的级别，速度立刻上来了。

第二个是缓存不友好。非比较排序的数据访问模式是“按值跳转”：每次把元素放进 count 或 bucket，下标取决于元素值，而不是顺序地址。当 n 很大的时候，随机访问内存的 cache miss 代价非常可观，反而抵消了比较次数的优势。快速排序虽然比较次数多，但它的数据访问是局部连续的，缓存命中率高许多。所以在 1000 万级别以上的随机数据中，精心优化的快速排序常常能跑赢没有做过缓存优化的基数排序。这不是算法复杂度失效，而是内存层次结构在起作用。

我后来总结的实测结论是：数据量在一万到百万级别，且数据满足各自前提时，这三种 O(n) 算法确实有明显优势；数据量上千万、分布又不满足前提时，先测一下内置排序的基线，再决定要不要手写这些算法。工程师要先看常数和瓶颈，而不是只看大 O。

5.3 一个简单的判据流程：3 个问题定算法

如果在写代码前不想做复杂分析，我推荐一个三个问题的判据：

1. 数据是整数吗？不是整数，看分布是否均匀；均匀选桶排序，不均匀直接内置排序。
2. 整数范围小吗？比如范围 k 小于 n 的 10 倍，计数排序优先，内存算得过来就行。
3. 范围大，但位数固定可以拆吗？能拆成有限的位或字符，就用基数排序；不能拆就用快排。

这个流程是我自己在实际项目中总结的，虽然简单，但能避开绝大多数瞎选导致的问题。记住：O(n) 是有条件的线性，不是无条件的线性，条件满足才成立。

6. 关于这几种排序，最后再分享几条我的实战体会

写到这里，这篇文章的主要篇幅已经说完了，但我想额外提一个很多人忽略的细节：三种非比较排序都很适合“半在线”场景。比如计数排序过程中你会得到频率分布，桶排序过程中你会得到分布直方图，基数排序每一轮会产生中间有序序列。如果业务还需要“排序后的统计信息”，这三种算法经常能一次遍历同时完成两件事，这是快排做不到的。

另一点是：非比较排序之间可以组合使用。我做一个模拟项目时遇到过“浮点数 + 需要稳定排序 + 数据量巨大”的需求，单用桶排序不稳定，单用基数排序要处理浮点字节顺序，最后我的方案是先按大区间做桶排序，再对桶内元素用基数排序处理字节表示。实测效果不错。排序算法不是孤岛，组合使用往往比坚持某一个更有效。

最后一个实用建议：不要在你的代码里手写这些算法去替代标准库排序，除非你有明确的性能测试数据支撑。标准库的排序在绝大多数情况下已经优化得非常好，尤其内置快排的常数极小。只有当你的数据明确满足计数排序、基数排序或桶排序的前提，并且你做了基准测试确认收益，才值得引入这些实现。毕竟，工程里“确定能用”比“理论上更快”更重要。如果你被哪段实现卡住了，欢迎按上面代码跑一跑，多调几组不同分布的数据，就会对“为什么需要那些前提条件”有更直观的感受了。