基数排序(radix sort)

我们知道假如一个正整数A大于数B,要么就是A的位数更多点,要是相同位数则从高往低数起,必有某一位大于B.
基数排序就是把一待排序的元素每一位(个,十,百...)拆分出来排序.先从个位,然后再十位.那么首先肯定要确定下待排序中的元素最大数有多少位.然后再借助一个临时数组和一个计数的大小为10的数组辅助每一轮的排序.
//先计算出待排序元素最大数的位数
int MaxDigit(int* arr, int len)
{
   int digit = 1;   //所有元素小于10时的默认最大位数为1
   int radix = 10;
   for(int i = 0; i < len; i++) //遍历整个序列
     {
         if(arr[i] > 10)
          {
             while( arr[i] >= radix)  //当大于等于10则最大位数为2,依此类推大于等于100是3
           {
              digit++;
             radix= radix*10;   
           }       
           }
      }
  return digit;
}
 
void RadixSort(int* arr, int len)
{
    int digit = MaxDigit(arr, len);  //待排序数组最大元素的位数为digit
    int* tmpArr = new int[ len] ;  //辅助排序的临时数组
    int count[10] = {0};        //索引0 - 9刚好对应数字0至9
    int radix = 1;
    int val ;  //计算出来的元素每一位的值
    int j; 
    for(int i = 1; i <= digit; i++) //i是1时对个位数排序,为2时对百位数排序
      {
          for(j = 0; j< 10; j++)
                count[j] = 0;
 
          for(j = 0; j < len; j ++)
            {
               val = (arr[j] / radix) %10; //计算每一位的数值.当radix为1时是个位,为100时则是百位数的值
               count[ val] ++;  //val的取值是索引0-9,每有一位元素的位数值与索引值相同则计数数组索引对应值加1
             }
         
        //这一步最为关键,很让人迷糊的.我们经过前面一步后,数组中每个索引对应的值是arr元素的个数.
        //要是把计数数组count中所有值加起来总数应该是len.现在用前一个值是自己本身的值相加得出的结果是左边所有
        //元素个数和,这在等会映射到tmpArr中时有用
            for(j = 1; j < 10; j ++)
                 count[j]  = count[j-1] + count[j];
 
        for(j = len - 1 ; j >=0; j--)
            {  www.zzzyk.com
               val = (arr[j] / radix) %10;
               tmpArr[count[val] - 1] = arr[j]; //把arr中的元素映射到tmpArr,并且是按位数排好序的.
               count[k]--;
            }
        
           for(j = 0; j < len; j++)
               arr[j] = tmpArr[j]; //把临时数组中按位排好序的元素拿回来
         
           radix = radix*10;
       }
      delete [] tmpArr;
}

补充：综合编程 , 其他综合 ,