计数排序 c++ 代码

计数排序是一种线性时间复杂度的排序算法，适用于待排序元素范围较小的情况。下面是一个简单的C++代码示例：

#include <iostream>
#include <vector>

void countingSort(std::vector<int>& arr) {
    int maxVal = *std::max_element(arr.begin(), arr.end()); // 获取最大值
    std::vector<int> count(maxVal + 1, 0); // 创建计数数组并初始化为0

    // 统计每个元素出现的次数
    for (int num : arr) {
        count[num]++;
    }

    // 根据计数数组重新排序原数组
    int index = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

int main() {
    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    
    countingSort(arr);

    std::cout << "排序结果：";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}