基數(shù)排序是桶排序的擴(kuò)展，它將所有待排序的數(shù)值統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的前面補0，然后從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成后，待排序列就有序了。
1. 案例：
現(xiàn)有如下待排序列：
53 3 542 748 14 214
然后假如有如下10個桶(一維數(shù)組)，編號從0到9：
53，個位數(shù)是3，所以放在下標(biāo)為3的桶里。一輪下來，情況如下：
第一輪結(jié)束后，按照桶下標(biāo)順序，依次取出各桶中數(shù)據(jù)，放回原數(shù)組，所以原數(shù)組就變成了：
542 53 3 14 214 748
542，十位是4，所以放到下標(biāo)為4的桶里。一輪下來，情況如下：
第二輪結(jié)束后，按照桶下標(biāo)順序，依次取出桶中數(shù)據(jù)，放回原數(shù)組，所以原數(shù)組就變成了：
3 14 214 542 748 53
3，百位是0，所以放到下標(biāo)為0的桶里。一輪下來，情況如下：
第三輪結(jié)束后，按照桶下標(biāo)順序，依次取出桶中數(shù)據(jù)，放回原數(shù)組，所以原數(shù)組就變成了：
3 14 53 214 542 748
此時數(shù)組就是有序的了。總共要進(jìn)行幾輪呢？就是數(shù)組中最大數(shù)有多少位，就要進(jìn)行幾輪。通過這些分析大家發(fā)現(xiàn)啥沒有？每一輪的排序，就是對0到9數(shù)字排序，那豈不是很適合用計數(shù)排序？沒錯，就是這樣，所以，基數(shù)排序中，我們要做的就是每一輪都用計數(shù)排序就好了。
以下代碼就是基于計數(shù)排序?qū)崿F(xiàn)的，網(wǎng)上的一些基數(shù)排序教程可能會用二維數(shù)組來表示桶，這樣容易理解，但是非常浪費空間。
public static void radixSort(int[] arr) {
if (arr == null || arr.length == 1) {
return;
}
// 1. 先求數(shù)組中最大數(shù)的位數(shù)
int max = arr[0];
for(int i=1; i<arr.length; i++) {
max = arr[i] > max ? arr[i] : max;
}
int maxLength = (max + "").length();
// 2. 定義一個用來接收每一輪排序結(jié)果的數(shù)組
int[] result = new int[arr.length];
// 3. 定義一個長度為數(shù)據(jù)范圍的數(shù)組，每個數(shù)各數(shù)位只可能是0到9，所以數(shù)組長度為10
int[] count = new int[10];
// 4. 循環(huán)進(jìn)行排序
for(int i=0; i<maxLength; i++) {
// 5. 第一輪求個位，第二輪求十位……，求個位：num / 1 % 10，求百位：num / 10 % 10……
int division = (int)Math.pow(10, i); // 求10的次方
// 從這里開始其實就是計數(shù)排序
for(int j=0; j<arr.length; j++) {
int num = arr[j] / division % 10;
// num就是數(shù)組下標(biāo)值，然后該下標(biāo)對應(yīng)的元素值加1。count數(shù)組下標(biāo)和對應(yīng)的值就表示該數(shù)出現(xiàn)了多少次
count[num] ++;
}
// 6. 對count進(jìn)行變形，使其變成穩(wěn)定的
for(int x=1; x<count.length; x++) {
count[x] += count[x-1];
}
// 7. 逆序遍歷原數(shù)組
for(int y=arr.length-1; y>=0; y--) {
int num = arr[y] / division % 10;
result[count[num] - 1] = arr[y];
count[num]--;
}
// 8. 拷貝result到原數(shù)組
System.arraycopy(result, 0, arr, 0, arr.length);
// 9. 清空count，進(jìn)行下一輪的計數(shù)
Arrays.fill(count, 0);
}
}