计数排序——像数豆子一样把数字排好

你有没有遇到过这样的情况：老师发了一堆成绩单，想按分数从低到高排列，但分数只有0到100分，而且人数不算多。这时候，你不需要一趟趟地比较大小，只要先数一数每个分数有多少人，再按照分数从小到大把人列出来就行了。这种排序方法就叫计数排序。

计数排序是一种非比较排序——它压根不需要比较数字谁大谁小，而是通过统计每个数字出现的次数，然后根据次数直接放回正确的位置。它特别适合用来处理整数，而且数字的范围不能太大（比如最大值和最小值相差几千以内），否则太浪费内存。

核心思想：先数数，再按顺序放人

把计数排序想象成一个整理学号的过程。比如全班同学的学号范围是1到10，老师想知道学号顺序的名单，可以这样做：

1. 准备一张纸，写上1到10每个学号。
2. 看到第一个同学是学号4，就在“4”后面画一横。
3. 看到第二个同学是学号2，就在“2”后面画一横。
4. 全部同学看完后，统计每个学号后面有几横。
5. 从学号1开始，如果没有同学就跳过；如果有1个同学就把学号1写一遍；有2个同学就把学号1写两遍……这样按学号从小到大写出来，就是一个有序名单。

在计算机里，这张“纸”就是计数数组（count）。它的大小取决于最大数字有多大。比如最大值是8，计数数组就需要0到8共9个位置（因为数组下标从0开始）。

生活中的类比：整理零花钱硬币

假设你存钱罐里有1元、2元、5元、10元的硬币，你想把它们按面值从小到大排好。你不需要每枚硬币都去比较大小，只需要：

• 把1元的硬币挑出来，数一数有几个。
• 把2元的硬币挑出来，数一数有几个。
• ……
• 然后按面值从小到大，把几枚1元、几枚2元……依次放回罐子里。

这就完成了排序，而且一次比较都没有用。

具体步骤拆解

我们用经典例子 [4, 2, 2, 8, 3, 3, 1] 演示：

1. 找到最大值
   数字最小是1，最大是8。我们只需要知道最大值，就能确定计数数组的大小。

2. 创建计数数组并清零
   创建一个大小为 最大值+1 的数组，即9个元素（下标0~8），全部设为0。

3. 统计每个数字出现的次数
   遍历原数组：

   • 遇到4，count[4]变成1
   • 遇到2，count[2]变成1
   • 遇到2，count[2]变成2
   • 遇到8，count[8]变成1
   • 遇到3，count[3]变成1
   • 遇到3，count[3]变成2
   • 遇到1，count[1]变成1
     最终结果：count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1，其余为0。

4. 根据计数数组，按顺序放回原数组
   从下标0开始，检查 count[i] 是多少：

   • count[0]=0，跳过
   • count[1]=1，放入一个1
   • count[2]=2，放入两个2
   • count[3]=2，放入两个3
   • count[4]=1，放入一个4
   • count[5..7]=0，跳过
   • count[8]=1，放入一个8
     最终得到：[1, 2, 2, 3, 3, 4, 8]，是不是和直接排序的结果一样？

代码实现（附带详细注释）

下面这个完整程序实现了对整数数组（非负，范围较小）的计数排序。我们一步步来看每一段的作用。

#include <iostream>
#include <cstring>   // 提供 memset 函数用于快速清零
using namespace std;

// 计数排序函数，接收数组和元素个数
void countingSort(int arr[], int n) {
    // 1. 找到数组中的最大值
    int maxVal = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > maxVal) maxVal = arr[i];

    // 2. 动态分配计数数组，大小为 maxVal+1，并初始化为0
    int* count = new int[maxVal + 1](); // 后面的 () 表示所有元素初始化为0

    // 3. 统计每个数字出现的次数
    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    // 4. 根据计数数组，把数字按顺序放回原数组
    int index = 0;               // 原数组的填充位置
    for (int i = 0; i <= maxVal; i++) {
        while (count[i] > 0) {   // 如果数字 i 还有剩余，就放一个
            arr[index++] = i;
            count[i]--;
        }
    }

    // 5. 释放动态分配的内存
    delete[] count;
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};  // 待排序的原始数组
    int n = 7;                           // 数组长度

    // 调用计数排序
    countingSort(arr, n);

    // 输出排序后的结果
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    // 输出：1 2 2 3 3 4 8

    return 0;
}

代码要点解释：

• new int[maxVal + 1]() 中的 () 确保每个元素都被初始化为0。如果忘了 ()，新分配的内存里可能遗留垃圾值。
• 用 while 循环是因为一个数字可能出现多次，每放一个就把计数减1，直到放完为止。
• 最后一定要 delete[] count，否则会造成内存泄漏（程序结束后虽会自动回收，但好习惯要养成）。

新手容易犯的错误

错误1：计数数组下标越界

如果数组中有负数，比如 [-2, 3, 1]，直接用 count[arr[i]]++ 会访问负数的下标，导致程序崩溃。
解决方法：计数排序默认只适用于非负整数。如果必须处理负数，可以先把所有数减去最小值，使它们变成非负，排序后再加回来。

错误2：忘记求最大值，直接固定计数数组大小

比如数组最大值是10000，你却只分配了100大小的计数数组，同样会越界。
正确做法：先遍历数组找出最大值，再分配数组。或者如果已知数字范围很小（比如0~100），可以固定写死，但不够灵活。

错误3：误认为计数排序能排所有类型

计数排序只能排整数，而且最好范围小。如果数字是浮点数（如3.14）或字符串，就不适用了。

错误4：动态分配内存后忘记释放

如果程序中频繁创建计数数组而不释放，内存会越用越少（内存泄漏）。养成 new 和 delete[] 成对出现的好习惯。

完整示例：用计数排序处理考试成绩

假设一次随堂测验的满分是10分，有12个同学的成绩如下：[5, 3, 8, 5, 6, 7, 3, 9, 2, 5, 10, 6]。我们想按成绩从小到大排序。注意这里最大值是10，最小值是2（非负），范围很小，非常适合计数排序。

#include <iostream>
using namespace std;

void countingSort(int arr[], int n) {
    // 找最大值
    int maxVal = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > maxVal) maxVal = arr[i];

    // 计数数组
    int* count = new int[maxVal + 1]();

    // 统计
    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    // 放回
    int index = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }

    delete[] count;
}

int main() {
    int scores[] = {5, 3, 8, 5, 6, 7, 3, 9, 2, 5, 10, 6};
    int n = 12;

    countingSort(scores, n);

    cout << "排序后的成绩：";
    for (int i = 0; i < n; i++)
        cout << scores[i] << " ";
    // 输出：2 3 3 5 5 5 6 6 7 8 9 10

    return 0;
}

计数排序的优缺点

延伸学习：还有其他类似的排序方法吗？

如果你已经理解了计数排序，可以接着了解桶排序——它把数据分到几个“桶”里，每个桶内再用其他排序（比如插入排序）来排。还有基数排序——它按数字的每一位（个位、十位、百位）多次使用计数排序。

当然，如果数字范围大、数据类型复杂，还是老老实实用快速排序或归并排序吧。这些经典的比较排序算法虽然速度也不慢，但不需要依赖数字范围，应用更广泛。

建议你按这个顺序学习排序算法：

1. 冒泡排序（最简单，但慢）
2. 选择排序、插入排序
3. 归并排序、快速排序（分治思想）
4. 计数排序、桶排序、基数排序（非比较排序）

这样一步一步来，你会发现排序的世界非常有趣。