基數排序詳解及代碼示例

---

基數排序原理

基數排序通過處理每一位數字進行排序，分為 LSD（最低位優先） 和 MSD（最高位優先） 兩種方式。核心步驟：

1. 確定最大值：計算數組中最大數的位數。
2. 逐位排序：對每一位數字使用穩定排序（如計數排序）。

---

1. 標準LSD基數排序（處理正整數）

代碼示例

public class RadixSort {public static void radixSort(int[] arr) {if (arr == null || arr.length == 0) return;int max = Arrays.stream(arr).max().getAsInt();for (int exp = 1; max / exp > 0; exp *= 10) {countSort(arr, exp);}}private static void countSort(int[] arr, int exp) {int[] output = new int[arr.length];int[] count = new int[10]; // 0-9Arrays.fill(count, 0);// 統計當前位數字的出現次數for (int value : arr) {count[(value / exp) % 10]++;}// 累加計數for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 反向填充輸出數組（保證穩定性）for (int i = arr.length - 1; i >= 0; i--) {int index = (arr[i] / exp) % 10;output[count[index] - 1] = arr[i];count[index]--;}// 替換原數組System.arraycopy(output, 0, arr, 0, arr.length);}public static void main(String[] args) {int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};radixSort(arr);System.out.println(Arrays.toString(arr)); // [2, 24, 45, 66, 75, 90, 170, 802]}
}

---

2. 處理負數的LSD變體

代碼示例

通過偏移將負數轉換為正數后再排序：

public static void radixSortWithNegative(int[] arr) {if (arr == null || arr.length == 0) return;int min = Arrays.stream(arr).min().getAsInt();if (min < 0) {// 將所有數偏移到非負區間for (int i = 0; i < arr.length; i++) {arr[i] += -min;}}int max = Arrays.stream(arr).max().getAsInt();for (int exp = 1; max / exp > 0; exp *= 10) {countSort(arr, exp);}// 恢復原始值if (min < 0) {for (int i = 0; i < arr.length; i++) {arr[i] += min;}}
}

---

3. 基數為16的基數排序（十六進制）

代碼示例

public static void radixSortBase16(int[] arr) {int max = Arrays.stream(arr).max().getAsInt();for (int exp = 1; max / exp > 0; exp *= 16) {countSortBase16(arr, exp);}
}private static void countSortBase16(int[] arr, int exp) {int[] output = new int[arr.length];int[] count = new int[16]; // 0-15Arrays.fill(count, 0);for (int value : arr) {int digit = (value / exp) % 16;count[digit]++;}for (int i = 1; i < 16; i++) {count[i] += count[i - 1];}for (int i = arr.length - 1; i >= 0; i--) {int digit = (arr[i] / exp) % 16;output[count[digit] - 1] = arr[i];count[digit]--;}System.arraycopy(output, 0, arr, 0, arr.length);
}

---

4. MSD基數排序（遞歸實現）

代碼示例

public static void msdRadixSort(int[] arr) {msdSort(arr, 0, arr.length - 1, 1); // 從最低位開始（假設初始位權為1）
}private static void msdSort(int[] arr, int low, int high, int exp) {if (low >= high) return;// 使用計數排序處理當前位int[] count = new int[10];for (int i = low; i <= high; i++) {count[(arr[i] / exp) % 10]++;}// 累加計數并移動元素for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}int[] temp = new int[arr.length];for (int i = high; i >= low; i--) {int digit = (arr[i] / exp) % 10;temp[count[digit] - 1] = arr[i];count[digit]--;}// 回填到原數組for (int i = low; i <= high; i++) {arr[i] = temp[i];}// 遞歸處理高位for (int i = 0; i < 10; i++) {if (count[i] > 0) {msdSort(arr, low, low + count[i] - 1, exp * 10);low += count[i];}}
}

---

變體對比表格

變體名稱	差異描述	時間復雜度	空間復雜度	穩定性
標準LSD	處理正整數，從最低位到最高位排序	O(nk)	O(n + k)	穩定
負數LSD變體	處理負數，通過偏移轉換為正數	O(nk)	O(n + k)	穩定
基數為16的變體	每位基數為16，適用于十六進制	O(nk)	O(n + 16)	穩定
MSD基數排序	從最高位開始，遞歸處理各桶	O(nk)	O(n + k)	穩定

---

關鍵說明

• 時間復雜度：O(nk)，其中 n 是元素數量，k 是位數。
• 空間復雜度：通常為 O(n + k)，因需要額外的計數數組和臨時數組。
• 穩定性：所有變體均使用計數排序作為中間步驟，因此穩定性保持。