基數(shù)排序也是非比較的排序算法霜幼，對每一位進行排序嫩码，從最低位開始排序，復(fù)雜度為O(kn),為數(shù)組長度罪既，k為數(shù)組中的數(shù)的最大的位數(shù)铸题；
基數(shù)排序是按照低位先排序，然后收集琢感；再按照高位排序丢间，然后再收集；依次類推驹针，直到最高位烘挫。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序牌捷，再按高優(yōu)先級排序墙牌。最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前暗甥∠脖酰基數(shù)排序基于分別排序，分別收集撤防，所以是穩(wěn)定的虽风。
算法描述
取得數(shù)組中的最大數(shù)，并取得位數(shù)寄月；
arr為原始數(shù)組辜膝，從最低位開始取每個位組成radix數(shù)組；
對radix進行計數(shù)排序（利用計數(shù)排序適用于小范圍數(shù)的特點）
動圖展示
算法分析：
時間復(fù)雜度
最佳情況：T(n) = O(n * k) 最差情況：T(n) = O(n * k) 平均情況：T(n) = O(n * k)
基數(shù)排序有兩種方法：
MSD 從高位開始進行排序 LSD 從低位開始進行排序
基數(shù)排序 vs 計數(shù)排序 vs 桶排序
這三種排序算法都利用了桶的概念漾肮，但對桶的使用方法上有明顯差異：
基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶
計數(shù)排序：每個桶只存儲單一鍵值
桶排序：每個桶存儲一定范圍的數(shù)值厂抖、
public static int[] RadixSort(int[] array) {
if (array == null || array.length < 2)
return array;
// 1.先算出最大數(shù)的位數(shù)；
int max = array[0];
for (int i = 1; i < array.length; i++) {
max = Math.max(max, array[i]);
}
int maxDigit = 0;
while (max != 0) {
max /= 10;
maxDigit++;
}
int mod = 10, div = 1;
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++)
bucketList.add(new ArrayList<Integer>());
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
for (int j = 0; j < array.length; j++) {
int num = (array[j] % mod) / div;
bucketList.get(num).add(array[j]);
}
int index = 0;
for (int j = 0; j < bucketList.size(); j++) {
for (int k = 0; k < bucketList.get(j).size(); k++)
array[index++] = bucketList.get(j).get(k);
bucketList.get(j).clear();
}
}
return array;
}
