counting sort c++

计数排序是一种用于排序整数的算法，可以在时间复杂度为O(n+k)的情况下完成排序，其中n为要排序的元素个数，k为元素的最大值。以下是C++的计数排序示例代码：

#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr){
    if (arr.size() == 0) return;

    int max_val = *max_element(arr.begin(), arr.end());
    vector<int> count(max_val + 1, 0);

    for (int i = 0; i < arr.size(); ++i)
        count[arr[i]]++;

    for (int i = 1; i < count.size(); ++i)
        count[i] += count[i - 1];

    vector<int> temp(arr.size());
    for (int i = arr.size() - 1; i >= 0; --i) {
        temp[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < arr.size(); ++i)
        arr[i] = temp[i];
}

int main()
{
    vector<int> arr = { 3, 2, 1, 4, 5, 7, 6, 8, 9, 0 };
    countingSort(arr);
    for (auto i : arr)
        cout << i << " ";
    cout << endl;
    return 0;
}