好程序員Java學習路線分享5分鐘了解基數排序

　　好程序員Java學習路線分享5分鐘了解基數排序，前言：基數排序無需進行比較和交換，而是利用分配和收集兩種基本操作實現排序。基數排序分為兩種：第一種是LSD ，從最低位開始排序；第二種是 MSD， 從最高位開始排序。

基數排序思想介紹

分配：對于數字，每位的取值范圍是0-9，因此需要10個容器（我們可以將其稱為桶），這10個桶標號為0-9。每趟排序時，我們取每一個元素在該位的數值依次放入桶中。

2. 收集：在一趟排序完成后，我們按順序從0-9的桶中依次取元素。

3. 繼續進行分配和收集，直到最大位數排序完成。

算法說明：

待排序數據：12, 34, 2, 123, 25, 59, 37

采用LSD，從低位開始排序

第一輪：取個位數，放入對應的桶，比如12的個位數是2，放到2號桶；34的個位數是4，放到4號桶

第一輪后，得到數據：12, 2, 123, 34, 25, 37, 59

第二輪：取十位數，放入桶中。比如2，十位數是0，放到0號桶

第二輪后，得到數據：2, 12, 123, 25, 34, 37, 59

第三輪：取百位數，放入桶

最后，得到有序數據 2, 12, 25, 34, 37, 59, 123

基數排序的代碼實現

private static void radixSort(int[] arr) {
//存儲最大值，暫時記錄為第一個元素
int max = arr[0];
//獲取待排序數組中的最大值
for (int v : arr) {
if (v > max) {
max = v;
}
}
// 用列表表示桶，一共10個桶，每個桶對應的元素也是列表
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i = 0; i < 10; i ++) {
list.add(new ArrayList<Integer>());
}
// 確定循環輪數
for(int i = 0, factor = 1; i < max; factor *= 10, i ++) {
for(int j = 0; j < arr.length; j ++) {
// 根據相應的位（個位/十位...）取通號，然后將數據放入桶中
list.get((arr[j] / factor) % 10).add(arr[j]);
}
// 遍歷桶，將其中數據放入arr數組中
for(int j = 0, k = 0; j < list.size(); j ++) {
while(!list.get(j).isEmpty()) {
arr[k] = list.get(j).get(0);
list.get(j).remove(0);
k++;
}
}
}
}

總結

基數排序是一種按記錄關鍵字的各位值逐步進行排序的方法。一般適用于記錄的關鍵字為整數類型的情況，對于字符串和文字排序不適合。