什么是计数排序？¶

计数排序是一种非比较型的排序算法，它的核心思想是通过统计每个元素出现的次数，然后根据这些次数直接构建排序后的数组。与快速排序、归并排序等基于比较的排序算法不同，计数排序不需要比较元素的大小，而是通过“计数”的方式完成排序。这种算法特别适合处理整数范围不大的排序场景，比如学生成绩（0-100分）、年龄（0-150岁）等数据。

基本思路¶

以一个具体例子说明计数排序的步骤：假设我们要对数组 [4, 2, 2, 8, 3, 3, 1] 进行排序。

1. 统计元素出现次数：
   首先找到数组中的最大值（这里是8），创建一个大小为 max_val + 1 的计数数组 count，用于记录每个元素出现的次数。遍历原数组，统计每个元素的出现次数：
   - count[0] = 0（无0）
   - count[1] = 1（元素1出现1次）
   - count[2] = 2（元素2出现2次）
   - count[3] = 2（元素3出现2次）
   - count[4] = 1（元素4出现1次）
   - count[5] = 0（无5）
   - count[6] = 0（无6）
   - count[7] = 0（无7）
   - count[8] = 1（元素8出现1次）

2. 构建排序数组：
   根据计数数组的统计结果，将元素按顺序插入到结果数组中。例如：
   - 元素1出现1次 → 插入结果数组：[1]
   - 元素2出现2次 → 插入结果数组：[1, 2, 2]
   - 元素3出现2次 → 插入结果数组：[1, 2, 2, 3, 3]
   - 元素4出现1次 → 插入结果数组：[1, 2, 2, 3, 3, 4]
   - 元素8出现1次 → 插入结果数组：[1, 2, 2, 3, 3, 4, 8]

C++代码实现¶

下面是计数排序的完整C++实现：

#include <iostream>
using namespace std;

// 计数排序函数：对数组arr进行排序
void countingSort(int arr[], int n) {
    // 步骤1：找到数组中的最大值
    int max_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    // 步骤2：创建计数数组，大小为max_val + 1，初始化为0
    int count[max_val + 1] = {0};

    // 步骤3：统计每个元素出现的次数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 步骤4：构建排序后的数组
    int output[n]; // 结果数组
    int index = 0; // 结果数组的当前索引
    for (int i = 0; i <= max_val; i++) {
        // 将元素i重复count[i]次插入到结果数组
        while (count[i] > 0) {
            output[index] = i;
            index++;
            count[i]--;
        }
    }

    // 步骤5：将排序后的结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 测试函数
int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前的数组: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    countingSort(arr, n);

    cout << "\n排序后的数组: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

代码解释¶

1. 找到最大值：遍历数组确定最大元素，用于创建计数数组的大小。
2. 统计次数：通过计数数组 count 记录每个元素出现的次数，例如 count[2] = 2 表示元素2出现2次。
3. 构建结果数组：遍历计数数组，将每个元素按出现次数重复插入结果数组 output。
4. 复制回原数组：将排序后的结果数组 output 复制回原数组 arr，完成排序。

时间复杂度与空间复杂度¶

• 时间复杂度：O(n + k)，其中 n 是数组长度，k 是最大值与最小值的差。遍历数组统计次数需要 O(n)，构建结果数组需要 O(n)，总时间为 O(n + k)。
• 空间复杂度：O(k)，需要额外的计数数组 count 和结果数组 output，空间大小取决于最大值 k。

适用场景与注意事项¶

• 适用场景：
• 待排序元素为非负整数且范围较小（如学生成绩、年龄）。

• 需高效排序且不关心元素间的相对顺序（仅需稳定排序时需额外处理）。

• 处理负数的方法：若数组包含负数，可通过“偏移量”将负数转换为非负数。例如，数组 [-1, 3, -2] 的最小值为 -2，可将每个元素加上 2（偏移量）转换为 [1, 5, 0]，排序后再减去偏移量。

通过上述步骤，计数排序能以线性时间完成排序，是处理小范围整数的高效算法。初学者只需理解“统计次数→构建结果”的核心逻辑，即可快速掌握其实现。