计数排序

模板题

洛谷-P1271-选举学生会

#include <iostream>
using namespace std;

const int N = 2000010, M = 1010;
int a[N], b[N], c[M];

int main () {
    int n, m;
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    for (int i = 1; i <= n; ++ i) ++ c[a[i]];
    for (int i = 1; i <= m; ++ i) c[i] += c[i - 1];
    // 此时，≤ a[i] 的元素有 c[a[i]] 个
    for (int i = n; i >= 1; -- i) // 倒序，以稳定地排序
        b[c[a[i]] --] = a[i];

    for (int i = 1; i <= n; ++ i) printf("%d ", b[i]);
    return 0;
}