1void countSort(int* A, int n, int exp) {
2 int i, output[n], count[10]={0};
3 for(i=0;i<n;i++) count[(A[i]/exp)%10]++;
4 for(i=1;i<10;i++) count[i]+=count[i-1];
5 for(i=n-1;i>=0;i--) output[--count[(A[i]/exp)%10]]=A[i];
6 for(i=0;i<n;i++) A[i]=output[i];
7}
8void radixSort(int* A, int n) {
9 int i, max=A[0];
10 for(i=1;i<n;i++) if(A[i]>max) max=A[i];
11 for(int exp=1;max/exp>0;exp*=10) countSort(A,n,exp);
12}
