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

题目描述：

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

输入：

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

输入的第一行为一个整数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[1000002];
int n;
 
int main(int argc, char const *argv[])
{
    while(scanf("%d",&n) != EOF) {
        for(int i = 0; i < n; i++) {
            scanf("%d",&num[i]);
        }
        qsort(num, n, sizeof(int), cmp);
        for(int i = 0; i < n; i++) {
            printf("%d ",num[i]);
        }
        puts("");
    }
    return 0;
}

超时

立马改成堆排序

#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 = 0; 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 0;
}

居然还超时

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

#include <cstdio>
#include <cstring>
int n;
int age[100];
 
int main(int argc, char const *argv[])
{
    while(scanf("%d",&n) != EOF) {
        memset(age, 0, sizeof(age));
        while(n--){
            int tmp;
            scanf("%d",&tmp);
            age[tmp]++;
        }
        for(int i = 1; i <= 99; i++) {
            for(int j = 0; j < age[i];j++) {
                printf("%d ",i);
            }
        }
        puts("");
    }
    return 0;
}

再优化一下

#include <cstdio>
#include <cstring>
int n;
int age[100] = {0};

int main(int argc, char const *argv[])
{
    while(scanf("%d",&n) != EOF) {
        while(n--){
            int tmp;
            scanf("%d",&tmp);
            age[tmp]++;
        }
        for(int i = 1; i <= 99; i++) {
            while(age[i]) {
                printf("%d ",i);
                age[i]--;
            }
        }
        puts("");
    }
    return 0;
}