排序算法篇（基数排序）
基本解法
第一步
以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]);
}
}
}