基數排序是一種非比較型整數排序算法，它通過按數位從低位到高位依次處理數字，將每個數字根據當前數位的數值分配到不同的“桶”中，再按桶的順序收集回原數組，重複這一過程直到所有數位處理完畢。這種方法特別適合處理位數較少的整數，效率較高。
基數排序的基本思想¶
- 分配：按當前數位（如個位、十位、百位）將數字分配到對應的桶中。例如，個位數字爲3的數放入桶3，十位數字爲2的數放入桶2等。
- 收集：按桶的順序（0到9）依次取出桶中的數字，放回原數組，完成一次數位的排序。
- 重複：對每一個數位（從低位到高位）重複上述分配和收集過程，直到所有數位處理完畢。
舉例說明排序過程¶
以數組 [5, 3, 8, 12, 23, 100] 爲例，逐步演示排序過程：
初始數組¶
[5, 3, 8, 12, 23, 100]
第一輪：處理個位（radix=1）¶
每個數的個位數字爲：5（個位5）、3（個位3）、8（個位8）、12（個位2）、23（個位3）、100（個位0）。
- 分配到桶中：
桶0：[100]，桶2：[12]，桶3：[3, 23]，桶5：[5]，桶8：[8]，其他桶空。
- 收集回數組：[100, 12, 3, 23, 5, 8]。
第二輪：處理十位（radix=10）¶
每個數的十位數字爲：100（十位0）、12（十位1）、3（十位0）、23（十位2）、5（十位0）、8（十位0）。
- 分配到桶中：
桶0：[100, 3, 5, 8]，桶1：[12]，桶2：[23]，其他桶空。
- 收集回數組：[100, 3, 5, 8, 12, 23]。
第三輪：處理百位（radix=100）¶
每個數的百位數字爲：100（百位1）、3（百位0）、5（百位0）、8（百位0）、12（百位0）、23（百位0）。
- 分配到桶中：
桶0：[3, 5, 8, 12, 23]，桶1：[100]，其他桶空。
- 收集回數組：[3, 5, 8, 12, 23, 100]。
排序完成！
Java代碼實現¶
import java.util.ArrayList;
import java.util.List;
public class RadixSort {
public static void radixSort(int[] arr) {
if (arr == null || arr.length == 0) {
return; // 空數組直接返回
}
// 1. 找到數組中的最大數，確定最大數位
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
// 2. 按數位從低位到高位處理（個位、十位、百位...）
for (int radix = 1; max / radix > 0; radix *= 10) {
// 創建10個桶（0-9），用ArrayList動態存儲元素
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < 10; i++) {
buckets.add(new ArrayList<>());
}
// 3. 分配：將每個數按當前位數字放入對應桶
for (int num : arr) {
int currentDigit = (num / radix) % 10; // 獲取當前位數字
buckets.get(currentDigit).add(num);
}
// 4. 收集：按桶順序（0-9）放回原數組
int index = 0;
for (List<Integer> bucket : buckets) {
for (int num : bucket) {
arr[index++] = num;
}
}
}
}
// 測試代碼
public static void main(String[] args) {
int[] arr = {5, 3, 8, 12, 23, 100};
System.out.println("排序前：" + java.util.Arrays.toString(arr));
radixSort(arr);
System.out.println("排序後：" + java.util.Arrays.toString(arr));
}
}
代碼關鍵點解析¶
- 找到最大數：確定需要處理的最高數位（如最大數爲100時，需處理百位）。
- 獲取當前位：通過
(num / radix) % 10計算當前數位。例如：
- 個位：radix=1，(num / 1) % 10→ 直接取個位。
- 十位：radix=10，(num / 10) % 10→ 取十位。 - 桶的分配與收集：使用
ArrayList動態存儲每個桶的元素，避免預先確定桶容量，收集時按順序放回原數組。
時間與空間複雜度¶
- 時間複雜度：
O(d*(n+k))，其中d是最大數的位數，n是數組長度，k是基數（此處k=10）。若d和k固定，時間複雜度近似O(n)。 - 空間複雜度：
O(n+k)，需n個空間存儲數組，k個桶。
總結¶
基數排序通過“按位分配-收集”的方式實現排序，適合整數排序，尤其當數字位數較少時效率較高。代碼中使用 ArrayList 作爲桶，簡化了動態存儲過程，且保持了排序的穩定性（相同數字相對順序不變）。對於負數，可先分離正負再分別排序，最後合併。