排序算法篇（基数排序）

基本解法

第一步

以LSD为例，假设原来有一串数值如下所示：

73,22,93,43,55,14,28,65,39,81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

181

222

3739343

414

55565

6

7

828

939

第二步

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81,22,73,93,43,14,55,65,28,39

接着再进行一次分配，这次是根据十位数来分配：

114

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]);

}

}

}