# 1. 介紹
基數排序是借助對多關鍵碼進行桶式排序的思想對單關鍵碼進行排序的。比如待排序數組`arr=[12, 34, 2, 100, 10, 50, 32, 6, 15]`，不妨還是先繪制一下排序流程：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-07 101541.png"/>
根據這個流程可以寫出其代碼為：
~~~
/**
* 非比較排序
* @author mengfou
* @date 2022-1-7
*/
public class RadixSortDemo {
public static void main(String[] args) {
int[] arr = new int[]{12, 34, 2, 100, 10, 50, 32, 6, 15};
new RadixSortDemo().radixSort(arr);
for (int i : arr) {
System.out.print(i+"\t");
}
System.out.println();
}
public void radixSort(int[] arr){
int digitalBits = getDigitalBits(arr);
Map<Integer, List<Integer>> bucket = new HashMap<>();
for (int i = 0; i < digitalBits; i++) { // 從個、十、...開始放置在桶中
for (int item : arr) {
int number = getNumberByBit(item, i);
List<Integer> orDefault = bucket.getOrDefault(number, new ArrayList<>());
orDefault.add(item);
bucket.put(number, orDefault);
}
// 從桶中取出元素，然后放置回arr
int k = 0;
for (Integer key : bucket.keySet()) {
List<Integer> value = bucket.getOrDefault(key, null);
if (value != null) {
for (Integer integer : value) {
arr[k++] = integer;
}
}
}
bucket = new HashMap<>();
}
}
/**
* 從數組number中獲取其個、十等的值
* @param number 待獲取數字
* @param i 標識位，0表示個位、1表示十位...
*/
private int getNumberByBit(int number, int i) {
number = number / (int) Math.pow(10, i);
return number % 10;
}
/**
* 獲取數組arr中最大的數的位數
* @param arr 待排序數組
* @return 數組中最大數的位數
*/
private int getDigitalBits(int[] arr) {
int maxVal = arr[0];
for (int i = 0; i < arr.length; i++) {
maxVal = Math.max(maxVal, arr[i]);
}
int bit = 0;
while(maxVal != 0){
bit++;
maxVal /= 10;
}
return bit;
}
}
~~~
比如上面案例的運行結果為：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-07 105633.png"/>
當然，有更加優雅的寫法。可以不使用`HashMap`和`ArrayList`，直接使用一個`0-9`的一個數組來存放其上的放置的數據的個數的統計，然后我們將待排序數組從后到前進行遍歷，可以知道對應的放置的桶的位置，由于其是最后一個放置在這個位置的數據，且其數據中我們存放的是其前綴和，故而可以根據其前綴和唯一確定一個下標位置，如下圖所示：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-07 143940.png"/>
上圖為一趟基數排序的結果，代碼如下：
~~~
/**
* 非比較排序
* @author mengfou
* @date 2022-1-7
*/
public class RadixSortDemo2 {
public static void main(String[] args) {
int[] arr = new int[]{12, 34, 2, 100, 10, 50,32,6,15};
new RadixSortDemo2().radixSort(arr);
for (int i : arr) {
System.out.print(i+"\t");
}
System.out.println();
}
public void radixSort(int[] arr){
int digitalBits = getDigitalBits(arr);
int[] bucket = new int[arr.length];
for (int i = 0; i < digitalBits; i++) { // 從個、十、...開始放置在桶中
int[] count = new int[10];
for (int item : arr) {
int number = getNumberByBit(item, i);
count[number]++;
}
// 前綴和數組
for (int j = 1; j < 10; j++) {
count[j] += count[j - 1];
}
// 從后往前遍歷，放置元素
for (int j = arr.length - 1; j >= 0; j--) {
int number = getNumberByBit(arr[j], i);
bucket[count[number] - 1] = arr[j];
count[number]--;
}
System.arraycopy(bucket, 0, arr, 0, arr.length);
}
}
/**
* 從數組number中獲取其個、十等的值
* @param number 待獲取數字
* @param i 標識位，0表示個位、1表示十位...
*/
private int getNumberByBit(int number, int i) {
number = number / (int) Math.pow(10, i);
return number % 10;
}
/**
* 獲取數組arr中最大的數的位數
* @param arr 待排序數組
* @return 數組中最大數的位數
*/
private int getDigitalBits(int[] arr) {
int maxVal = arr[0];
for (int i = 0; i < arr.length; i++) {
maxVal = Math.max(maxVal, arr[i]);
}
int bit = 0;
while(maxVal != 0){
bit++;
maxVal /= 10;
}
return bit;
}
}
~~~
如果打印一下每趟排序結果，那么結果為：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-07 144118.png"/>
