计数排序c++

以下是 C++ 中的计数排序实现：

#include <iostream>
#include <algorithm>

using namespace std;

void countingSort(int arr[], int n) {
    int maxVal = *max_element(arr, arr+n); // 获取数组中的最大值
    int freq[maxVal+1] = {0}; // 用于存储每个元素出现的次数

    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }

    int j = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (freq[i] > 0) {
            arr[j++] = i;
            freq[i]--;
        }
    }
}

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

    countingSort(arr, n);

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

    return 0;
}

计数排序的时间复杂度为 O(n+k)，其中 k 为数组中的最大值。在数组元素分布较为均匀的情况下，计数排序表现良好，但如果元素值分布过于不均匀，计数排序的效率会下降。