本節(jié)開始講一下分配排序中的基數(shù)排序，其實分配排序相對來說比較簡單袱衷，基本上離不開一個桶/盒的概念敬察，分配排序的思想薪捍，我認(rèn)為也可以像歸并排序那樣描述為分治思想：
- 將數(shù)組元素按分配規(guī)則分配到一個個桶中
- 對桶中元素進(jìn)行排序
- 桶和并，若未排好序抽兆，繼續(xù)進(jìn)行算法指定規(guī)則進(jìn)行分配识补，直至排序完畢
不過分配排序和歸并排序是有區(qū)別的：
歸并的分我愿稱之為遞歸邏輯的分化，假設(shè)拆分的兩個數(shù)組有序辫红，然后進(jìn)行合并凭涂；為保證上述假設(shè)成立，對拆分的各自數(shù)組繼續(xù)進(jìn)行分化(歸并排序)厉熟，其實是一種遞歸的思想（或者是實現(xiàn)邏輯）
而分配导盅，我更傾向于稱為一種簡單的分配，相較于遞歸揍瑟，更適合用循環(huán)來描述它。
說了不多不少的廢話乍炉，就開始進(jìn)入正題绢片，基數(shù)排序：顧名思義，即按照數(shù)組的基數(shù)進(jìn)行排序岛琼，核心邏輯如下：
- 確定數(shù)組中最大值的位數(shù)n底循，以此來確立排序的次數(shù)
- 對個位數(shù)進(jìn)行分桶，按數(shù)組中的每個元素個位數(shù)的值槐瑞，分別放置到初始化的bucket[0] ~ bucket[9]中（舉例: 19個位數(shù)為9熙涤，放到bucket[9]中）
- 全部放完后，對每個桶進(jìn)行排序困檩，然后依次將0~9桶的元素合并祠挫，將值賦到原數(shù)組中
- 同2邏輯，不過是對數(shù)組中每個元素的十位數(shù)的值悼沿，進(jìn)行分桶等舔，排序，合并
- 同上糟趾，對每個元素的百位數(shù)慌植，進(jìn)行分桶，排序义郑，合并
- 直至對n位數(shù)進(jìn)行分桶蝶柿，排序，合并
基數(shù)排序.png
筆者認(rèn)為基數(shù)排序相對來說較為簡單非驮，顧不贅述上圖中實例的桶排序邏輯交汤，基本上看圖結(jié)合核心邏輯即可理解，直接上代碼~
public static void radixSort(int[] arrays) {
int max = Arrays.stream(arrays).max().getAsInt();
// 最大值的位數(shù)即為排序次數(shù)
int length = String.valueOf(max).length();
for (int i = 0; i < length; i++) {
//每次開始進(jìn)行放到不同基數(shù)的桶中,每次排序都是新桶
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]);
}
//放完全部的數(shù)組元素到box后喉誊，鋪平，回填到arrays中
List<Integer> result = boxes.stream().flatMap(List::stream).collect(Collectors.toList());
//賦值到原數(shù)組
for (int j = 0; j < arrays.length; j++) {
arrays[j] = result.get(j);
}
}
}
之前希爾排序的時候我也說過纵顾，其實個人認(rèn)為對組內(nèi)(桶內(nèi))的元素進(jìn)行排序伍茄，具體選擇哪種排序方法其實是隨意的；所以在此桶排序的代碼中施逾，我直接選用了Java的內(nèi)置類庫中的sort方法敷矫，避免桶內(nèi)排序占用太大篇幅影響對代碼邏輯的理解~
