(四)分配排序:基数排序(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--)

{

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;

}