基數(shù)排序
基本思想：對元素分別按照個位、十位、百位....N位進行排序。
具體步驟如下
1.待排序算組array
待排序數(shù)組
2.創(chuàng)建一個10行*array.length列的二維數(shù)組sortArray。
二維數(shù)組
3.選出array中的最大值max，值為48，這是一個二位數(shù)，那么只需要排到十位即可，也就是排序兩次。
怎么進行排序呢？先進行個位的排序，將sortArray的每一行看成一個桶子，這個桶子用來存放array中元素個位與桶子序號相同的元素。例如21的個位是1，它將存放到1號桶子，循環(huán)array數(shù)組將所有元素放入二維數(shù)組，再循環(huán)之前先建立一個一位數(shù)組order，用來記錄每一個桶子里面的有多少個元素，桶子每插入一個元素，order對應(yīng)位置+1。結(jié)果如下。
按照個位排序
4.將二維數(shù)組中的元素取出來，覆蓋到array中，取出順序是從第一行的第一列開始，讀取完一行再讀取下一行，每一行讀取元素的個數(shù)，在order中都有記載，全部讀取完畢后，將order元素都初始化為0。結(jié)果如下，發(fā)現(xiàn)array已經(jīng)將個位排好序了。
個位排序結(jié)果
5.之后進行十位的排序，操作和上面相同。排序過程如下。
按照十位填入二維數(shù)組
取出二維數(shù)組的元素。
排序完成
因為max是二位數(shù)，所以十位排完就結(jié)束排序了。
完整代碼如下
/**
* 基數(shù)排序
* 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("數(shù)組中有數(shù)小于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));
}
}
