c++编程实现计数排序

计数排序是一种非基于比较的整数排序算法，它通过统计每个元素在输入数组中出现的次数来进行排序。以下是C++编程实现计数排序的基本步骤：

#include <iostream>
#include <vector>

// 计数排序函数
void countingSort(int arr[], int n, int max_val) {
    std::vector<int> count(max_val + 1, 0); // 创建一个桶，存储每个数字出现的次数

    // 统计每个元素出现的次数
    for (int i = 0; i < n; ++i)
        count[arr[i]]++;

    // 更新每个元素在结果数组的位置
    for (int i = 1; i <= max_val; ++i)
        count[i] += count[i - 1];

    std::vector<int> output(n);
    for (int i = n - 1; i >= 0; --i) {
        output[count[arr[i]] - 1] = arr[i]; // 将元素放到输出数组相应的位置
        count[arr[i]]--;
    }

    // 将排序后的数组复制回原数组
    for (int i = 0; i < n; ++i)
        arr[i] = output[i];
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_val = *std::max_element(arr, arr + n);

    std::cout << "Original array: ";
    for (int num : arr)
        std::cout << num << " ";
    std::cout << "\n";

    countingSort(arr, n, max_val);
    
    std::cout << "Sorted array: ";
    for (int num : arr)
        std::cout << num << " ";
    std::cout << "\n";

    return 0;
}

在这个例子中，`countingSort` 函数首先创建了一个长度为 `max_val+1` 的 `count` 数组，并遍历输入数组计算每个元素出现的次数。然后，通过累加得到每个位置应该放置的元素索引，最后将元素放回新的位置形成有序数组。