使用C++实现计数排序算法

计数排序是一种非比较型整数排序算法，它适用于待排序数据范围较小的情况，通常用于对一定范围内整数的排序。在C++中实现计数排序的基本步骤如下：

1. **获取输入数组的最大值**：遍历数组找出最大值`max_val`，以便确定桶的数量。

2. **创建计数数组**：初始化一个大小为`max_val + 1`的计数数组`count[]`，所有元素初始化为0。这个数组将用于存储每个元素在原始数组中出现的次数。

3. **统计每个元素出现次数**：遍历输入数组，对于每一个元素`val`，将`count[val]`加一。

4. **累计计数**：从数组末尾开始，将每个位置的计数值累加到前一个位置，模拟每个元素实际的位置。

5. **构建排序后的数组**：从最小值开始，按照计数数组`count[]`的顺序，复制元素到新的数组中，并更新原数组的对应位置。

6. **返回结果**：最后得到的结果数组就是已排序的序列。

以下是简单的C++代码示例：

#include <iostream>
using namespace std;

void countingSort(int arr[], int n) {
    // 步骤1 & 2
    int max_val = *max_element(arr, arr+n);
    int count[max_val+1] = {0};

    // 步骤3
    for (int i = 0; i < n; ++i) {
        count[arr[i]]++;
    }

    // 步骤4
    for (int i = 1; i <= max_val; ++i) {
        count[i] += count[i - 1];
    }

    // 步骤5 & 6
    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);
    cout << "Sorted array is: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}