1 #include <stdio.h> 2 #include <string.h> 3 const int N = 10000; 4 const int RADIX = 10; 5 int a[N]; 6 int count[RADIX]; 7 void radixSort(int n) 8 { 9     int *bucket = new int[RADIX];10     int d = 1;11     int i;12     for(int k=1; k<=10; k++)//最大数为1<<32 - 1,为10位数13     {14         for(i=0; i<RADIX; ++i)15             count[i] = 0;16         for(i=0; i<n; ++i)17             count[a[i]/d%10] ++;18         for(i=1; i<RADIX; ++i)19             count[i] += count[i-1];20         for(i=RADIX-1; i>=0; --i)21         {22             int j = a[i]/d%10;23             bucket[count[j]-1] = a[i];24             count[j]--;25         }26         for(i=0; i<n; ++i)27             a[i] = bucket[i];28         d *= 10;29     }30 }31 int main()32 {33     int n,i;34     scanf("%d",&n);35     for(i=0; i<n; ++i)36         scanf("%d",&a[i]);37     radixSort(n);38     for(i=0; i<n; ++i)39         printf("%d ",a[i]);40     return 0;41 }