C++中的计数排序算法

计数排序是一种用于排序一组整数的算法。它适用于具有已知范围的整数排序，通常在不需要比较元素的情况下完成排序，因此速度非常快。

这里是计数排序的简要步骤：

1. 扫描数组以确定每个整数出现的次数。你可以创建一个计数数组，其大小等于整数范围的大小，然后对数组进行遍历，每当找到一个整数，就在计数数组中对应的位置增加1。

2. 累计计数数组。现在，你需要修改计数数组，使每个位置的值等于或累积前面所有位置的值。这将告诉你每个整数在排序后数组中的最终位置。

3. 创建一个临时数组来存储排序后的结果。这个数组的大小应与待排序数组的大小相同。

4. 遍历原始数组，对于每个整数，查找其在计数数组中的累计计数，将其放入临时数组中的相应位置，并将计数数组中的值减1。

5. 最后，将临时数组中的内容复制回原始数组，这样原始数组就被排序了。

以下是用C++98语法的示例代码：

#include <iostream>
#include <vector>

void CountingSort(std::vector<int>& arr, int range) {
    std::vector<int> count(range + 1, 0);
    int size = arr.size();

    // 计算每个整数出现的次数
    for (int i = 0; i < size; ++i) {
        count[arr[i]]++;
    }

    // 累计计数数组
    for (int i = 1; i <= range; ++i) {
        count[i] += count[i - 1];
    }

    // 创建临时数组来存储排序后的结果
    std::vector<int> result(size);

    // 填充临时数组并更新计数数组
    for (int i = size - 1; i >= 0; --i) {
        result[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // 将排序后的结果复制回原始数组
    for (int i = 0; i < size; ++i) {
        arr[i] = result[i];
    }
}

int main() {
    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    int range = 8; // 整数范围为0到8

    CountingSort(arr, range);

    // 输出排序后的数组
    for (int i = 0; i < arr.size(); ++i) {
        std::cout << arr[i] << " ";
    }

    return 0;
}