 c++编程计数排序算法

计数排序（Counting Sort）是一种非基于比较的整数排序算法，它适用于待排序元素范围较小的情况，如都是正整数且不超过某个定值。下面是基本的C++实现步骤：

1. **确定输入数组的最大值**：首先扫描整个数组找出最大值，这将作为计数数组的大小。

2. **创建计数数组**：初始化一个大小为最大值+1的数组，所有元素默认值为0。这个数组用于存储每个输入值出现的次数。

3. **统计每个元素的出现次数**：遍历输入数组，对于每个元素，将其对应的计数数组值加一。

4. **累积计数**：从计数数组的第一个元素开始，累加每个元素到当前索引位置的值，这样就得到了每个元素应该放置的新位置。

5. **输出排序后的数组**：按照计数数组重构原数组，从最后一个元素的位置（即最大值）开始，依次取出计数数组对应位置的元素，放到新的数组中，并更新计数。

#include <iostream>
using namespace std;

void countingSort(int arr[], int n) {
    if (n == 0) return; // 空数组处理

    // 第一步：找到最大值
    int max_val = *max_element(arr, arr+n);

    // 第二步：创建计数数组并填充
    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];
    }

    // 第四步：重建排序后的数组
    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]);
    countingSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}