基本思想

如果我们能够得到数组中元素在排序后的位置就好了。计数排序就是基于这种愿望。

基本步骤

1. 准备一个辅助数组用来记录某个数组元素的个数。cnt[i]=j 意味着，大小为 i 的元素有 j 个；
2. 计算 cnt 数组的前缀和数组 s，s[i-1]=j 意味着比 i 小的数的个数为 j；
3. 上一步骤中的 j，就决定了 i 元素在排序后的位置为 j+1（如果数组的下标从 1 开始）；

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;
int n;
int a[N], s[N], w[N];

void count_sort() {
    // 统计元素个数
    for (int i = 0; i < n; i++) s[a[i]]++;
    // 计算前缀和
    for (int i = 1; i < N; i++) s[i] += s[i - 1];
    // 得出元素 i 的位置
    for (int i = n - 1; i >= 0; i--) w[--s[a[i]]]
    // 填入原数组
    for (int i = 0; i < n; i++) a[i] = w[i];
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    count_sort();
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}