数据结构与算法 / 系统课时
计数排序
计数排序
计数排序不比较元素大小,而是统计每个整数键出现的次数,再根据累计次数确定元素位置。本课将实现稳定版本,并说明它为何能达到 ,以及值域过大时为什么不适合使用。
学习目标
- 掌握计数、前缀累加和稳定回填三个核心步骤。
- 能够实现可运行的稳定计数排序。
- 能根据输入规模 与值域大小 判断算法是否合适。
工作机制
设输入包含 个元素,键值位于 。算法先创建长度为 的计数数组,再把频次转换为前缀累计次数。累计值表示“键值不大于当前键的元素共有多少个”,因此可以直接推导每个元素在输出数组中的结束位置。
这个实现使用累计结束位置,因此从输入末尾向前回填。另一种稳定实现可以使用每个键的起始位置,再从左向右回填。对键 key,先将 count[key] 减 1,再把元素写入该下标。逆序回填可以让相同键中后出现的元素先占据靠后位置,从而保持原有相对顺序。

时间复杂度为 :扫描输入需要 ,累加计数需要 ,回填需要 。稳定版本还需要长度为 的输出数组,因此额外空间为 。当 远大于 时,初始化和保存计数数组的成本会抵消线性排序的优势。
完整实现
下面使用 Java 17 的 record 保存键和标签。示例中的两个键为 1 的对象、两个键为 2 的对象会在排序后保持原顺序。将代码保存为 CountingSortDemo.java。
import java.util.Arrays;
import java.util.Comparator;
public class CountingSortDemo {
public record Item(int key, String name) {
@Override
public String toString() {
return "(" + key + "," + name + ")";
}
}
public static Item[] stableCountingSort(Item[] input, int maxKey) {
long range = (long) maxKey + 1;
if (range < 1 || range > 1_000_000) {
throw new IllegalArgumentException("值域长度必须在 1 到 1000000 之间");
}
int[] count = new int[(int) range];
for (Item item : input) {
if (item == null || item.key() < 0 || item.key() > maxKey) {
throw new IllegalArgumentException("键值超出 [0, maxKey] 范围");
}
count[item.key()]++;
}
for (int key = 1; key < count.length; key++) {
count[key] += count[key - 1];
}
Item[] output = new Item[input.length];
for (int i = input.length - 1; i >= 0; i--) {
Item item = input[i];
int position = --count[item.key()];
output[position] = item;
}
return output;
}
public static void main(String[] args) {
Item[] input = {
new Item(2, "A"),
new Item(1, "B"),
new Item(2, "C"),
new Item(0, "D"),
new Item(1, "E")
};
int maxKey = 2;
Item[] sorted = stableCountingSort(input, maxKey);
System.out.println("原始数据: " + Arrays.toString(input));
System.out.println("排序结果: " + Arrays.toString(sorted));
System.out.println("计数数组长度: " + (maxKey + 1));
System.out.println("稳定性验证: " + matchesStableOrder(input, sorted));
}
private static boolean matchesStableOrder(Item[] input, Item[] sorted) {
if (input.length != sorted.length) {
return false;
}
Item[] expected = input.clone();
Arrays.sort(expected, Comparator.comparingInt(Item::key));
for (int i = 0; i < expected.length; i++) {
if (expected[i] != sorted[i]) {
return false;
}
}
return true;
}
}运行命令:
javac -encoding UTF-8 CountingSortDemo.java
java CountingSortDemo预期输出:
原始数据: [(2,A), (1,B), (2,C), (0,D), (1,E)]
排序结果: [(0,D), (1,B), (1,E), (2,A), (2,C)]
计数数组长度: 3
稳定性验证: true关键边界
示例要求键值位于 。若数据包含负数,可以先求最小值 min 和最大值 max,再使用 value - min 作为计数下标,此时计数数组长度为 max - min + 1。先用 long 计算差值和长度,再检查资源预算及是否可安全转成索引。本例主动拒绝超过 1,000,000 个桶的输入。参考排序与身份对照只用于验证,并另占空间。
稳定性的关键不是“使用了计数数组”,而是“使用累计次数定位,并从右向左回填”。若只按频次直接重复输出键值,虽然数值顺序正确,但对象携带的其他字段会丢失;若仍用累计结束位置递减,却改成从左向右读取,相同键的相对顺序会反转。
选择算法时可先比较 与 。当键值紧凑且可接受 额外空间时,计数排序很有优势;当键值范围巨大、数据稀疏或键不是可映射的整数时,应考虑比较排序、哈希分组或基数排序。
本课练习
- 修改程序,使其支持键值范围
[-3, 3]。验收条件是排序结果正确,且相同键的标签顺序保持不变。 - 给值域检查编写边界用例。maxKey 等于 999999 时长度为 1,000,000;1000000 与 Integer.MAX_VALUE 都应在分配前拒绝。
本课总结
- 计数排序通过频次和前缀累计位置排序,不受比较排序下界约束。
- 稳定实现需要额外输出数组,并从输入末尾向前回填。
- 总成本为 ,值域是否紧凑决定了它在工程中是否划算。
下一课预告
下一阶段将继续学习利用键值结构完成线性排序的方法,并比较计数排序与基数排序在稳定性、值域和内存成本上的差异。