極客演算法訓練筆記(九)，十大經典排序之桶排序

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

大轉盤抽獎之分桶實現

桶排序

桶排序場景

演算法思想

圖解桶排序

程式碼實現

時間複雜度分析

空間複雜度分析

穩定性分析

適用條件

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

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

十大排序分類

如上圖所示（圖來自於極客時間演算法訓練營超哥的資料），我之前寫的七大排序演算法，都是比較類排序，最後三種是時間複雜度是O（n）的非比較類排序演算法：桶排序、計數排序、基數排序。因為這些排序演算法的時間複雜度是線性的，所以我們把這類排序演算法叫作線性排序（Linear sort）。之所以能做到線性的時間複雜度，主要原因是，這三個演算法是非基於比較的排序演算法，都不涉及元素之間的比較操作。

這幾種排序算法理解起來都不難，時間、空間複雜度分析起來也很簡單，但是對要排序的資料要求很苛刻，所以弄清楚這三種排序的適用場景是重點。

大轉盤抽獎之分桶實現

我想到了我實習負責寫的第一個業務，就是大轉盤抽獎，實現的核心抽獎演算法其實就是用的分桶。

業務場景：一個抽獎活動裡面有很多個獎品，每個獎品的中獎率都不一樣，其中的未中獎也相當於一種獎品，所有獎品中獎率加起來和是1，外表如下所示，想玩玩的朋友可以一鍵到達 http：//shop386997。kuaizhan。com/pages/marketing-package/fortune-wheel/fortune-wheel？id=5fd5b484fa079a000618c65a

大轉盤抽獎

例如上圖中，積分獎品，優惠券獎品，贈品獎品三種獎品機率分別為20%，20%，30%，那麼未中獎機率是30%。

我的實現：每次抽獎都生成一個1～100的隨機數，根據每個獎品後臺設定的中獎機率的大小進行分桶，隨機數在1～20代表中獎積分，在20～40內的數代表中獎優惠券，40～70內代表中獎贈品，70～100內的隨機數代表未中獎，這就是抽獎演算法的核心實現，這其實和分桶差不多，將100內的數分為了四個桶。

桶排序

桶排序場景

比如說我們有10GB的訂單資料，我們希望按訂單金額（假設金額都是正整數）進行排序，但是我們的記憶體有限，只有幾百MB，沒辦法一次性把10GB的資料都加載到記憶體中。這個時候該怎麼辦呢？

我們可以先掃描一遍檔案，看訂單金額所處的資料範圍。假設經過掃描之後我們得到，訂單金額最小是1元，最大是10萬元。我們將所有訂單根據金額劃分到100個桶裡，第一個桶我們儲存金額在1元到1000元之內的訂單，第二桶儲存金額在1001元到2000元之內的訂單，以此類推。每一個桶對應一個檔案，並且按照金額範圍的大小順序編號命名（00，01，02。。。99）。

理想的情況下，如果訂單金額在1到10萬之間均勻分佈，那訂單會被均勻劃分到100個檔案中，每個小檔案中儲存大約100MB的訂單資料，我們就可以將這100個小檔案依次放到記憶體中，用快排來排序。等所有檔案都排好序之後，我們只需要按照檔案編號，從小到大依次讀取每個小檔案中的訂單資料，並將其寫入到一個文件中，那這個檔案中儲存的就是按照金額從小到大排序的訂單資料了。

不過，你可能也發現了，訂單按照金額在1元到10萬元之間並不一定是均勻分佈的，所以10GB訂單資料是無法均勻地被劃分到100個檔案中的。有可能某個金額區間的資料特別多，劃分之後對應的檔案就會很大，沒法一次性讀入記憶體。這又該怎麼辦呢？

針對這些劃分之後還是比較大的檔案，我們可以繼續劃分，比如，訂單金額在1元到1000元之間的比較多，我們就將這個區間繼續劃分為10個小區間，1元到100元，101元到200元，201元到300元。。。901元到1000元。如果劃分之後，101元到200元之間的訂單還是太多，無法一次性讀入記憶體，那就繼續再劃分，直到所有的檔案都能讀入記憶體為止。

演算法思想

桶排序，顧名思義，會用到“桶”，核心思想是將要排序的資料分到幾個有序的桶裡，每個桶裡的資料再單獨進行排序（有可能再使用別的排序演算法或是以遞迴方式繼續使用桶排序進行排），桶內排完序後，再把每個桶裡的資料按照順序依次取出，組成的序列就是有序的了。

頗有點大事化小，小事化了的感覺

圖解桶排序

圖解桶排序

值得注意的是，桶的個數是人為指定的，不隨著陣列大小和數值大小改變（例如上面的例子中，可以根據檔案大小和記憶體大小，得到桶的個數）。

桶內的資料範圍是（max-min）/k 因為最後一組的原因向上取整，k是桶的個數，這個地方是（46-4）/5 向上取整得到9。

步驟：

先進行陣列的最大最小值的掃描，得到最值；

計算每個桶的額分割槽範圍；

遍歷原陣列，將每個值放到對應範圍的桶內，按照桶讀取資料就是有序的了；

程式碼實現

這裡假設每個桶的大小為5，程式碼實現如下：

import java。util。ArrayList；import java。util。Collections；/** * @author by zengzhiqin * 2020-12-13 */public class BucketSort { public static int［］ bucketSort（int［］ arr） { if （arr == null || arr。length < 2） { return arr； } int length = arr。length； double max = arr［0］； double 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］； } } // 桶的初始化 int bucketNum = 5； // 每個桶內還是陣列 ArrayList> bucketList = new ArrayList<>（bucketNum）； for （int i = 0； i < bucketNum； i++） { bucketList。add（new ArrayList<>（））； } // 分割槽大小 double section = Math。ceil（（max - min） / 5）； // 資料入桶 for （int i = 0； i < length； i++） { // 桶的序號 double bkt = Math。floor（（arr［i］ - min） / section）； System。out。println（arr［i］ + “ 這個數放到 ” + （int）bkt + “ 號桶”）； bucketList。get（（int）bkt）。add（arr［i］）； } // 對每個桶內的元素進行排序，使用jdk自帶的排序演算法，具體的原始碼分析我上一篇文章寫了（根據資料個數各種排序組合使用） for （int i = 0； i < bucketNum； i++） { Collections。sort（bucketList。get（i））； } // 把每個桶排序好的資料進行合併彙總放回原陣列 int index = 0； int i=0； for（ArrayList arrayList ： bucketList）{// System。out。print（i + “第幾組”）； for（int value ： arrayList）{// System。out。println（value）； arr［index］ = value； index++； } } 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 = bucketSort（arr）； System。out。print（“陣列排序之後：”）； for （int i=0； i