计数排序

题目描述
计数排序是一种非比较型整数排序算法，其时间复杂度为 O(n+k)，其中 n 是待排序元素的个数，k 是整数的范围。计数排序的基本思想是对于每个元素 x，确定小于 x 的元素个数，然后将 x 直接放到最终排序结果中的正确位置上。

输入格式
输入共 2 行，第一行是一个整数 n，表示数组的长度。第二行包含 n 个整数，表示待排序的数组。

输出格式
输出共 1 行，包含 n 个整数，表示排序后的数组（升序排列）。

数据范围
1 ≤ n ≤ 10000
0 ≤ 数组元素 ≤ 10000

输入样例：

10
4 2 2 8 3 3 1 5 5 0

输出样例：

0 1 2 2 3 3 4 5 5 8

注意事项

• 计数排序的时间复杂度为 O(n+k)，空间复杂度为 O(k)。
• 计数排序是稳定的排序算法。
• 计数排序特别适合于已知范围的整数排序，当 k 较小时，计数排序的效率很高。

代码实现

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

// 计数排序函数
void countingSort(int a[], int n, int max_value)
{
    vector<int> count(max_value + 1, 0); // 计数数组，初始化为0
    vector<int> output(n); // 输出数组
    
    // 统计每个元素出现的次数
    for (int i = 0; i < n; i++)
    {
        count[a[i]]++;
    }
    
    // 计算每个元素在输出数组中的位置（前缀和）
    for (int i = 1; i <= max_value; i++)
    {
        count[i] += count[i - 1];
    }
    
    // 从后向前遍历原数组，保证排序的稳定性
    for (int i = n - 1; i >= 0; i--)
    {
        output[count[a[i]] - 1] = a[i];
        count[a[i]]--;
    }
    
    // 将排序结果复制回原数组
    for (int i = 0; i < n; i++)
    {
        a[i] = output[i];
    }
}

int main()
{
    int n;
    cin >> n;
    int a[n];
    int max_value = 0;
    
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] > max_value)
        {
            max_value = a[i]; // 找出数组中的最大值
        }
    }
    
    countingSort(a, n, max_value); // 对整个数组进行计数排序
    
    // 输出排序后的数组
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    
    return 0;
}

时间复杂度

• 时间复杂度：O(n+k)，其中 n 为数组的长度，k 为数组中元素的最大值。
• 空间复杂度：O(n+k)。

代码解释

• 计数排序的核心思想是统计每个元素出现的次数，然后根据这些统计信息将元素放到正确的位置上。
• 计数排序的实现分为三个步骤：
  1. 统计每个元素出现的次数，存储在计数数组 count 中。
  2. 计算每个元素在输出数组中的位置，这可以通过计算计数数组的前缀和来实现。
  3. 从后向前遍历原数组，将每个元素放到输出数组中的正确位置上，这样可以保证排序的稳定性。
• 最后，将排序结果复制回原数组。