计数排序与基数排序（进阶）
复习
- 排序问题与稳定性：稳定性为何重要
- 数组：可按下标存取
- 归并与快排：基于比较的
O(n log n)
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 计数排序不比较元素，而是统计每个取值出现的次数
- 它需要知道取值范围，适合小范围的整数
- 基数排序按“位”逐轮排序，常配合稳定排序
- 它们能快过比较排序，但有各自的适用前提
正文
前面几种排序都靠“两两比较”决定顺序。可如果不比较，能不能更快？能——只要利用数据本身的取值特点。
计数排序：数一数各有多少个
计数排序（counting sort）的思路很直接：如果元素都是某个小范围内的整数，那就统计每个值出现了多少次，再按顺序把它们摆回去。
- 建一个计数数组，统计每个取值出现的次数
- 累加计数，算出每个值应该放在哪个位置
- 按顺序把元素放回结果数组
它不做任何比较，代价是 O(n + k)，其中 k 是取值范围。当 k 不太大时，这就是线性的，比 O(n log n) 还快。但如果取值范围极大（比如 32 位整数），那就没法开这么大的计数数组了。
基数排序：一位一位来
基数排序（radix sort）则适合更一般的情况：把整数按个位、十位、百位这样一位一位地排序。
做法是：先按最低位排一遍，再按次低位排一遍……直到最高位。每一轮都用一个稳定的排序（通常是计数排序）来处理当前这一位。
为什么要求每轮稳定？因为高位排序时，必须保留低位已经排好的顺序。如果这一轮不稳定，就会把之前排好的低位顺序打乱，前功尽弃。稳定性在这里不是锦上添花，而是必要条件。
它们突破了什么
这两种算法的共同点，是绕开了“两两比较”，转而利用数据的取值结构（范围、位数）。因此它们能做到线性级别，快过归并、快排。
但代价也很清楚：
- 计数排序要求取值范围不大
- 基数排序要求数据能被“按位”拆分（通常是整数或定长串）
换句话说，它们更快，是因为对数据提出了额外要求。这也预告了下一章的一个深刻结论：如果只允许比较，那 O(n log n) 就是一道绕不过去的坎。
思考题 1
计数排序为什么不需要比较元素？它的前提是什么？
思考题 2
基数排序为什么要求每一轮的排序都是稳定的？
小结
知识点
- 计数排序统计取值频次，代价
O(n + k) - 它适合取值范围不大的整数
- 基数排序按位逐轮排序
- 每轮必须稳定，才能保留低位的顺序
参考资料
- Wikipedia(zh)：计数排序：统计频次的非比较排序
- Wikipedia(zh)：基数排序：按位逐轮排序的非比较排序
思考题答案（仅供参考）
思考题 1
因为它直接统计每个取值出现的次数，再按值的大小顺序把元素摆回去，不需要两两比较。前提是元素是某个范围内的整数（或可映射为小范围整数），这样才能开得起计数数组。
思考题 2
因为高位排序时必须保留低位已排好的相对顺序。若某一轮不稳定，就会打乱低位排序的成果，导致最终结果不正确。稳定性是基数排序正确性的必要条件。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪