洛谷 P1271：选举学生会 ← 计数排序

​【题目来源】
https://www.luogu.com.cn/problem/P1271

【题目描述】
学校正在选举学生会成员，有 n（1≤n≤999）名候选人，每名候选人编号分别从 1 到 n，现在收集到了 m（1≤m≤2000000）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。设第 i（1≤i≤m）张选票上的数字为 ai，则保证有 1≤ai≤n。

【输入格式】
输入 n 和 m 以及 m 个选票上的数字。

【输出格式】
求出排序后的选票编号。​​​​​​​

【输入样例】
5 10
2 5 2 2 5 2 2 2 1 2​​​​​​​

【输出样例】
1 2 2 2 2 2 2 2 5 5

【数据范围】
1≤n≤999，1≤m≤2000000​​​​​​​

【算法分析】
● 此题可以简单地调用 sort 进行排序。不过为了学习，特地实现了一把“计数排序”。
● 计数排序是一种非比较型排序算法，当待排序的元素范围不是很大时，它非常高效，时间复杂度可以达到 O(n+k)，其中 n 是元素个数，k 是元素的范围大小。‌​​​​​​​

【算法代码：计数排序】

#include<bits/stdc++.h>
using namespace std;const int maxn=1000;
int cnt[maxn];int main() {int n,m,x;cin>>n>>m;while(m--) {cin>>x;cnt[x]++;}for(int i=1; i<maxn; i++) {while(cnt[i]) {cout<<i<<" ";cnt[i]--;}}return 0;
}/*
in:
5 10
2 5 2 2 5 2 2 2 1 2out:
1 2 2 2 2 2 2 2 5 5
*/

【参考文献】
https://www.luogu.com.cn/problem/solution/P1271






 

​