編程中梳理桶排序的邏輯

1. 什麼是桶排序，它和希爾排序的區別是什麼

桶排序 (Bucket sort)或所謂的箱排序，是一個排序演算法，工作的原理是將數組分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序並不是 比較排序，他不受到 O(n log n) 下限的影響。

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。該方法因DL．Shell於1959年提出而得名。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。

區別就是桶排序要求數據的長度必須完全一樣，而希爾排序是非穩定排序演算法。

2. 桶式排序

桶式排序不再是一種基於比較的排序方法，它是一種非常巧妙的排序方式，但這種排序方式需要待排序列滿足如下兩個特徵：

下面介紹桶式的詳細過程，以如下待排序列為例。
5、4、2、4、1
這個待排序列處於0、1、2、3、4、5這個可枚舉范圍內，而且這個范圍也很小，正是桶式排序待派用場之時。
具體步驟如下。
(1)對這個可枚舉范圍構建一個buckets數組，用於記錄「落入」每個桶中的元素的個數，於是可以得到下圖所示的buckets數組。

(2)對圖中所示的buckets數組的元素進行重新困備計算，按如下公式進行重新計算。
buckets[i]=buckets[i]+buckets[i-1] ；（其中1<= i < buckets.length）
即得到下圖所示的buckets數組。

上面理論還有點抽象。以待排序列中最後一個元素1為例，找到新buckets數組中元素1對應桶的值，該值為1，這表明元素1就應該排在第1位；再以待排碼返序列中倒數第2個元素4為例，找到新buckets數組中元素4對應桶的值，該值為4，這表明元素4就應該排在第4位……依此類推。

桶式排序是一種非常優秀的排序演算法，時間效率極高，
它只要經過2輪遍歷：
第1輪遍歷待排數據，統計每個待排數據「落入」各桶中的個數；
第2輪遍歷用於重新計算每個buckets數組元素的值。
2 輪遍歷後就可得到每個待排數據在有序序列中的位置，然後將各個數據項一次放入指定位置即可。
桶式排序的空間開銷較大，它需要兩個數組：第1個buckets數組用於記錄「落入」各桶中元素的個數，進而保存各元素在有序序列中的位置；第2個數組用於緩存待遲尺飢排數據。

桶式排序是穩定的。

3. 桶排序與哈希桶排序

桶排序 (箱排序)的原理是將待排序序列分到有限數量的桶裡面，然後對每個桶再分別排序（帆禪咐可以使用其它的排序演算法或者是遞歸使用桶排序演算法），最後將各個桶中的數據有序的合並起來成為一個整體有序的序列。
排序過程：
1.假設待排序的一組數統一的分布在一個范圍中，並將這一范圍劃分成幾個子范圍，也就是桶
2.將待排序的一組數，分檔規入這些子桶，並將桶中的數據進行排序
3.將各個桶中的數據有序的合並起來

設有數組 array = [29, 25, 3, 49, 9, 37, 21, 43]，那麼數組中最大數為 49，先設置 5 個桶，那麼每個桶可存放數的范圍為：09、1019、2029、3039、40~49，然後分別將這些數放人自己所屬的桶，如下圖：

1.時間復雜度：O(m+n)
2.空間復雜度：O(m+n)

適用於序列比較均勻的情況，否則會很耗空間。
或者特殊的場景，例如需要對一個公司的員工的年齡進行排序，年齡的范圍為1-120，此時就可以開辟120個桶進行統計排序。
另，桶排序的瓶頸主要是桶數量的選擇。
另此演算法為穩定的排序演算法。

排序演算法主要是用分治法，用哈希函數對序列進行劃分，最後使用其它的排序演算法或者遞歸使用哈希排序進行排序從而得到一個整體有序的序列。下面先介紹幾個自定義的概念：
1.哈希桶排序：因為本演算法是使用了哈希函數把序列劃分到對應的桶裡面，所以本排序演算法取名為哈希桶排序。
2.哈希桶因子（hashFactor）：hashFactor = （max - min） / length
計算公式如上式，當結果小於等於0的時候再做特殊處理，據此因子進行桶的劃分。

設有數組 array = [10011, 10001, 16, 14, 12, 10000, 10, 10002, 10003, 1]，那麼數組中最大值max = 10011，最小值min = 1，哈希桶因子hashFactor = （10011 - 1） / 10 = 1001。對數組進行劃分，10011 / 1001 = 10，所以10011放在keywei10的桶裡面；10001 / 1001 = 9， 所以10001放在key為9的桶裡面，以此類推，最後得到的桶態純的情況為：{0=[1, 10, 12, 14, 16], 9=[10000, 10001, 10002, 10003], 10=[10011]}。再分別對每個桶進行排序即可。

1.時間復雜度：O(m+n)
2.空間復雜度：O(m+n)

此演算法與桶排序對比，主要是通過哈希建桶的方式減少了空間的消耗，對序列進行了一個歸約襲伍，時間上跟桶排序相當。
使用與序列的最小最大值相差比較大同時又出現在某一個取值區間的集聚的情況。
另此演算法為穩定的排序演算法。

4. 桶排序怎麼實現

桶排序的實驗如下：

桶排序 (Bucket sort)或所謂的箱排序，是一個排序演算法，工作的原理是將數組分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別皮明的排序演算法或是以遞歸方式繼續使用桶排序進行排序）。

桶排序是鴿巢運拿排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序並不是 比較排序，他不受到O(nlogn) 下限的影響。

處理大量重復元素的情況：對於存在大量重復元素的情況，桶排序的效率也會比其他排序演算法高。因為桶排序在統計每個元素出現次數的過程中，相同元素只需計數一次，並存放在同一個桶里，不需要進行額外的比較和交換操作。

作為其他排序演算法的優化：桶排序還可以作為其他排序演算法的優化，提高其排序效率。比如，在快速排序中，每次選取的樞軸元素可能會導致某些分區的長度遠大於另一些分區，這就會影響快排的效率。此時可以使用桶排序對樞軸元素進行預處理，將數據分成若干個區域，再對燃悄告每個區域內的元素進行快排。