基數排序

基數排序是一種非比較排序，它的時間複雜度為O（K*N），其中k是最大那個數的長度，

1 //基數排序
 2 #include <stdio.h>
 3 #define MAX 1000000
 4 void print(int *a, int n)
 5 {
 6   int i;
 7   for (i = 0; i < n; i++)
 8     printf("%d\t", a[i]);
 9 }
10  
11 void radixsort(int *a, int n)
12 {
13   int i, b[MAX], m = a[0], exp = 1;
14   for (i = 1; i < n; i++)
15   {
16     if (a[i] > m)
17       m = a[i];
18   }
19  
20   while (m / exp > 0)
21   {
22     int bucket[10] ={ 0 };
23     for (i = 0; i < n; i++)
24       bucket[(a[i] / exp) % 10]++;
25     for (i = 1; i < 10; i++)
26       bucket[i] += bucket[i - 1];
27     for (i = n - 1; i >= 0; i--)
28       b[--bucket[(a[i] / exp) % 10]] = a[i];
29     for (i = 0; i < n; i++)
30       a[i] = b[i];
31     exp *= 10;
32   }
33 }
34  
35  
36 int arr[MAX];
37 int main()
38 {
39   int i, n;
40  
41   scanf("%d", &n);
42  
43   for (i = 0; i < n; i++)
44     scanf("%d", &arr[i]);
45   
46   radixsort(&arr[0], n);
47  
48   print(&arr[0], n);
49   printf("\n");
50  
51   return 0;
52 }      

View Code