1 #include<stdio.h> 2 #include<math.h> 3  4 //计数排序，A为输入数组，B为输出数组，n为数组大小,k为数组中最大的数。 5 //时间复杂度为O(n+k)，取决于k，当k为O(n)时，则为线性时间。 6 //缺点为会浪费太多内存空间。 7 void COUNTING_SORT(int A[],int B[],int n,int k){ 8     int *C=malloc((k+1)*sizeof(int)); 9     int i,j=0;10     k=k+1;11     for(i=0;i<k;i++)12         C[i]=0;13     for(i=0;i<n;i++)14         C[A[i]]++;15     /*16     for(i=0,j=0;i<k;i++)17         while(C[i]>0){18             B[j]=i;19             j++;20             C[i]--;21         }    22     */23     for(i=1;i<k;i++)24         C[i]=C[i-1]+C[i];25     for(i=n-1;i>=0;i--){//排序稳定性26         B[C[A[i]]-1]=A[i];27         C[A[i]]--;28     }29 }30 31 //基数排序，n为数组大小，d为数组中最大数的长度;32 //h为进制，相当于计数排序中的k，可见减小了所需空间;33 //时间复杂度为O(d(n+h))34 void RADIX_SORT(int A[],int n,int d,int h){35     int i;36     int *C=malloc(h*sizeof(int));37     int *B=malloc(n*sizeof(int));38     int j=0;39     for(i=1;i<=d;i++){40         for(j=0;j<h;j++)41             C[j]=0;42         for(j=0;j<n;j++)43             C[((int)(A[j]/(pow(h,i-1)))%h)]++;44         for(j=1;j<h;j++)45             C[j]=C[j]+C[j-1];46         for(j=n-1;j>=0;j--){//排序稳定性47             B[C[((int)(A[j]/(pow(h,i-1)))%h)]-1]=A[j];48             C[((int)(A[j]/(pow(h,i-1)))%h)]--;49         }50         for(j=0;j<n;j++)51             A[j]=B[j];52     }53 }54 55 void main(){56     int i;57     int n;58     int A[8]={2,5,3,0,29,123,3200,38};59     int B[8]={0};60     n=sizeof(A)/sizeof(int);61     //COUNTING_SORT(A,B,n,3200);62     RADIX_SORT(A,n,4,10);63     for(i=0;i<n;i++)64         printf("%d\t",A[i]);65     printf("\n");66 }