选型与应用场景
基于通用算法套路 · 核于 2026-07
速查
- 选型三问：①数据是整数且值域小吗？→ 计数；②数据分布近似均匀吗（尤其浮点）？→ 桶；③数据有固定位数可按位分解吗（手机号/字符串）？→ 基数；都不满足 → 退回比较排序。
- 计数排序的黄金场景：值域
k = O(n)的整数或可映射为整数的类型——年龄（0~150）、考试分数（0~100）、字符 ASCII（0~127）。只要k不大，计数排序是这几种数据的最快解。 - 桶排序的黄金场景：值域连续且分布近似均匀的浮点数（如
[0, 1)均匀分布），桶数m = Θ(n)时期望 O(n)；也适合「值域大但分布均匀」无法直接计数的场景。 - 基数排序的黄金场景：固定位数的多关键字——手机号（11 位）、身份证号、定长字符串字典序、IPv4 地址（4 段 8 位）。位数
d是常数时 O(d · n) ≈ O(n)。 - 稳定性速查：计数排序（倒序放）稳定；基数排序（每趟稳定）稳定；桶排序取决于桶内排序——桶内用插排则稳定，用快排则不稳定。
- 局限性铁律：值域
k大时计数排序空间O(k)爆炸；分布倾斜时桶排序退化到 O(n²)；位数d大或不可拆位时基数排序失效——前提不满足就退回比较排序。 - 负数处理：计数排序统一减
min做偏移把值域平移到[0, k)；基数排序负数需单独分组（按补码或绝对值分别处理），通常更推荐计数偏移法。 - 实际应用：①计数/基数排序作为子例程出现在字符串排序、后缀数组构造；②LSD 基数用于定长字符串字典序（旧式卡片机排序的遗产）；③MSD 基数用于变长字符串前缀排序；④桶思想用于均匀分片的负载均衡 / 哈希分桶。
- 工程现实：各语言默认排序仍是比较排序或其混合（Timsort / 内省排序 / 双轴快排）——非比较排序只在「值域小整数」这类确定满足前提的场景才登场。
一、何时用计数排序：值域小的整数
判定条件：数据是整数（或可一对一映射为整数），且值域 k 与元素数 n 同阶或更小（k = O(n)）。
为什么：计数排序时间 O(n + k)、空间 O(k)。当 k = O(n) 时，整体就是 O(n)，且常数极小（只做加减与下标定位，无比较函数调用）。一旦 k ≫ n，O(k) 的频次数组空间和初始化时间会成为灾难。
典型场景：
- 年龄排序：值域 0~150，
k=151，对任意n都极快。 - 考试分数排序：百分制 0~100，
k=101。 - 字符 / 字节频率统计：ASCII
k=128或字节k=256，这也是基数排序每趟的内部子例程。 - 小范围枚举：颜色值（0~255）、星期（1~7）、月份（1~12）。
反例（不该用）：对 10 个 32 位整数排序，k ≈ 4×10⁹，频次数组要 4GB——远比直接插排慢。
二、何时用桶排序：均匀分布的浮点数
判定条件：值域连续（尤其浮点数），分布近似均匀，无法或不宜直接计数。
为什么：把值域均分成 m = Θ(n) 个桶后，均匀分布下每桶平均 n/m = O(1) 个元素，桶内排序近乎常数，整体期望 O(n)。桶排序的关键不是「桶内用什么排序」，而是「分布是否均匀让每桶都轻」。
典型场景：
[0, 1)均匀分布浮点数：经典教科书设定，m = n个桶，期望 O(n)。- 值域大但分布均匀的数据：如传感器读数、随机散布的大范围数值，无法计数但分布均匀。
- 均匀分片 / 哈希分桶：桶思想在分布式负载均衡、一致性哈希中复用——把 key 均分到桶（节点）。
反例（不该用）：数据严重倾斜（90% 落入同一桶），退化到该桶内排序，最坏 O(n²)。
三、何时用基数排序：固定位数的多关键字
判定条件：数据可按位分解（整数按数位、字符串按字符），且位数 d 不大（常数或 O(log n)）。
为什么：基数排序做 d 趟稳定计数排序，每趟 O(n + b)，合计 O(d · (n + b))。当 d 是常数（定长数据）时，整体 O(n)，且稳定——这对多关键字排序（先按次要关键字排，再按主关键字稳定排）特别有价值。
典型场景：
- 手机号 / 身份证号排序：固定位数（11 位 / 18 位），LSD 基数 O(11n) / O(18n) ≈ O(n)。
- 定长字符串字典序：如 8 位日期
YYYYMMDD、定长编码，LSD 按字符位排序。 - 日期 / 时间排序：可拆为「年-月-日-时-分-秒」多位关键字。
- IPv4 地址排序：4 段 8 位，按段做基数。
- 多关键字排序：先按次要键排，再按主键稳定排（基数排序思想的推广）。
MSD vs LSD：
- LSD（低位到高位）：实现简单，迭代
d趟，适合定长数据。 - MSD（高位到低位）：递归分桶，适合变长字符串字典序（短的排前），但实现复杂、递归开销大。
反例（不该用）：任意可比较对象（无法拆位）、位数 d 很大的大整数（d 大时 O(d · n) 不见得比 O(n log n) 好）、浮点数（位模式与大小关系非单调，需特殊处理）。
四、稳定性：不只是特性，是正确性
非比较排序里稳定性地位特殊：
| 算法 | 稳定？ | 原因 |
|---|---|---|
| 计数排序 | ✅ 稳定 | 第三步「倒序遍历 + 前缀和定位」保证同值元素后出现的仍排后 |
| 桶排序 | 取决桶内 | 桶间天然有序；桶内用插排 / 归并则稳定，用快排则不稳定 |
| 基数排序 | ✅ 稳定 | 每一趟用稳定计数排序，稳定性是 LSD 正确的前提 |
为什么基数排序必须稳定：从低位排到高位时，若某趟不稳定，高位排序会打乱低位已排好的相对次序——比如 [21, 12] 按个位排成 [21, 12]（1 同），再按十位若不稳定可能得到 [12, 21]（对）但也可能错乱。稳定性保证「同高位元素保持低位趟的次序」，从而最终全局有序。
对计数排序「倒序放」的理解：前缀和后 count[v] 指向值 v 的末尾下标 + 1。倒序遍历原数组时，后出现的同值元素先被放进靠后的位置（--count 先减），从而保持原相对次序——这就是稳定性的来源。若改成顺序放则不稳定。
五、局限性与负数处理
非比较排序的命门在于前提，三个常见陷阱：
- 值域
k过大 → 空间爆炸：计数排序要 O(k) 空间。对 32 位整数k ≈ 4×10⁹，频次数组不可接受。应对：只在k = O(n)时用计数；否则换基数（按位）或退回比较排序。 - 分布倾斜 → 桶排序退化：全挤一个桶时退化到桶内排序最坏 O(n²)。应对：先估分布，倾斜则不用桶排序；或桶数动态调整。
- 位数
d过大 / 不可拆位 → 基数失效：大整数d大、浮点位模式非单调、任意对象不可拆位。应对：只对固定位数整数 / 字符串用基数。
负数处理：
- 计数排序：统一减最小值
x - min做偏移，把值域[min, max]平移到[0, k)，输出时还原。这是最干净的负数处理法。 - 基数排序：负数较麻烦——十进制下负号与位不兼容。常见做法是把负数、非负数分组，各自基数排序后拼接（负数按绝对值排再反转）；或用补码按无符号位模式排序（但需理解补码的符号位）。通常负数场景更推荐计数偏移法。
六、实际工程应用
- 基数排序作为字符串排序的子例程：后缀数组构造（SA-IS、DC3 的某些步骤）、定长键的字典序排序。
- LSD 基数的历史地位：早期卡片机（打孔卡）排序就是 LSD 基数——按列（位）分桶收集，是计算机出现前就有的排序方法。
- 桶思想的外延：负载均衡（把任务按 key 均分到节点）、一致性哈希（虚拟节点分桶）、数据库直方图统计。
- 混合排序中的计数身影：当快排 / Timsort 递归到小子数组且值域小时，部分实现会切换到计数排序以利用其小常数——这也是非比较排序最常见的「藏身之处」。
交互演示
下一步
选型掌握后，最后一份是速查参考——复杂度对比表、可直接复用的代码模板、选型决策树、与比较排序的横向对比、以及高频易错点清单，见参考。