数据结构与算法 / 系统课时

计数排序

计数排序

计数排序不比较元素大小,而是统计每个整数键出现的次数,再根据累计次数确定元素位置。本课将实现稳定版本,并说明它为何能达到 O(n+k)O(n+k),以及值域过大时为什么不适合使用。

学习目标

  • 掌握计数、前缀累加和稳定回填三个核心步骤。
  • 能够实现可运行的稳定计数排序。
  • 能根据输入规模 nn 与值域大小 kk 判断算法是否合适。

工作机制

设输入包含 nn 个元素,键值位于 [0,k][0,k]。算法先创建长度为 k+1k+1 的计数数组,再把频次转换为前缀累计次数。累计值表示“键值不大于当前键的元素共有多少个”,因此可以直接推导每个元素在输出数组中的结束位置。

这个实现使用累计结束位置,因此从输入末尾向前回填。另一种稳定实现可以使用每个键的起始位置,再从左向右回填。对键 key,先将 count[key] 减 1,再把元素写入该下标。逆序回填可以让相同键中后出现的元素先占据靠后位置,从而保持原有相对顺序。

稳定计数排序执行流程

时间复杂度为 O(n+k)O(n+k):扫描输入需要 O(n)O(n),累加计数需要 O(k)O(k),回填需要 O(n)O(n)。稳定版本还需要长度为 nn 的输出数组,因此额外空间为 O(n+k)O(n+k)。当 kk 远大于 nn 时,初始化和保存计数数组的成本会抵消线性排序的优势。

完整实现

下面使用 Java 17 的 record 保存键和标签。示例中的两个键为 1 的对象、两个键为 2 的对象会在排序后保持原顺序。将代码保存为 CountingSortDemo.java。

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;
    }
}

运行命令:

bash
javac -encoding UTF-8 CountingSortDemo.java
java CountingSortDemo

预期输出:

text
原始数据: [(2,A), (1,B), (2,C), (0,D), (1,E)]
排序结果: [(0,D), (1,B), (1,E), (2,A), (2,C)]
计数数组长度: 3
稳定性验证: true

关键边界

示例要求键值位于 [0,k][0,k]。若数据包含负数,可以先求最小值 min 和最大值 max,再使用 value - min 作为计数下标,此时计数数组长度为 max - min + 1。先用 long 计算差值和长度,再检查资源预算及是否可安全转成索引。本例主动拒绝超过 1,000,000 个桶的输入。参考排序与身份对照只用于验证,并另占空间。

稳定性的关键不是“使用了计数数组”,而是“使用累计次数定位,并从右向左回填”。若只按频次直接重复输出键值,虽然数值顺序正确,但对象携带的其他字段会丢失;若仍用累计结束位置递减,却改成从左向右读取,相同键的相对顺序会反转。

选择算法时可先比较 kk 与 nn。当键值紧凑且可接受 O(n+k)O(n+k) 额外空间时,计数排序很有优势;当键值范围巨大、数据稀疏或键不是可映射的整数时,应考虑比较排序、哈希分组或基数排序。

本课练习

  1. 修改程序,使其支持键值范围 [-3, 3]。验收条件是排序结果正确,且相同键的标签顺序保持不变。
  2. 给值域检查编写边界用例。maxKey 等于 999999 时长度为 1,000,000;1000000 与 Integer.MAX_VALUE 都应在分配前拒绝。

本课总结

  • 计数排序通过频次和前缀累计位置排序,不受比较排序下界约束。
  • 稳定实现需要额外输出数组,并从输入末尾向前回填。
  • 总成本为 O(n+k)O(n+k),值域是否紧凑决定了它在工程中是否划算。

下一课预告

下一阶段将继续学习利用键值结构完成线性排序的方法,并比较计数排序与基数排序在稳定性、值域和内存成本上的差异。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

计数排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通