桶排序（BucketSort）
桶排序（Bucket sort）或所謂的箱排序败许，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶里。每個桶再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序），最后依次把各個桶中的記錄列出來記得到有序序列。桶排序是鴿巢排序的一種歸納結(jié)果郭变。當要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時候，桶排序使用線性時間（Θ(n)）涯保。但桶排序并不是比較排序诉濒，他不受到O(n log n)下限的影響。
1. 基本思想
桶排序的思想近乎徹底的分治思想夕春。
桶排序假設(shè)待排序的一組數(shù)均勻獨立的分布在一個范圍中未荒，并將這一范圍劃分成幾個子范圍（桶）。
然后基于某種映射函數(shù)f 及志，將待排序列的關(guān)鍵字 k 映射到第i個桶中 (即桶數(shù)組B 的下標i) 片排，那么該關(guān)鍵字k 就作為 B[i]中的元素 (每個桶B[i]都是一組大小為N/M 的序列 )。
接著將各個桶中的數(shù)據(jù)有序的合并起來 : 對每個桶B[i] 中的所有元素進行比較排序 (可以使用快排)速侈。然后依次枚舉輸出 B[0]….B[M] 中的全部內(nèi)容即是一個有序序列率寡。
補充： 映射函數(shù)一般是 f = array[i] / k; k^2 = n; n是所有元素個數(shù)
為了使桶排序更加高效，我們需要做到這兩點：
在額外空間充足的情況下倚搬，盡量增大桶的數(shù)量
使用的映射函數(shù)能夠?qū)⑤斎氲?N 個數(shù)據(jù)均勻的分配到 K 個桶中
同時冶共，對于桶中元素的排序，選擇何種比較排序算法對于性能的影響至關(guān)重要。
2. 實現(xiàn)邏輯
設(shè)置一個定量的數(shù)組當作空桶子捅僵。
尋訪序列家卖，并且把項目一個一個放到對應(yīng)的桶子去。
對每個不是空的桶子進行排序庙楚。
從不是空的桶子里把項目再放回原來的序列中上荡。
