之前所学的排序都是基于比较的，通过两数的比较得出数的大小顺序，基于比较的算法最优的时间复杂度为n*lg(n)。

而计数排序采用了另一种方式，没有比较，让人眼前一亮。但需要特定的环境下才能行。比如输入数组需要是0~k之间的整数。

但他至少让排序能在线性时间O(n)内完成。

基数排序弥补了计数排序排列大数时需太多内存的缺陷，而且基数排序排列大数时时间也快一些。我的这个基数排序还可以改进。

1 #include
     
       2 #include
      
        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
       
        0){18             B[j]=i;19             j++;20             C[i]--;21         }    22     */23     for(i=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
         
          =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
         
        
       
      
     

 

推荐学习基数排序地址：http://www.cnblogs.com/hazir/archive/2011/05/05/2447290.html