桶排序是將待排序集合中處于同一個值域的元素存入同一個桶中，也就是根據元素值特性將集合拆分為多個區(qū)域，則拆分后形成的多個桶，從值域上看是處于有序狀態(tài)的。對每個桶中元素進行排序，則所有桶中元素構成的集合是已排序的。

快速排序是將集合拆分為兩個值域，這里稱為兩個桶，再分別對兩個桶進行排序，最終完成排序。桶排序則是將集合拆分為多個桶，對每個桶進行排序，則完成排序過程。兩者不同之處在于，快排是在集合本身上進行排序，屬于原地排序方式，且對每個桶的排序方式也是快排。桶排序則是提供了額外的操作空間，在額外空間上對桶進行排序，避免了構成桶過程的元素比較和交換操作，同時可以自主選擇恰當的排序算法對桶進行排序。

當然桶排序更是對計數排序的改進，計數排序申請的額外空間跨度從最小元素值到最大元素值，若待排序集合中元素不是依次遞增的，則必然有空間浪費情況。桶排序則是弱化了這種浪費情況，將最小值到最大值之間的每一個位置申請空間，更新為最小值到最大值之間每一個固定區(qū)域申請空間，盡量減少了元素值大小不連續(xù)情況下的空間浪費情況。

桶排序過程中存在兩個關鍵環(huán)節(jié)：

• 元素值域的劃分，也就是元素到桶的映射規(guī)則。映射規(guī)則需要根據待排序集合的元素分布特性進行選擇，若規(guī)則設計的過于模糊、寬泛，則可能導致待排序集合中所有元素全部映射到一個桶上，則桶排序向比較性質排序算法演變。若映射規(guī)則設計的過于具體、嚴苛，則可能導致待排序集合中每一個元素值映射到一個桶上，則桶排序向計數排序方式演化。
• 排序算法的選擇，從待排序集合中元素映射到各個桶上的過程，并不存在元素的比較和交換操作，在對各個桶中元素進行排序時，可以自主選擇合適的排序算法，桶排序算法的復雜度和穩(wěn)定性，都根據選擇的排序算法不同而不同。

算法過程

1. 根據待排序集合中最大元素和最小元素的差值范圍和映射規(guī)則，確定申請的桶個數；
2. 遍歷待排序集合，將每一個元素移動到對應的桶中；
3. 對每一個桶中元素進行排序，并移動到已排序集合中。

步驟 3 中提到的已排序集合，和步驟 1、2 中的待排序集合是同一個集合。與計數排序不同，桶排序的步驟 2 完成之后，所有元素都處于桶中，并且對桶中元素排序后，移動元素過程中不再依賴原始集合，所以可以將桶中元素移動回原始集合即可。

演示示例

待排序集合為：[-7, 51, 3, 121, -3, 32, 21, 43, 4, 25, 56, 77, 16, 22, 87, 56, -10, 68, 99, 70]
映射規(guī)則為：，其中常量位：，即以間隔大小 10 來區(qū)分不同值域
排序算法為：堆排序，根據堆排序特性可知， 個元素的集合，時間復雜度為：，算法不保持穩(wěn)定性

step 1:

遍歷集合可得，最大值為：，最小值為：，待申請桶的個數為：

step 2:

遍歷待排序集合，依次添加各元素到對應的桶中。

step 3:

對每一個桶中元素進行排序，并移動回原始集合中，即完成排序過程。

算法示例

def bucketSort(arr):
    maximum, minimum = max(arr), min(arr)
    bucketArr = [[] for i in range(maximum // 10 - minimum // 10 + 1)]  # set the map rule and apply for space
    for i in arr:  # map every element in array to the corresponding bucket
        index = i // 10 - minimum // 10
        bucketArr[index].append(i)
    arr.clear()
    for i in bucketArr:
        heapSort(i)   # sort the elements in every bucket
        arr.extend(i)  # move the sorted elements in bucket to array

第一個循環(huán)作用為將待排序集合中元素移動到對應的桶中，復雜度為 ；第二個循環(huán)的作用為對每個桶中元素進行排序，并移動回初始集合中，若桶個數為 ，平均每個桶中元素個數為 ，則復雜度為 。當 時，即桶排序向計數排序方式演化，則堆排序不發(fā)揮作用，復雜度為 ，只需要將元素移動回初始集合即可。當 時，即桶排序向比較性質排序算法演化，對集合進行堆排序，并將元素移動回初始集合，復雜度為 。

算法分析

由算法過程可知，桶排序的時間復雜度為 ，其中 表示桶的個數。由于需要申請額外的空間來保存元素，并申請額外的數組來存儲每個桶，所以空間復雜度為 。算法的穩(wěn)定性取決于對桶中元素排序時選擇的排序算法。由桶排序的過程可知，當待排序集合中存在元素值相差較大時，對映射規(guī)則的選擇是一個挑戰(zhàn)，可能導致元素集中分布在某一個桶中或者絕大多數桶是空桶的現象，對算法的時間復雜度或空間復雜度有較大影響，所以同計數排序一樣，桶排序適用于元素值分布較為集中的序列。

github 鏈接：桶排序