# 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"/>
