桶排序

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 int a[10010],w[10010],p[10010],o[10010];
 5 
 6 void Barrel_Sort( int *a , int n ,int mx )
 7 {
 8     int i ;
 9     memset ( w , 0 , sizeof(w) ) ;
10     for ( i = 1 ; i <= n ; i++ )
11         w[ a[i] ]++;
12     for ( i = 1 ; i <= mx ; i++ )
13         w[i] = w[i] + w[i-1] ;
14     for ( i = 1 ; i <= n ; i++ ) {
15         p[i] = w[a[i]] ;
16         w[a[i]]--;
17     }
18     for( i = 1 ; i <= n ; i++ )
19         o[p[i]] = i;
20 }
21 
22 int main()
23 {
24     int n,i,mx;
25     while ( scanf("%d" , &n) != EOF ) {
26 
27     mx = 0;
28     for( i = 1 ; i <= n ; i++ )
29     {
30         scanf ("%d" , &a[i] );
31         if ( a[i] > mx )
32             mx = a[i];
33     }
34     Barrel_Sort( a , n , mx );
35     for ( i = 1 ; i <= n ; i++ )
36     {
37         printf ("%d " , a[o[i]] );
38     }
39     printf ("
");
40     
41     }
42     return 0;
43 }
44
桶排序
桶排序为复杂度为O(n +　ｋ)，其中k为所排数的最大值。　