- 题目描述：
公司现在要对所有员工的年龄进行排序，因为公司员工的人数非常多，所以要求排序算法的效率要非常高，你能写出这样的程序吗？
- 输入：
输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为一个整数n(1<= n<=1000000)：代表公司内员工的人数。
输入的第二行包括n个整数：代表公司内每个员工的年龄。其中，员工年龄age的取值范围为(1<=age<=99)。
- 输出：
对应每个测试案例，
请输出排序后的n个员工的年龄，每个年龄后面有一个空格。
- 样例输入：
5
43 24 12 57 45
- 样例输出：
12 24 43 45 57 开始没多想，直接快排
#include <cstdio>
#include <algorithm> int cmp(const void *a, const void *b) {
int at = *(int *)a;
int bt = *(int *)b;
return at > bt;
} int num[];
int n; int main(int argc, char const *argv[])
{
while(scanf("%d",&n) != EOF) {
for(int i = ; i < n; i++) {
scanf("%d",&num[i]);
}
qsort(num, n, sizeof(int), cmp);
for(int i = ; i < n; i++) {
printf("%d ",num[i]);
}
puts("");
}
return ;
}超时
立马改成堆排序
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std; int n; priority_queue <int, vector<int>,greater<int> >que;
int main(int argc, char const *argv[])
{
while(scanf("%d",&n) != EOF) {
for(int i = ; i < n; i++) {
int tmp;
scanf("%d",&tmp);
que.push(tmp);
}
while(!que.empty()) {
int t = que.top();que.pop();
printf("%d ",t);
}
puts("");
}
return ;
}居然还超时
仔细看了看题，改成桶排序
#include <cstdio>
#include <cstring>
int n;
int age[]; int main(int argc, char const *argv[])
{
while(scanf("%d",&n) != EOF) {
memset(age, , sizeof(age));
while(n--){
int tmp;
scanf("%d",&tmp);
age[tmp]++;
}
for(int i = ; i <= ; i++) {
for(int j = ; j < age[i];j++) {
printf("%d ",i);
}
}
puts("");
}
return ;
}再优化一下
#include <cstdio>
#include <cstring>
int n;
int age[] = {}; int main(int argc, char const *argv[])
{
while(scanf("%d",&n) != EOF) {
while(n--){
int tmp;
scanf("%d",&tmp);
age[tmp]++;
}
for(int i = ; i <= ; i++) {
while(age[i]) {
printf("%d ",i);
age[i]--;
}
}
puts("");
}
return ;
}