基數排序原理及實戰
- 2020 年 1 月 16 日
- 筆記
基數排序
原理
我們來看這樣一個排序問題。假設我們有 10 萬個手機號碼，希望將這 10 萬個手機號碼從小到大排序，你有什麼比較快速的排序方法呢？
我們之前講的快排，時間複雜度可以做到 O(nlogn)，還有更高效的排序演算法嗎？桶排序、計數排序能派上用場嗎？手機號碼有 11 位，範圍太大，顯然不適合用這兩種排序演算法。針對這個排序問題，有沒有時間複雜度是 O(n) 的演算法呢？現在我就來介紹一種新的排序演算法，基數排序。
剛剛這個問題里有這樣的規律：假設要比較兩個手機號碼 a，b 的大小，如果在前面幾位中，a 手機號碼已經比 b 手機號碼大了，那後面的幾位就不用看了。
藉助穩定排序演算法，這裡有一個巧妙的實現思路。還記得我們第 11 節中，在闡述排序演算法的穩定性的時候舉的訂單的例子嗎？我們這裡也可以藉助相同的處理思路，先按照最後一位來排序手機號碼，然後，再按照倒數第二位重新排序，以此類推，最後按照第一位重新排序。經過 11 次排序之後，手機號碼就都有序了。
手機號碼稍微有點長，畫圖比較不容易看清楚，我用字元串排序的例子，畫了一張基數排序的過程分解圖，你可以看下。
注意，這裡按照每位來排序的排序演算法要是穩定的，否則這個實現思路就是不正確的。因為如果是非穩定排序演算法，那最後一次排序只會考慮最高位的大小順序，完全不管其他位的大小關係，那麼低位的排序就完全沒有意義了。
根據每一位來排序，我們可以用剛講過的桶排序或者計數排序，它們的時間複雜度可以做到 O(n)。如果要排序的數據有 k 位，那我們就需要 k 次桶排序或者計數排序，總的時間複雜度是 O(k*n)。當 k 不大的時候，比如手機號碼排序的例子，k 最大就是 11，所以基數排序的時間複雜度就近似於 O(n)。
實際上，有時候要排序的數據並不都是等長的，比如我們排序牛津字典中的 20 萬個英文單詞，最短的只有 1 個字母，最長的我特意去查了下，有 45 個字母，中文翻譯是塵肺病。對於這種不等長的數據，基數排序還適用嗎？
實際上，我們可以把所有的單詞補齊到相同長度，位數不夠的可以在後面補「0」，因為根據ASCII 值，所有字母都大於「0」，所以補「0」不會影響到原有的大小順序。這樣就可以繼續用基數排序了。
我來總結一下，基數排序對要排序的數據是有要求的，需要可以分割出獨立的「位」來比較，而且位之間有遞進的關係，如果 a 數據的高位比 b 數據大，那剩下的低位就不用比較了。除此之外，每一位的數據範圍不能太大，要可以用線性排序演算法來排序，否則，基數排序的時間複雜度就無法做到 O(n) 了。
示例
import java.util.ArrayList; import java.util.List; /** * 基數排序 * （1）從低位開始，每一位用桶排序 * @author huangy on 2020-01-06 */ public class BaseSort { public static void baseSort(int[] arr) { // 計算出數字的最大位數 int digit = getMaxDigit(arr); // 遍歷每一位，依次進行桶排序 int digitValue; for (int k = 1; k <= digit; k++) { List<Node> nodeList = new ArrayList<>(arr.length); int maxDigitValue = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { // 取出該數字，當前位的值，不夠位則返回0 digitValue = getDigitValue(arr[i], k); Node node = new Node(); node.digitValue = digitValue; node.realValue = arr[i]; nodeList.add(node); if (digitValue > maxDigitValue) { maxDigitValue = digitValue; } } // 桶排序 int[] countArr = new int[maxDigitValue + 1]; for (Node node : nodeList) { countArr[node.digitValue]++; } int[] addressArr = new int[countArr.length]; addressArr[0] = countArr[0]; for (int j = 0; j < (addressArr.length - 1); j++) { addressArr[j + 1] = addressArr[j] + countArr[j + 1]; } // 先存放到臨時數組 List<Node> temNodeList = new ArrayList<>(nodeList); int i = nodeList.size() - 1; /* * 這裡一定要注意，從後往前遍歷，那麼才是穩定的桶排序演算法 * 因為addressArr存儲的元素的下標，從後往前，對應下標逐個減少 */ while (i >= 0) { Node node = nodeList.get(i); temNodeList.set((addressArr[node.digitValue] - 1), node); addressArr[node.digitValue]--; i--; } // 更新arr數組 for (int h = 0; h < arr.length; h++) { arr[h] = temNodeList.get(h).realValue; } System.out.print("按一位排序的結果："); for (i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } } private static int getMaxDigit(int[] arr) { int digit = 0; int tem, temDigit; for (int i = 0; i < arr.length; i++) { tem = arr[i]; temDigit = 0; while (tem != 0) { temDigit++; tem = tem / 10; } if (temDigit > digit) { digit = temDigit; } } return digit; } /** * 獲取某一位的值 * @param realValue 真正的值 * @param k 第幾位 */ private static int getDigitValue(int realValue, int k) { // 首先判斷有沒有這麼多位，沒有則返回0 int tem = 1; int temK = k - 1; while (temK > 0) { tem = tem * 10; temK--; } if (realValue < tem) { return 0; } // 獲取對應位數 temK = k - 1; while (temK > 0) { realValue /= 10; temK--; } return realValue % 10; } private static class Node { /** * 當前位的值 */ public int digitValue; /** * 真真的值 */ public int realValue; } public static void main(String[] args) { int[] arr = {342, 58, 576, 356}; baseSort(arr); System.out.print("最終結果: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }
