燕哥带你学算法 2014-12-05
基本解法
第一步
以LSD为例,假设原来有一串数值如下所示:
73,22,93,43,55,14,28,65,39,81
首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:
0181
222
3739343
414
55565
6
7
828
939
第二步
接下来将这些桶子中的数值重新串接起来,成为以下的数列:
81,22,73,93,43,14,55,65,28,39
接着再进行一次分配,这次是根据十位数来分配:
0114
22228
339
443
555
665
773
881
993
第三步
接下来将这些桶子中的数值重新串接起来,成为以下的数列:
14,22,28,39,43,55,65,73,81,93
这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
Java实现代码:
packagecom.algorithm.sort;
importjava.util.Arrays;
publicclassRadixSort{
//基于计数排序的基数排序算法
privatestaticvoidradixSort(int[]array,intradix,intdistance){
//array为待排序数组
//radix,代表基数
//代表排序元素的位数
intlength=array.length;
int[]temp=newint[length];//用于暂存元素
int[]count=newint[radix];//用于计数排序
intdivide=1;
for(inti=0;i<distance;i++){
System.arraycopy(array,0,temp,0,length);
Arrays.fill(count,0);
for(intj=0;j<length;j++){
inttempKey=(temp[j]/divide)%radix;
count[tempKey]++;
}
for(intj=1;j<radix;j++){
count[j]=count[j]+count[j-1];
}
//个人觉的运用计数排序实现计数排序的重点在下面这个方法
for(intj=length-1;j>=0;j--){
inttempKey=(temp[j]/divide)%radix;
count[tempKey]--;
array[count[tempKey]]=temp[j];
}
divide=divide*radix;
}
}
/**
*@paramargs
*/
publicstaticvoidmain(String[]args){
int[]array={3,2,3,2,5,333,45566,2345678,78,990,12,432,56};
radixSort(array,10,7);
for(inti=0;i<array.length;i++){
System.out.print(""+array[i]);
}
}
}