传送门：P1271 【深基9.例1】选举学生会

更佳的阅读体验：洛谷 P1271 题解

简要题意：给定一个长度为 $m$ 的序列，要求你对该序列从小到大排序。

题意很清晰。但考虑到本题可能用于各位入门排序算法，这里我们介绍两种做法。

计数排序

顾名思义，计数排序（Counting Sort）是一种基于计数操作的排序算法。

那么，给谁计数？怎么计数？

计数排序要求我们统计序列中每个元素的出现次数。换句话说，计数排序要求对谁排序，就对谁计数。

因为我们要对选票上的编号排序，因此我们考虑给选票上的编号计数，也就是要记录每个编号的出现次数。

因为编号一定是正整数，在 C++ 中，我们可以直接把编号当作数组下标处理。这里就引出了代码的实现方式。

我们可以新建一个辅助数组 $cnt$ 用来统计编号的出现次数，$cnt_i$ 表示编号 $i$ 的出现次数。在输入时，我们边输入边统计，每输入一个编号 $x$，我们就给 $cnt_x$ 加一。

统计结束以后，我们遍历整个 $cnt$ 数组，如果 $cnt_i$ 不为 $0$，那我们就输出 $cnt_i$ 个 $i$。注意，因为编号一定在 $[1, n]$ 之间，因此我们只需要从 $1$ 遍历到 $n$（而非 $m$）即可。

复杂度 $O(n + m)$。

#include <iostream>
using namespace std;

const int N = 1010, LIM = 999;
int n, m, x, cnt[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> x, ++cnt[x];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= cnt[i]; ++j) cout << i << ' ';
    return 0;
}

当然，计数排序也有一些限制。比如，计数排序要求被排序序列的元素必须是非负整数，并且元素的值域不能太大（值域太大会导致遍历数组的时间开销非常大，甚至根本开不下这么大的数组）。

那，是否有更加具有普适性的做法呢？答案是肯定的。

sort

C++ 中有一个好东西，叫做标准模板库（Standard Template Library, STL）。STL 中有一个函数 sort，被包含在 algorithm 头文件中，专门用于对一个数组进行排序。

sort 默认为从小到大排序。执行完 sort 之后，被排序的数组就会变成有序的。我们排序后直接输出即可。

复杂度 $O(m \log m)$。

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

const int N = 2e6 + 10;
int n, m, a[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> a[i];
    sort(a + 1, a + m + 1);
    // 如果是从大到小排序，使用 sort(a + 1, a + m + 1, greater<>());
    for (int i = 1; i <= m; ++i) cout << a[i] << " \n"[i == m];
    return 0;
}

当然，如果你对 sort 函数的原理感兴趣，你可以参考内省排序。