目錄

十大經典排序演算法江山圖大轉盤抽獎之分桶實現桶排序桶排序場景演算法思想圖解桶排序程式碼實現時間複雜度分析空間複雜度分析穩定性分析適用條件十大經典排序演算法江山圖

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

十大排序分類

如上圖所示（圖來自於極客時間演算法訓練營超哥的資料），我之前寫的七大排序演算法，都是比較類排序，最後三種是時間複雜度是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<ArrayList<Integer>> 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<Integer> 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<arr.length; i++) {            System.out.print(arr[i] + "，");        }    }}

桶排序結果

根據這個圖回去看上面圖解分桶中，桶裡面的資料是不是如此，這裡是先進行了一遍陣列值的大小掃描，實際開發中很多業務場景下，我們自己知道資料的最大最小範圍，例如

時間複雜度分析

假設要排序的資料有n個，均勻地劃分到 k 個桶內。

遍歷所有元素入桶過程，時間複雜度為O(n);遍歷每個桶，進行排序，如果每個桶內只有一個元素，時間複雜度O(k);總的為 O(n+k);

實際上，這個還取決於桶內排序演算法，如果每個桶內元素很多，假設使用的桶內快排，實際的時間複雜度要比這個大。

看起來很美好，但是這是建立在美好假設的情況下，桶排序對排序的資料要求是非常苛刻的，下面看下桶排序的資料條件：

資料值比較均勻，在各個桶之間分佈就比較均勻；能確定資料的範圍，資料的跨度不會特別大； 第一條，如果桶排序之後有些桶資料特別多，有些特別少，那麼資料量多的桶內資料排序時間複雜度就會很高 第二條，資料跨度特別大，容易引起資料分佈不均，例如總共就5個數，0，10000，1000000，10000000，1000000000，這樣就很不好分桶，也就不適合桶排序。

桶排序比較適合用在外部排序中。所謂的外部排序就是資料儲存在外部磁碟中，資料量比較大，記憶體有限，無法將資料全部載入到記憶體中。

空間複雜度分析

O(n+k)。

穩定性分析

穩定。 資料進桶時可以控制相同元素的先後順序保持不變。

適用條件

用於均勻分佈的數字陣列.

往期類似推薦：

極客演算法訓練筆記(八)，十大經典排序之堆排序，被樹耽誤的陣列

極客演算法訓練筆記(七)，十大經典排序之歸併排序，全網最詳

極客演算法訓練筆記(六)，十大經典排序之希爾排序，快速排序

極客演算法訓練筆記(五)，十大經典排序之冒泡，選擇，插入排序

參考資料：極客時間演算法訓練營資料，資料結構與演算法之美