计数排序、桶排序、基数排序是怎么做到 O(n) 的？它们有什么限制？

简化版

它们是非比较排序,不靠元素间比较,而是利用元素的值本身当索引或分组依据,所以能突破比较排序 O(n log n) 的下界、做到 O(n) 级。计数排序:统计每个值出现次数,按值域顺序输出;桶排序:按值分到若干桶、桶内排序再拼接;基数排序:按位(个、十、百…)逐位做稳定排序。限制:都要求元素能映射到有限、可控的值域(通常是整数或定长串),值域太大就不划算。

详细版

计数排序(Counting Sort)

int[] countingSort(int[] a, int maxVal) {
    int[] count = new int[maxVal + 1];
    for (int x : a) count[x]++;              // 统计每个值出现次数
    int[] res = new int[a.length]; int idx = 0;
    for (int v = 0; v <= maxVal; v++)        // 按值从小到大输出
        while (count[v]-- > 0) res[idx++] = v;
    return res;
}

O(n + k),k 是值域大小。适合值域小的非负整数(年龄、分数)。

桶排序(Bucket Sort)

把数据按值范围分到若干个「桶」,每个桶内部再排序(常用插入排序),最后按桶顺序拼接。数据均匀分布时接近 O(n),分布不均时退化。

基数排序(Radix Sort)

把整数按位处理:先按个位用稳定排序(通常计数排序),再按十位、百位……从低位到高位逐位排完,整体就有序了。O(d·(n+k)),d 是最大位数。适合整数或定长字符串。

完整版教学

一、为什么非比较排序能突破 O(n log n)

比较排序的下界是 Ω(n log n),因为它只能通过「谁比谁大」获取信息,n! 种排列至少需要 log(n!) = Ω(n log n) 次比较。非比较排序换了个信息来源:它不问「a 比 b 大吗」,而是直接利用元素的值——把值当数组下标(计数)、当分组依据(桶)、当逐位关键字(基数)。因为绕开了「比较」这个瓶颈,它们不受 Ω(n log n) 约束,能做到线性。代价是通用性下降:必须能把元素映射到有限值域。

二、计数排序:用值当下标

计数排序的核心是「开一个以值为下标的计数数组」:

遍历原数组,count[值]++,统计每个值出现多少次。
从小到大遍历 count,把每个值按出现次数依次写回。

因为值直接当下标,不需要任何比较,时间 O(n + k)(n 遍历原数组、k 遍历计数数组)。

适合:值域 k 不大的非负整数(如 0~100 的分数、年龄)。
不适合:值域巨大(如存 int 全范围,要开 40 亿的数组)——空间会爆炸。所以计数排序的适用前提是「k 和 n 同量级或更小」。
稳定版:用「前缀和」确定每个值的输出位置,从后往前填,可保证稳定。

三、桶排序:分而治之的值域划分

桶排序把值域划分成若干区间,每个区间一个「桶」:

遍历数据,按值把每个元素分到对应的桶。
对每个桶内部排序(桶内元素少,用插入排序等)。
按桶的顺序依次拼接,就是有序结果。

如果数据均匀分布,每个桶只有常数个元素,桶内排序 O(1),整体接近 O(n)。但如果数据都挤在一个桶里,就退化成桶内排序的复杂度(最坏 O(n²) 或 O(n log n))。所以桶排序的效率依赖数据分布是否均匀。它常用于浮点数排序(如 [0,1) 均匀分布的小数)。

四、基数排序:逐位稳定排序

基数排序处理整数(或定长字符串),按「位」来排:

先按最低位(个位) 排序,再按十位、百位……一直到最高位。
每一位的排序必须用稳定排序(通常是计数排序)——这样高位相同的元素,能保持低位已经排好的顺序。

这叫 LSD(最低位优先)。因为每一位用 O(n+k) 的计数排序,共 d 位,总时间 O(d·(n+k))。

为什么从低位到高位、且每位必须稳定?因为「先排低位」的结果要靠「后排高位时的稳定性」来保留。如果高位排序不稳定,低位排好的顺序就被打乱了,结果就错。这是基数排序对稳定性依赖的关键。

五、三者的限制与选择

它们都很快,但都有使用前提,不是万能的:

计数排序:值域 k 不能太大(空间 O(k));只适合整数/可离散化的键。
桶排序:依赖数据均匀分布,分布差会退化;需要额外空间放桶。
基数排序:适合整数或定长串;位数 d 大时优势减弱;每位排序要稳定、需额外空间。

怎么选:值域小的整数用计数;均匀分布的浮点数用桶;位数不多的大整数/定长字符串用基数。一旦数据是任意可比较对象、或值域巨大,还是得回到比较排序(快排/归并)。

六、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：每个阶段按键的可枚举结构分配元素，并保留此前已经建立的次序。

对应的状态推进是：计数按值映射，桶排序按值域分段，LSD 基数排序从低位做稳定排序。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。计数 O(n+k)；基数 O(d(n+r))；桶排序复杂度取决于分布和桶内算法。

带数字走一遍：100 万个 0–120 的年龄只需 121 个计数槽，32 位全值域则不可行。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	仅在值域、位数或分布满足约束时才能优于比较排序
时间复杂度	不是无条件 O(n)，必须带上 k、d、r 等参数
额外空间	通常 O(n+k) 或 O(n+r)
关键边界	负数需做偏移；稳定计数要反向回填；LSD 每一趟必须稳定
替代方案	无可利用键结构时回到比较排序

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

七、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“仅在值域、位数或分布满足约束时才能优于比较排序”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写不是无条件 O(n)，必须带上 k、d、r 等参数就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“计数 O(n+k)；基数 O(d(n+r))；桶排序复杂度取决于分布和桶内算法”。
误区：重复值和边界值不会改变代码。 负数需做偏移；稳定计数要反向回填；LSD 每一趟必须稳定。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“每个阶段按键的可枚举结构分配元素，并保留此前已经建立的次序”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“100 万个 0–120 的年龄只需 121 个计数槽，32 位全值域则不可行”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“无可利用键结构时回到比较排序”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

八、加强记忆

计数/桶/基数是非比较排序,靠利用值本身(当下标/分组/逐位键)而非比较,突破 Ω(n log n) 到 O(n) 级。计数:以值为下标统计次数,O(n+k),适合小值域整数;桶:按值分桶、桶内排序再拼,均匀分布时 O(n);基数:从低位到高位逐位用稳定排序(计数),O(d(n+k)),适合整数/定长串。三者都稳定,但都要求值能映射到有限值域——值域大或任意对象就用比较排序。

简化版

详细版