極客演算法訓練筆記(十)，十大經典排序之計數排序、基數排序

非比較類排序

計數排序場景

基數排序場景

計數排序

基數排序

非比較類排序

十大經典排序演算法江山圖

十大排序分類

終於來到了最後兩個演算法，非比較類的線性時間複雜度演算法，計數排序和基數排序。上一篇也提到過，這幾種排序算法理解起來都不難，時間、空間複雜度分析起來也很簡單，但是對要排序的資料要求很苛刻，上一篇提到的桶排序就是適用於外部排序中，即所謂的外部排序就是資料儲存在外部磁碟中，資料量比較大，記憶體有限，無法將資料全部載入到記憶體中。

計數排序其實是桶排序的一種特殊情況。當要排序的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

時間複雜度分析

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> bucketList = new ArrayList<>（10）； //初始化桶 for （int i = 0； i < 10； i++） { bucketList。add（new ArrayList（））； } // 進行每一趟的排序，從個位數開始排 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

時間複雜度分析

O（n*k），k代表桶的個數

空間複雜度分析

O（n+k），k代表桶的個數

穩定性分析

穩定。

適用條件

需要可以分割出獨立的“位”來比較，而且位之間有遞進的關係，如果

「a」

資料的高位比

「b」

歡迎點贊分享在看，關注公眾號《阿甘的碼路》看更多內容，有問題可以加我微信私我指正，各大平臺也會同步只不過排版可能有些會不太一樣～