非比较排序（计数 / 桶 / 基数）
非比较排序（Non-comparison Sort）是一族绕开「元素两两比较」的排序算法——它不依赖 a[i] < a[j] 这类比较来决定次序，而是直接利用数据的数值性质（取值范围、分布、按位可分解）来定位每个元素。正因为绕开了比较，它突破了比较排序 O(n log n) 的理论下限：决策树证明告诉我们任何「只靠比较」的排序至少要 Ω(n log n) 次比较，而计数排序在值域 k 有限时能做到 O(n + k)、桶排序在均匀分布下期望 O(n)、基数排序对 d 位关键字能做到 O(d · n)——线性级别。这听起来「违反」下限，其实是因为它用了比较排序没有的「额外信息」（值域、分布、位数），用空间/前提换时间。
非比较排序的全部考点都源于一个权衡事实：靠数值性质而非比较 ⇒ 线性时间，但要求前提满足。由此衍生出三大算法：①计数排序（Counting Sort）——统计每个值的出现频次，再做前缀和把频次转成「该值在结果中的末尾位置」，值域为 k 时 O(n + k) 时间、O(k) 空间，且稳定；②桶排序（Bucket Sort）——把值域切成若干桶，每个桶内用任意排序（常插排）排好后依序拼接，均匀分布时每桶元素少、期望 O(n)；③基数排序（Radix Sort）——把整数按位（LSD 由低位到高 / MSD 反之）分解，对每一位用稳定的计数排序，d 位时 O(d · (n + b))（b 为基数）。三者共享同一个铁律：不比较，所以能 O(n)；但有前提（值域有限 / 分布均匀 / 可分解位），前提不满足就退化甚至不可用。
评价
优点
- 突破 O(n log n) 下限：不靠比较，靠数值性质直接定位，计数 O(n + k)、桶期望 O(n)、基数 O(d · n)——这是它们存在的全部理由。
- 可做到稳定：计数排序（前缀和从后往前放）与基数排序（每趟稳定）天然稳定；桶排序取决于桶内算法，桶内用稳定排序则整体稳定——这点优于快排/堆排。
- 常数因子小、无比较开销：计数排序只做加减与数组下标定位，不调用比较函数，对小值域整数极快；基数排序对固定位数（手机号、身份证、定长字符串）非常高效。
- 适合特定数据：计数排序适合「值域小」的整数（年龄、考试分数）；桶排序适合「均匀分布」的浮点数；基数排序适合「固定位数」的多关键字（手机号、日期、字符串字典序）。
缺点
- 前提苛刻，不能通用：计数要求值域
k不能远大于n（否则空间爆炸）；桶要求分布近似均匀（否则退化到桶内 O(n log n) 甚至 O(n²)）；基数要求可按位分解且位数d不能太大——脱离前提性能急剧恶化。 - 空间开销大：计数排序要 O(k) 的频次数组，值域大时（如 32 位整数
k ≈ 4×10⁹）空间不可接受；桶排序要桶数组 + 桶内存储；基数排序要 O(n + b) 辅助空间。 - 数据类型受限：计数/基数主要面向整数或可映射为整数的类型（浮点数要先映射到桶，字符串要按字符位处理），对任意可比较对象不通用——这点远不如比较排序。
- 不能原地：三者都需要与
n或值域同阶的额外空间，不像堆排能 O(1) 原地完成。
本叶地图
- 入门 —— 比较排序 O(n log n) 下限（决策树证明）、非比较如何突破、三者共同前提、为何不能通用
- 三种算法详解 —— 计数排序（频次 + 前缀和定位）、桶排序（分桶 + 桶内排序 + 合并）、基数排序（LSD 按位 + 计数排序）、代码与复杂度推导
- 选型与应用场景 —— 何时用计数（值域小整数）、何时用桶（均匀分布浮点）、何时用基数（固定位数）、稳定性、局限性
- 参考 —— 复杂度对比表、代码模板、选型决策树、与比较排序对比、易错点（值域/稳定性/负数）