看完点个赞，谢谢！ 

P1271

题目描述

学校正在选举学生会成员，有 n(n≤999)名候选人，每名候选人编号分别从 1 到 n，现在收集到了 m(m<=2000000) 张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

输入格式

输入 nn 和 mm 以及 mm 个选票上的数字。

输出格式

求出排序后的选票编号。

Input 输入

5 102 5 2 2 5 2 2 2 1 2

Output 输出

1 2 2 2 2 2 2 2 5 5

这题一看就是个排序题。

先说说各个排序算法的最大可排序元素数量（1秒内）

1 选择排序、插入排序、冒泡排序：10000次 

时间复杂度：

​​​​​​​​​​​​百度百科 时间复杂度​​​​​​​

2  快速排序、sort 函数排序：100000次 

时间复杂度：

3  堆排序、桶排序、基数排序、计数排序 100000000次 

时间复杂度：

堆排序参考：https://www.cnblogs.com/chengxiao/p/6129630.html

桶排序参考：https://blog.csdn.net/weixin_38426554/article/details/95931499

基数排序简单说就是一个数当基数，然后围绕那个数展开排序算法。

但是以上都不是这题要用的方法，下面才是

计数排序！

计数排序主要用在那种范围小但数数的个数超级多时使用

比如在 [1, 100] 的区间里有 50000 个数，这时就该用计数排序

说回那道题直接计数排序就行了。

那它是怎么实现的呢？

首先读入很多的数，然后读入时记录它是多少，这是需要一个计数的数组，比如 cnt。然后让那个数所对应的 cnt 数组的位置+1，（其实目的就是为了找出每个数输入了几次）。

接着输出时，比如从小到大输出，就可以看看最小的数出现了多少次，比如2次，假如最小数是1，那么就输出两个1，然后看2有多少个就输出多少个2，以此类推，知道输出完了所有数就OK。

以上就是大概的思路

现在给个程序：

注意：此题数据量极大，需用加速 cin 与 cout 的东西

    ios::sync_with_stdio(0);
    cin.tie(0);
   可参考：https://blog.csdn.net/zeekliu/article/details/124077201

//LG1271 21-07-30#include using namespace std;int main(){    ios::sync_with_stdio(0);    cin.tie(0);    int n,m;    int a[2000001],p[1000];    memset(p,0,sizeof(p));    cin>>n>>m;    for (int i=1;i>a[i];p[a[i]]++;    }    for (int i=1;i<=n;i++)    { for (int j=1;j<=p[i];j++)     cout<<i<<" ";    }    return 0;}