桶排序(Bucket Sort)演算法是先將大量資料分類成少量資料後,再進行排序的演算法。可以透過簡單的運算式來完成資料的分類,在最好的情況之下,資料可以被完全打散,此時的時間複雜度就會是一個線性時間。



桶排序法(Bucket Sort)

桶排序法的概念

桶排序法會將資料先分類丟進不同的桶子中,接著再將所有桶子以插入排序等適合少量資料的演算法進行排序之後,再依照桶子的順序把桶子中的元素串接在一起,如此一來就能完成所有排序。在一開始的分類資料的時候,也要注意到桶子的順序,譬如要將一個整數序列進行遞增排序,我們可以把值比較小的整數群丟進第一個桶子中;把值比較大的整數群丟進第二個桶子中。

桶排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

現在有九個桶子,用來分別儲存0~9、10~19、20~29、30~39、40~49、50~59、60~69、70~79、80~89的整數資料。

桶子號碼    0   1   2   3   4   5   6   7   8
桶子內容   []  []  []  []  []  []  []  []  []

要如何將陣列遞增排列呢?

我們可以走訪陣列中的所有元素,元素值除10的整數部份即為其要被丟進去的桶子號碼。例如79這個元素,就會被丟進7這個號碼的桶子裡。所以在所有元素都依走訪順序被丟進桶子之後,桶子此時儲存的資料如下表:

桶子號碼        0             1             2             3             4             5             6             7             8
桶子內容   [9, 2]            []            []  [30, 38, 32]          [47]            []      [69, 61]          [79]          [81]

接著分別將這些桶子進行排序,排序後的結果如下:

桶子號碼        0             1             2             3             4             5             6             7             8
桶子內容   [2, 9]            []            []  [30, 32, 38]          [47]            []      [61, 69]          [79]          [81]

最後再依照桶子的順序,把桶子中的元素合併成序列,就會是已排序好的序列了!

桶排序法的程式實作

這邊的程式實作是以非常通用的方式來完成,先把資料的最小值、最大值,和每個桶子可儲存的元素數量先設定好,接著再算出最大需要的桶子個數,有了這些資訊之後再把桶子建立出來,元素可以依照其值落在哪個數值範圍,來被決定丟進哪個桶子。在實務上,為了使資料儘可能分散到不同的桶子中,實作起來並不會這麼地單純。

桶排序法的複雜度

桶排序法的複雜度主要還是得看其使用到的資料結構,如果是單純地類似以上實作的方式來完成,在此以#{{n}}#來表示要排序的資料筆數,以#{{k}}#來表示要排序的資料可能的值的數量,以#{{m}}#來表示桶子的數量。

項目 備註
最差時間複雜度 #{{O(n^2)}}# 元素都在同一個桶子中,而且使用的排序演算法也遭遇最差狀況。
最佳時間複雜度 #{{O(n + m)}}# 元素完全分散在不同的桶子中,完全不需進行排序。
平均時間複雜度 #{{O(n + {{n^2} \over m} + m )}}#
最差空間複雜度 #{{O(n + k)}}#
#{{O(n \times k)}}#
?
不預先配置桶子的空間。
預先配置桶子的空間。
使用了其它需要額外空間的排序演算法。
是否穩定
使用穩定排序法來排序每個桶子。
有使用到不穩定排序法。