基数排序
基本思想：对元素分别按照个位、十位、百位....N位进行排序。
具体步骤如下
1.待排序算组array
待排序数组
2.创建一个10行*array.length列的二维数组sortArray。
二维数组
3.选出array中的最大值max，值为48，这是一个二位数，那么只需要排到十位即可，也就是排序两次。
怎么进行排序呢？先进行个位的排序，将sortArray的每一行看成一个桶子，这个桶子用来存放array中元素个位与桶子序号相同的元素。例如21的个位是1，它将存放到1号桶子，循环array数组将所有元素放入二维数组，再循环之前先建立一个一位数组order，用来记录每一个桶子里面的有多少个元素，桶子每插入一个元素，order对应位置+1。结果如下。
按照个位排序
4.将二维数组中的元素取出来，覆盖到array中，取出顺序是从第一行的第一列开始，读取完一行再读取下一行，每一行读取元素的个数，在order中都有记载，全部读取完毕后，将order元素都初始化为0。结果如下，发现array已经将个位排好序了。
个位排序结果
5.之后进行十位的排序，操作和上面相同。排序过程如下。
按照十位填入二维数组
取出二维数组的元素。
排序完成
因为max是二位数，所以十位排完就结束排序了。
完整代码如下
/**
* 基数排序
* Created by ShouJingGuo on 2018/3/24.
*/
public class RadixSort {
private static final int BARREL_NUM = 10;
public static void radixSort(int[] array){
int max = getMax(array);
int[][] sortArray = new int[BARREL_NUM][array.length];
int[] order = new int[BARREL_NUM];
int i = 1, k = 0;
while(max > i){
for(int j = 0; j < array.length; j++){
int remainder = array[j] / i % 10;
sortArray[remainder][order[remainder]] = array[j];
order[remainder]++;
}
for(int index = 0; index < BARREL_NUM; index++){
for(int num = 0; num < order[index]; num++){
array[k++] = sortArray[index][num];
}
}
clearArray(order);
k = 0;
i *= 10;
}
}
private static void clearArray(int[] array){
for(int i = 0; i < array.length; i++){
array[i] = 0;
}
}
private static int getMax(int[] array){
int max = array[0];
for(int i = 0; i < array.length; i++){
if(array[i] < 0){
throw new RuntimeException("数组中有数小于0");
}
if(max < array[i]){
max = array[i];
}
}
return max;
}
public static void main(String[] args) {
int arr[] = {10,50,24,11,68,20,41,0,24,25,4,7,94,15,5,44,66};
RadixSort.radixSort(arr);
System.out.println(Arrays.toString(arr));
}
}
