第 26 课：计数排序

前面所讲述的都是需要比较才能进行的排序，现在我们学习一种非比较型的整数排序算法，它是利用元素的数值范围来统计元素出现的次数，进而实现的排序。

26.1 计数排序的概念及步骤

概念

当需要排序的数据在一个明显有限的范围内（整型）时，我们可以将数组下标与数值一一对应，将每个数值放进与它对应的数组元素中，然后按照顺序输出数组下标，得到有序的序列。这种排序方式，我们称为计数排序（counting sort）。

步骤

1. 初始化数组：创建一个长度比元素最大值大 1 的数组，用于记录每个元素出现的次数，数组元素的初始值默认为 0。

2. 计数：读取待排序元素的数量，并逐个读取元素，将对应元素值作为数组下标，该下标位置的计数加 1。

3. 输出结果：按照元素值从小到大的顺序遍历数组，依据每个下标位置的计数值，输出对应元素相应次数。

26.2 演示及实现

演示

我们以输入的 5 个数 [3, 1, 2, 3, 1] 为例，来演示计数排序的过程。

1. 先定义一个大小为 5 的数组 a，用于统计每个元素出现的次数。在这个例子开始时，数组 a 的所有元素默认初始化为 0，即 a = [0, 0, 0, 0, 0]。

2. 计数

a. 读取第一个数 3：将 a[3] 的值加 1，此时 a = [0, 0, 0, 1, 0]。

b. 读取第二个数 1：将 a[1] 的值加 1，此时 a = [0, 1, 0, 1, 0]。

c. 读取第三个数 2：将 a[2] 的值加 1，此时 a = [0, 1, 1, 1, 0]。

d. 读取第四个数 3：将 a[3] 的值再加 1，此时 a = [0, 1, 1, 2, 0]。

e. 读取第五个数 1：将 a[1] 的值再加 1，此时 a = [0, 2, 1, 2, 0]。

此时，计数数组 a 记录了每个元素出现的次数：a[1] = 2 表示数字 1 出现了 2 次；a[2] = 1 表示数字 2 出现了 1 次；a[3] = 2 表示数字 3 出现了 2 次。

3. 按元素值从小到大的顺序遍历计数数组 a，根据每个位置的计数值输出相应个数的下标。

代码实现（假设输入的数最大到 10000）

#include <iostream>
using namespace std;
int main()
{
    int a[10005] = {0};
    int input[] = {3, 1, 2, 3, 1}; // 输入的五个数
    int n = 5;
    for (int i = 0; i < n; i++)
    {
        int t = input[i];
        a[t]++; // 计数
    }
    for (int i = 1; i <= 10000; i++) // 遍历所有的下标
    {
        for (int j = 1; j <= a[i]; j++) // 输出 a[i] 个下标
        {
            cout << i << " ";
        }
    }
    return 0;
}

26.3 实例讲解

例 1：奇怪的排序

现在有 n 个整数，这些数的取值范围为 -1000 到 1000，请你设计程序，将这些数据按照从大到小排序后输出。

【输入格式】输入两行。第 1 行输入一个正整数 n（1 ≤ n ≤ 1000）。

第 2 行输入 n 个用空格隔开的整数。

【输出格式】输出一行，n 个用空格隔开的整数。

【输入样例】

5
-1 2 4 -3 5

【输出样例】5 4 2 -1 -3

注：原书将负数范围的负号误排为全角破折号“—”，且 n 的取值范围写作“—1000 ≤ n ≤ 1000”，与“正整数”矛盾，此处已分别修正为“-1000”和“1 ≤ n ≤ 1000”。

解析

1. 创建一个长度为 2001 的计数数组 a，用于统计每个元素出现的次数。

2. 读取输入的整数 n，表示待排序元素的数量。

3. 读取 n 个整数，对于每个整数 t，将其映射到计数数组的下标 t + 1000，并将该下标的计数值加 1。

4. 从计数数组的最大下标 2000 开始反向遍历到下标 0，对于每个下标 i，如果计数值 a[i] 大于 0，则输出 i - 1000 共 a[i] 次。

参考代码

#include <iostream>
using namespace std;
int a[2100];
int main()
{
    int n, t;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        // 读取一个数 t
        cin >> t;
        // 将数 t 映射到数组 a 的下标位置并计数（加 1）
        a[t + 1000]++;
    }
    // 从大到小遍历数组 a（对应数从 1000 到 -1000）
    for (int i = 2000; i >= 0; i--)
    {
        // 根据每个数的计数，输出相应个数的该数
        for (int j = 1; j <= a[i]; j++)
            cout << i - 1000 << " ";
    }
    return 0;
}

注：原书输出语句写作 ' '（两空格的多字符字面量），此处统一改为 " "，与样例输出保持一致；下文示例中的同类写法也一并修正。

26.4 计数排序的去重与计数

我们可以利用计数排序来完成去重与计数的任务。

1. 解决去重问题时，只需将每个数据装入数组中，再根据数组中是否有数据（count[i] > 0），来输出对应的下标，而不需要循环输出多个下标。

2. 解决计数问题时，输出数组中的数据即为元素出现的次数。

例 1：教务主任的烦恼（去重）

蛙蛙所在的学校近期统计了师生的年龄数据，教务处主任希望你帮忙把这些年龄从小到大排序，重复的年龄只保留一个。

作为编程小高手的你能帮他解决这个问题吗？

【输入格式】输入两行。第 1 行输入整数 n，表示要输入 n 位师生的年龄。

第 2 行输入 n 个整数，用空格隔开，分别表示每一位老师或学生的年龄。（0 < n ≤ 100000，年龄在 1 和 100 之间）

【输出格式】输出一行，去掉重复项后从小到大排列的年龄，年龄用空格隔开。

【输入样例】

10
15 28 35 15 45 23 14 19 26 33

【输出样例】14 15 19 23 26 28 33 35 45

参考代码

#include <iostream>
using namespace std;
int a[105];
int main()
{
    int n, t;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> t;
        a[t]++;
    }
    for (int i = 1; i <= 100; i++)
        if (a[i]) // 数据不为 0，输出一次
            cout << i << " ";
    return 0;
}

例 2：信息学成绩统计（计数）

蛙市中小学刚刚结束期中测试，信息学老师想统计全市学生信息学的得分情况，即得到某些分数的人数，以便改进教学内容和方法，提高同学们的信息学成绩。同学们写个程序，帮助老师实现吧。

【输入格式】输入三行。第 1 行是两个由空格分隔的正整数 n 和 k，其中 n 表示全市所有学生的人数，k 表示老师想要统计 k 个分数的人数。

第 2 行共有 n 个由空格分隔的正整数，表示每一位学生的成绩。

第 3 行有 k 个由空格分隔的正整数，表示想要统计的 k 个分数。

（1 ≤ n ≤ 10000，k ≥ 0，分数在 100 以内。）

【输出格式】输出一行，k 个由空格分隔的正整数，对应每个得分的学生数。

【输入样例】

10 3
90 96 60 65 67 72 75 75 80 85
65 75 95

【输出样例】1 2 0

参考代码

#include <iostream>
using namespace std;
int t[105];
int main()
{
    int a, n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a;
        t[a]++;
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> a;
        cout << t[a] << " "; // 查找 a 出现的次数
    }
    return 0;
}