九度oj 题目1374：所有员工年龄排序

题目描述：

公司现在要对所有员工的年龄进行排序，因为公司员工的人数非常多，所以要求排序算法的效率要非常高，你能写出这样的程序吗？

 

输入：

输入可能包含多个测试样例，对于每个测试案例，

输入的第一行为一个整数n(1<= n<=1000000)：代表公司内员工的人数。

输入的第二行包括n个整数：代表公司内每个员工的年龄。其中，员工年龄age的取值范围为(1<=age<=99)。

 

输出：

对应每个测试案例，

请输出排序后的n个员工的年龄，每个年龄后面有一个空格。

 

样例输入：

5 43 24 12 57 45

样例输出：

12 24 43 45 57

开始没多想，直接快排 1 #include <cstdio> 2 #include <algorithm> 3 4 int cmp(const void *a, const void *b) { 5 int at = *(int *)a; 6 int bt = *(int *)b; 7 return at > bt; 8 } 9 10 int num[1000002]; 11 int n; 12 13 int main(int argc, char const *argv[]) 14 { 15 while(scanf("%d",&n) != EOF) { 16 for(int i = 0; i < n; i++) { 17 scanf("%d",&num[i]); 18 } 19 qsort(num, n, sizeof(int), cmp); 20 for(int i = 0; i < n; i++) { 21 printf("%d ",num[i]); 22 } 23 puts(""); 24 } 25 return 0; 26 }

超时

立马改成堆排序

1 #include <cstdio> 2 #include <algorithm> 3 #include <queue> 4 using namespace std; 5 6 int n; 7 8 priority_queue <int, vector<int>,greater<int> >que; 9 int main(int argc, char const *argv[]) 10 { 11 while(scanf("%d",&n) != EOF) { 12 for(int i = 0; i < n; i++) { 13 int tmp; 14 scanf("%d",&tmp); 15 que.push(tmp); 16 } 17 while(!que.empty()) { 18 int t = que.top();que.pop(); 19 printf("%d ",t); 20 } 21 puts(""); 22 } 23 return 0; 24 }

居然还超时

仔细看了看题，改成桶排序

1 #include <cstdio> 2 #include <cstring> 3 int n; 4 int age[100]; 5 6 int main(int argc, char const *argv[]) 7 { 8 while(scanf("%d",&n) != EOF) { 9 memset(age, 0, sizeof(age)); 10 while(n--){ 11 int tmp; 12 scanf("%d",&tmp); 13 age[tmp]++; 14 } 15 for(int i = 1; i <= 99; i++) { 16 for(int j = 0; j < age[i];j++) { 17 printf("%d ",i); 18 } 19 } 20 puts(""); 21 } 22 return 0; 23 }

再优化一下

1 #include <cstdio> 2 #include <cstring> 3 int n; 4 int age[100] = {0}; 5 6 int main(int argc, char const *argv[]) 7 { 8 while(scanf("%d",&n) != EOF) { 9 while(n--){ 10 int tmp; 11 scanf("%d",&tmp); 12 age[tmp]++; 13 } 14 for(int i = 1; i <= 99; i++) { 15 while(age[i]) { 16 printf("%d ",i); 17 age[i]--; 18 } 19 } 20 puts(""); 21 } 22 return 0; 23 }

 

转载于:https://www.cnblogs.com/jasonJie/p/5810902.html

总结

以上是生活随笔为你收集整理的九度oj 题目1374：所有员工年龄排序的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。