题意
排序，25MB大数据，都是整数，最大100最小0，内存极其紧张。
思路
面对这种数据范围很小，量很大的情况，考虑计数排序，原理非常简单就是开个数组统计一下不同值有多少个数字就搞定了，时间O(n)。
能做到O(n)的排序算法还有Sleep Sort，不过因为利用多线程睡眠差异太难控制所以也没啥实际意义。
被卡常数的时候，也可以考虑用计数排序进行没什么卵用的优化（结果可能就真卡过了）。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; int cnt[101]; int main(){ int n; while(scanf(" %d",&n) != EOF && n){ memset(cnt,0,sizeof(cnt)); for(int i = 1; i <= n; i++){ int a; scanf(" %d",&a); cnt[a]++; } for(int i = 1; i <= 100; i++){ if(cnt[i]) if(n == cnt[i]){ for(int j = 1; j <= cnt[i]-1; j++){ printf("%d ",i); } printf("%d\n",i); }else{ for(int j = 1; j <= cnt[i]; j++){ printf("%d ",i); } } n -= cnt[i]; } } return 0; } |
