现在的位置: 首页 > 综合 > 正文

数组计数排序,类似于桶排序小问题

2013年09月05日 ⁄ 综合 ⁄ 共 1401字 ⁄ 字号 评论关闭
题目描述:http://ac.jobdu.com/problem.php?cid=1039&pid=16

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

输入:

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

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

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

输出:

对应每个测试案例,

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

样例输入:
5
43 24 12 57 45
样例输出:
12 24 43 45 57

代码AC:

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

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3.   
  4. int main()  
  5. {  
  6.     int age[99] = {0}, tmp;  // 依然是记录型的题目!^_^   
  7.     long int n, i, cou, j;  
  8.       
  9.     while( scanf("%ld", &n) != EOF )  
  10.     {  
  11.            memset( age, 0, sizeof( age ) );  
  12.              
  13.            for( i = 0; i < n; i++ )  
  14.            {  
  15.                 scanf("%d", &tmp);  
  16.                 age[tmp-1]++;  
  17.            }  
  18.              
  19.            cou = 0;  
  20.            for( i = 0; i < 99; i++ )  
  21.            {  
  22.                 if( age[i] )  
  23.                 {  
  24.                     cou += age[i];  
  25.                     for( j = 0; j < age[i]; j++ )  
  26.                     {  
  27.                          printf("%d ", i + 1);  
  28.                     }  
  29.                       
  30.                     if( cou == n )  // 无需再继续,所有人已扫描到!  
  31.                     {  
  32.                         break;  
  33.                     }  
  34.                 }  
  35.            }  
  36.              
  37.            printf("\n");  
  38.     }  
  39.       
  40.     return 0;  
  41. }  

这个就是简单的桶排序。因为一般情况下:桶排序是一个指针数组,即指针指向链表。这个链表就是所谓的桶。

下图就是桶排序的基本思想:

桶排序一般应用于海量数据中的应用。

抱歉!评论已关闭.