计数排序

#include <bits/stdc++.h>
#define N 500005

using namespace std;

int n, a[N], cnt[N], b[N];

void countSort(int n, int arr[])
{
    memset(cnt, 0, sizeof(cnt));
    int maxn = *max_element(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; i++)
        cnt[arr[i]]++;
    for (int i = 1; i <= maxn; i++)
        cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--)
        b[cnt[arr[i]]--] = arr[i];
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    countSort(n, a);
    for (int i = 1; i <= n; i++)
        printf("%d ", b[i]);
    return 0;
}