编辑代码

#include <iostream>
#include <vector>

void countingSort(std::vector<int>& arr) {
    // 找到数组中的最大值，以确定计数数组的大小
    int max = arr[0];
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    // 创建计数数组，并初始化为0
    std::vector<int> count(max + 1, 0);

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

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

int main() {
    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    
    std::cout << "Original Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }

    countingSort(arr);

    std::cout << "\nSorted Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }

    return 0;
}