排序算法（九）：桶排序

桶排序是將待排序集合中處于同一個值域的元素存入同一個桶中朗兵，也就是根據(jù)元素值特性將集合拆分為多個區(qū)域，則拆分后形成的多個桶柿隙，從值域上看是處于有序狀態(tài)的叶洞。對每個桶中元素進(jìn)行排序，則所有桶中元素構(gòu)成的集合是已排序的禀崖。

快速排序是將集合拆分為兩個值域衩辟，這里稱為兩個桶，再分別對兩個桶進(jìn)行排序波附，最終完成排序艺晴。桶排序則是將集合拆分為多個桶，對每個桶進(jìn)行排序掸屡，則完成排序過程封寞。兩者不同之處在于，快排是在集合本身上進(jìn)行排序仅财，屬于原地排序方式狈究，且對每個桶的排序方式也是快排。桶排序則是提供了額外的操作空間盏求，在額外空間上對桶進(jìn)行排序谦炒，避免了構(gòu)成桶過程的元素比較和交換操作，同時可以自主選擇恰當(dāng)?shù)呐判蛩惴▽ν斑M(jìn)行排序风喇。

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

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

元素值域的劃分倦始，也就是元素到桶的映射規(guī)則斗遏。映射規(guī)則需要根據(jù)待排序集合的元素分布特性進(jìn)行選擇，若規(guī)則設(shè)計的過于模糊鞋邑、寬泛诵次，則可能導(dǎo)致待排序集合中所有元素全部映射到一個桶上账蓉，則桶排序向比較性質(zhì)排序算法演變。若映射規(guī)則設(shè)計的過于具體逾一、嚴(yán)苛铸本，則可能導(dǎo)致待排序集合中每一個元素值映射到一個桶上，則桶排序向計數(shù)排序方式演化遵堵。
排序算法的選擇箱玷，從待排序集合中元素映射到各個桶上的過程，并不存在元素的比較和交換操作陌宿，在對各個桶中元素進(jìn)行排序時锡足，可以自主選擇合適的排序算法，桶排序算法的復(fù)雜度和穩(wěn)定性壳坪，都根據(jù)選擇的排序算法不同而不同舶得。

算法過程

根據(jù)待排序集合中最大元素和最小元素的差值范圍和映射規(guī)則，確定申請的桶個數(shù)弥虐；
遍歷待排序集合扩灯，將每一個元素移動到對應(yīng)的桶中媚赖；
對每一個桶中元素進(jìn)行排序霜瘪，并移動到已排序集合中。

步驟 3 中提到的已排序集合惧磺，和步驟 1颖对、2 中的待排序集合是同一個集合。與計數(shù)排序不同磨隘，桶排序的步驟 2 完成之后缤底，所有元素都處于桶中，并且對桶中元素排序后番捂，移動元素過程中不再依賴原始集合个唧，所以可以將桶中元素移動回原始集合即可。

演示示例

待排序集合為：[-7, 51, 3, 121, -3, 32, 21, 43, 4, 25, 56, 77, 16, 22, 87, 56, -10, 68, 99, 70]
映射規(guī)則為： $f(x)=\frac x{10}-c$ 设预，其中常量位： $c=\frac {min}{10}$ 徙歼，即以間隔大小 10 來區(qū)分不同值域
排序算法為：堆排序，根據(jù)堆排序特性可知鳖枕， $K$ 個元素的集合魄梯，時間復(fù)雜度為： $Klog_2K$ ，算法不保持穩(wěn)定性

step 1:

遍歷集合可得宾符，最大值為： $max=121$ 酿秸，最小值為： $min=-10$ ，待申請桶的個數(shù)為： $\frac {max}{10}-\frac {min}{10}+1=12-(-1)+1=14$

step 2:

遍歷待排序集合魏烫，依次添加各元素到對應(yīng)的桶中辣苏。

桶下標(biāo)	桶中元素
0	-7, -3, -10
1	3, 4
2	16
3	21, 25, 22
4	32
5	43
6	51, 56, 56
7	68
8	77, 70
9	87
10	99
11
12
13	121

step 3:

對每一個桶中元素進(jìn)行排序肝箱，并移動回原始集合中，即完成排序過程考润。

算法示例

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)作用為將待排序集合中元素移動到對應(yīng)的桶中狭园，復(fù)雜度為 $O(N)$ ；第二個循環(huán)的作用為對每個桶中元素進(jìn)行排序糊治，并移動回初始集合中唱矛，若桶個數(shù)為 $M$ ，平均每個桶中元素個數(shù)為 $\frac NM$ 井辜，則復(fù)雜度為 $O(M*\frac NMlog_2{\frac NM}+N)=O(N+N(log_2N-log_2M))$ 绎谦。當(dāng) $M==N$ 時，即桶排序向計數(shù)排序方式演化粥脚，則堆排序不發(fā)揮作用窃肠，復(fù)雜度為 $O(N)$ ，只需要將元素移動回初始集合即可刷允。當(dāng) $M==1$ 時冤留，即桶排序向比較性質(zhì)排序算法演化，對集合進(jìn)行堆排序树灶，并將元素移動回初始集合纤怒，復(fù)雜度為 $O(N+Nlog_2N)$ 。

算法分析

由算法過程可知天通，桶排序的時間復(fù)雜度為 $O(N+N(log_2N-log_2M))$ 泊窘，其中 $M$ 表示桶的個數(shù)。由于需要申請額外的空間來保存元素像寒，并申請額外的數(shù)組來存儲每個桶烘豹，所以空間復(fù)雜度為 $O(N+M)$ 。算法的穩(wěn)定性取決于對桶中元素排序時選擇的排序算法诺祸。由桶排序的過程可知携悯，當(dāng)待排序集合中存在元素值相差較大時，對映射規(guī)則的選擇是一個挑戰(zhàn)筷笨，可能導(dǎo)致元素集中分布在某一個桶中或者絕大多數(shù)桶是空桶的現(xiàn)象憔鬼，對算法的時間復(fù)雜度或空間復(fù)雜度有較大影響，所以同計數(shù)排序一樣奥秆，桶排序適用于元素值分布較為集中的序列逊彭。

github 鏈接：桶排序