线性时间排序：计数、基数与桶

05-排序与检索进阶预计 20 分钟计数排序基数排序桶排序非比较

学习状态：

一句话定义

计数排序（Counting Sort）用「值域计数数组」直接定位元素位置（O(n+k)，k 为值域宽）；基数排序（Radix Sort）按位把多轮稳定的计数排序串起来（O(d(n+k))，d 为位数）；桶排序（Bucket Sort）按值域均匀分桶、桶内再排（均匀分布下期望 O(n)）——三者都绕开「两两比较」，从而绕开 n log n 下界。

为什么重要

它们是下界的「出口示范」：限制条件一变（整数、值域已知、分布均匀），线性时间立刻可达。工程里它们并不边缘：Java 对小整数组的排序、后缀数组构造、数据库对枚举列的排序、GPU 排序都以基数排序为骨架。同时它们训练一个关键习惯——先审数据假设，再选算法。

前置知识

kp-020（比较下界，作为被绕开的对象）；kp-002（复杂度计数）。

核心概念

计数排序：统计每个值出现次数 → 前缀和求「严格小于该值的元素数」（即输出起始位置）→ 倒序遍历原数组写入输出数组以保稳定。
稳定性在计数排序里不是装饰：它是基数排序每轮的必要条件——低位排好的相对序必须被高位轮保留。
基数排序（LSD）：从最低有效位到最高位，每轮一个稳定排序（通常计数）；d 轮后全序。
MSD 基数排序：从最高位分桶递归，适合变长字符串。
桶排序：把 [0,1)（或已知值域）均分 n 个桶，元素落入桶后桶内插入排序；期望 O(n) 依赖「均匀分布」假设；最坏全落一桶退化为 O(n²)。

原理与机制

线性排序的机制是「用值当地址，不做比较」：计数排序先数每个值的出现次数，再用前缀和算出各值的输出区段，回写时倒序遍历以保持稳定——稳定是它的生命线，因为 LSD 基数排序靠「低位轮的相对序在高位轮中不被打乱」逐位累积出全序；桶排序则把同样的定位思想交给概率：均匀分布下每桶期望常数个元素，桶内小排序代价总和保持线性。

直观类比

计数排序：选举计票——先数出每个候选人的票数，再按名单顺序把票「按位置还原」，根本不需要两两比较谁先谁后。基数排序：图书馆按「年-月-日」排档案，先按日排（稳定），再按月排，最后按年排——因为每轮都稳定，日内的顺序在按月排时不会乱。桶排序：身高排队先按「年段」分堆，堆内再细排。

公式或模型

计数排序：三趟线性扫（计数、前缀和、回写），T(n,k) = Θ(n + k)。
LSD 基数：d 位、每轮值域 k ⇒ Θ(d(n + k))；32 位整数按 8 位/轮 ⇒ d=4、k=256，总计 Θ(4(n+256)) ≈ Θ(n)。
桶排序期望：桶 i 内元素数 nᵢ，E[Σ nᵢ²] = O(n)（均匀分布），故期望 Θ(n)；最坏（全落一桶）Θ(n²)。

图示

计数排序过程（值域 0–4）：

输入:      [2, 0, 2, 1, 3, 0]
计数:      值:   0  1  2  3  4
           次数: 2  1  2  1  0
前缀和(终点):2  3  5  6  6   ← 值 v 的最后写入位置
倒序回写(保稳定):
  0→位置1 ; 3→位置5 ; 1→位置2 ; 2→位置4 ; 0→位置0 ; 2→位置3
输出: [0, 0, 1, 2, 2, 3]

实例或案例

年龄/成绩排序（值域窄）：计数排序一题到底；LeetCode「颜色分类」计数变体。
32 位整数海量排序：LSD 基数 4 轮 × 256 桶，缓存友好，常数远小于快排——数据库与排序基准赛常客。
后缀数组倍增构造：每轮对「(rank[i], rank[i+k]) 二元组」做基数排序，O(n log n)。
浮点均匀分布（如粒子坐标）：桶排序 + 小桶插入排序。

常见误区

回写时正序遍历：破坏稳定性，多轮基数排序时结果直接错误——必须倒序。
值域 k 巨大仍用计数排序：内存 O(k) 爆炸，应改桶/基数或回到比较排序。
认为「线性排序推翻了下界」：下界在比较模型内成立；线性排序靠「不比较、按值定位」绕开模型，假设不可比。
基数排序排字符串时轮数按「最长串」计而不按实际字符分布：对定长整数成立，对变长数据要 MSD 或按需终止。

自测题

手推 [1,0,2,1,0] 的计数排序全过程（值域 0–2）。

答案要点：计数 [2,2,1] → 前缀 [2,4,5] → 倒序回写得 [0,0,1,1,2]。

32 位无符号整数用 LSD 基数排序：选每轮几位？共几轮？为何位宽不是越小越好？

答案要点：常 8 位/轮、4 轮；轮数变多（如 4 位则 8 轮）总代价 d(n+k) 中 d 增大，缓存与常数变差，8 位是工程折中。

桶排序什么时候退化？如何缓解？

答案要点：分布严重不均全落一桶退化为桶内比较排序的 O(n²)；缓解：桶数 ≈ n、桶内换插入/快排，或对分布建模（直方图重分桶）。

与其他知识点的关系

kp-020 的下界是其出发点；kp-023 外排的整数排序可用基数排序造有序 run；kp-031 位运算提供「取某 8 位」的实现（(x >> s) & 0xFF）；kp-009 的散列思想与「按值分桶」同构。

延伸阅读

《算法导论》第 8 章（8.2–8.4）；Sedgewick《算法（第 4 版）》第 5.1 节（字符串排序的 MSD/LSD）。

前置知识点

比较排序全景与 n log n 下界核心