所有员工年龄排序

忘是亡心i 2022-03-20 03:24 221阅读 0赞

**何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ**

**题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=16][http_ac.jobdu.com_problem.php_cid_1039_pid_16]**

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

**输入：**

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

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

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

**输出：**

对应每个测试案例，

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

**样例输入：**

43 24 12 57 45

**样例输出：**

12 24 43 45 57

代码AC：

思想：使用数组 int age\[99\] ，类似于 桶排序 的思想，扫描年龄，数组计数，然后再输出。

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        int age[99] = {0}, tmp;  // 依然是记录型的题目！^_^ 
        long int n, i, cou, j;
        
        while( scanf("%ld", &n) != EOF )
        {
               memset( age, 0, sizeof( age ) );
               
               for( i = 0; i < n; i++ )
               {
                    scanf("%d", &tmp);
                    age[tmp-1]++;
               }
               
               cou = 0;
               for( i = 0; i < 99; i++ )
               {
                    if( age[i] )
                    {
                        cou += age[i];
                        for( j = 0; j < age[i]; j++ )
                        {
                             printf("%d ", i + 1);
                        }
                        
                        if( cou == n )  // 无需再继续，所有人已扫描到！
                        {
                            break;
                        }
                    }
               }
               
               printf("\n");
        }
        
        return 0;
    }

[http_ac.jobdu.com_problem.php_cid_1039_pid_16]: http://ac.jobdu.com/problem.php?cid=1039&pid=16