目錄
非比較類排序計數排序場景基數排序場景計數排序基數排序非比較類排序十大經典排序演算法江山圖
十大排序分類
終於來到了最後兩個演算法，非比較類的線性時間複雜度演算法，計數排序和基數排序。上一篇也提到過，這幾種排序算法理解起來都不難，時間、空間複雜度分析起來也很簡單，但是對要排序的資料要求很苛刻，上一篇提到的桶排序就是適用於外部排序中，即所謂的外部排序就是資料儲存在外部磁碟中，資料量比較大，記憶體有限，無法將資料全部載入到記憶體中。
計數排序其實是桶排序的一種特殊情況。當要排序的n個數據，所處的範圍並不大的時候，比如最大值是k，我們就可以把資料劃分成k個桶。每個桶內的資料值都是相同的，省掉了桶內排序的時間。
計數排序場景例如高考查分系統，系統會顯示我們的成績以及所在省的排名。如果你所在的省有50萬考生，如何透過成績快速排序得出名次呢?
❝
考生的滿分是900分，最小是0分，這個資料的範圍很小，所以我們可以分成901個桶，對應分數從0分到900分。根據考生的成績，我們將這50萬考生劃分到 這901個桶裡。桶內的資料都是分數相同的考生，所以並不需要再進行排序。我們只需要依次掃描每個桶，將桶內的考生依次輸出到一個數組中，就實現了50萬考生的排序。因為只涉及掃描遍歷操作，所以時間複雜度是O(n)。
❞
計數排序的演算法思想就是這麼簡單跟桶排序非常類似，只是桶的大小粒度不一樣。
基數排序場景假設我們有10萬個手機號碼，希望將這10萬個手機號碼從小到大排序，用什麼方法快速排序?
❝
對於桶排序、計數排序，手機號碼有11位，範圍太大，顯然不適合用這兩 種排序演算法。手機號碼有這樣的規律:假設要比較兩個手機號碼a，b的大小，如果在前面幾位中，a手機號碼已經比b手機號碼大了，那後面的幾位就不用看了。根據這個思路，先按照最後一位來排序手機號碼，然後，再按照倒數第二位重新排序，以此類推，最後按照第一位重新排序。經過11次排序之後，手機號碼就都有序了。
❞
這就是基數排序的演算法思路，基數排序對要排序的資料是有要求的，需要可以分割出獨立的“位”來比較，而且位之間有遞進的關係，如果「a」資料的高位比「b」資料大，那剩下的低 位就不用比較了。除此之外，每一位的資料範圍不能太大，要可以用線性排序演算法來排序，否則，基數排序的時間複雜度就無法做到 O(n) 了。
計數排序演算法思想就是把陣列元素值作為陣列的下標，然後用一個臨時陣列統計該元素出現的次數，例如 temp[i] = m, 表示元素 i 一共出現了 m 次。最後再把臨時陣列統計的資料從小到大彙總起來，此時彙總起來是資料是有序的。
動圖演示計數排序
由圖可知，計數排序需要開闢一個臨時陣列來儲存，先遍歷原陣列一個個放入，然後再遍歷臨時陣列一個個取出。
程式碼實現public class CountSort { public static int[] countSort(int[] arr) { if (arr == null || arr.length < 2) { return arr; } int length = arr.length; int max = arr[0]; int min = arr[0]; // 陣列的最大值與最小值 for (int i = 1; i < arr.length; i++) { if(arr[i] < min) { min = arr[i]; } if(max < arr[i]) { max = arr[i]; } } // 建立大小為max的臨時陣列 int[] temp = new int[max + 1]; // 統計元素i出現的次數 for (int i = 0; i < length; i++) { temp[arr[i]]++; } // 把臨時陣列統計好的資料彙總到原陣列 int k = 0; for (int i = 0; i <= max; i++) { for (int j = temp[i]; j > 0; j--) { arr[k++] = i; } } return arr; } public static void main(String[] args) { int[] arr = {21,4,12,42,46,23,27,11,6,5,33,29,41,46,40,13,31}; arr = countSort(arr); System.out.print("陣列排序之後："); for (int i=0; i<arr.length; i++) { System.out.print(arr[i] + "，"); } }}O(n+k)
空間複雜度分析O(n+k)
穩定性分析穩定
適用條件計數排序只能用在資料範圍不大的場景中，如果資料範圍「k」比要排序的資料「n」大很多，就不適合用計數排序了。而且，計數排序只能給非負整數排序，如果要排序的資料是其他型別的，要將其在不改變相對大小的情況下，轉化為非負整數。
比如，還是拿考生這個例子。如果考生成績精確到小數後一位，我們就需要將所有的分數都先乘以10，轉化成整數，然後再放到9010個桶內。再比如，如果要排序的資料中有負數，資料的範圍是[-1000, 1000]，那我們就需要先對每個資料都加1000，轉化成非負整數，因為陣列的下邊不可能是負數。
基數排序演算法思想分別以個，十，百...位上數字大小對陣列進行排序，最後歸納彙總得到整體有序的陣列。
動圖演示基數排序
這裡的數最多兩位數，少於兩位數的比較十位數的時候，可以十位數補0比較：
第一遍是按照個位數排的，得到的陣列是個位數有序；
第二遍再按照十位數排，得到的陣列全部有序；
程式碼實現import java.util.ArrayList;public class RadixSort { public static int[] radixSort(int[] arr) { if(arr == null || arr.length < 2) return arr; int n = arr.length; int max = arr[0]; // 最大值 for (int i = 1; i < n; i++) { if (max < arr[i]) { max = arr[i]; } } // 計算最大值是幾位數 int num = 1; while (max / 10 > 0) { num++; max = max / 10; } // 建立10個桶 ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(10); //初始化桶 for (int i = 0; i < 10; i++) { bucketList.add(new ArrayList<Integer>()); } // 進行每一趟的排序，從個位數開始排 for (int i = 1; i <= num; i++) { for (int j = 0; j < n; j++) { // 獲取每個數最後第 i 位是陣列 int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10; //放進對應的桶裡 bucketList.get(radio).add(arr[j]); } //合併放回原陣列 int k = 0; for (int j = 0; j < 10; j++) { for (Integer t : bucketList.get(j)) { arr[k++] = t; } //取出來合併了之後把桶清光資料 bucketList.get(j).clear(); } } return arr; } public static void main(String[] args) { int[] arr = {21,4,12,42,46,23,27,11,6,5,33,29,41,46,40,13,31}; arr = radixSort(arr); System.out.print("陣列排序之後："); for (int i=0; i<arr.length; i++) { System.out.print(arr[i] + "，"); } }}O(n*k)，k代表桶的個數
空間複雜度分析O(n+k)，k代表桶的個數
穩定性分析穩定。
適用條件需要可以分割出獨立的“位”來比較，而且位之間有遞進的關係，如果「a」資料的高位比「b」資料大，那剩下的低位就不用比較了。除此之外，每一位的資料範圍不能太大，要可以用線性排序演算法來排序，否則，基數排序的時間複雜度就無法做到O(n)了。
參考資料： 極客演算法訓練營，資料結構與演算法之美