本节开始讲一下分配排序中的基数排序，其实分配排序相对来说比较简单，基本上离不开一个桶/盒的概念，分配排序的思想，我认为也可以像归并排序那样描述为分治思想：
- 将数组元素按分配规则分配到一个个桶中
- 对桶中元素进行排序
- 桶和并，若未排好序，继续进行算法指定规则进行分配，直至排序完毕
不过分配排序和归并排序是有区别的：
归并的分我愿称之为递归逻辑的分化，假设拆分的两个数组有序，然后进行合并；为保证上述假设成立，对拆分的各自数组继续进行分化(归并排序)，其实是一种递归的思想（或者是实现逻辑）
而分配，我更倾向于称为一种简单的分配，相较于递归，更适合用循环来描述它。
说了不多不少的废话，就开始进入正题，基数排序：顾名思义，即按照数组的基数进行排序，核心逻辑如下：
- 确定数组中最大值的位数n，以此来确立排序的次数
- 对个位数进行分桶，按数组中的每个元素个位数的值，分别放置到初始化的bucket[0] ~ bucket[9]中（举例: 19个位数为9，放到bucket[9]中）
- 全部放完后，对每个桶进行排序，然后依次将0~9桶的元素合并，将值赋到原数组中
- 同2逻辑，不过是对数组中每个元素的十位数的值，进行分桶，排序，合并
- 同上，对每个元素的百位数，进行分桶，排序，合并
- 直至对n位数进行分桶，排序，合并
基数排序.png
笔者认为基数排序相对来说较为简单，顾不赘述上图中实例的桶排序逻辑，基本上看图结合核心逻辑即可理解，直接上代码~
public static void radixSort(int[] arrays) {
int max = Arrays.stream(arrays).max().getAsInt();
// 最大值的位数即为排序次数
int length = String.valueOf(max).length();
for (int i = 0; i < length; i++) {
//每次开始进行放到不同基数的桶中,每次排序都是新桶
List<List<Integer>> boxes = new ArrayList<>(10);
for (int j = 0; j < 10; j++) {
boxes.add(new ArrayList<>());
}
//依次看个位i=0，十位i=1，百位i=2...
for (int j = 0; j < arrays.length; j++) {
int temp = arrays[j];
for (int k = 0; k < i; k++) {
temp /= 10;
}
int remain = temp % 10;
boxes.get(remain).add(arrays[j]);
}
//放完全部的数组元素到box后，铺平，回填到arrays中
List<Integer> result = boxes.stream().flatMap(List::stream).collect(Collectors.toList());
//赋值到原数组
for (int j = 0; j < arrays.length; j++) {
arrays[j] = result.get(j);
}
}
}
之前希尔排序的时候我也说过，其实个人认为对组内(桶内)的元素进行排序，具体选择哪种排序方法其实是随意的；所以在此桶排序的代码中，我直接选用了Java的内置类库中的sort方法，避免桶内排序占用太大篇幅影响对代码逻辑的理解~
