1.桶排序特點

1.待排序數(shù)服從均勻分布；
2.待排序數(shù)可分配到多個單調的部分；
3..待排序數(shù)分配到哪個部分實現(xiàn)容易；
4.平局情況下時間復雜度為O(n)；
如下圖，即把排序數(shù)分配到M1，M2 ... M(k-1), M(k)這k分部分，且M(i) < M(j) ,i < j時。

算法-桶排序1.png

2.桶排序介紹

桶排序，假設輸入數(shù)據(jù)服從均勻分布，平局情況下它的時間復雜度為O(n)。把輸入數(shù)據(jù)可以均勻映射到區(qū)間[0,1)上，再把區(qū)間[0,1)劃分為n個相同大小的子區(qū)間，該子區(qū)間就稱為桶，然后將n個輸入數(shù)分別放到各個桶中，因為輸入數(shù)是均勻獨立分布在[0,1)區(qū)間，所以一般不會出現(xiàn)很多數(shù)集中落入一個桶內，對每個桶內的數(shù)進行排序，然后按桶的大小次序列出每個桶中排序好的數(shù)。

3.桶排序的偽代碼

BUCKET-SORT(A)
1  n = A.length
2  let B[0..n-1] be a new array
3  for i = 0 to n-1
4    make B[i] an empty list
5  for i = 0 to n-1
6    把A[i]插入到B[f(A[i])]桶中      // 該處的f(x)函數(shù)為一一映射函數(shù)，把A[i]映射[0,1)區(qū)間的某個數(shù)
7  for i = 0 to n-1
8    排序B[i]桶內的數(shù)
9  列出B[0],B[1] ... B[n-1]桶中的數(shù)即為排序好的順序

實例如下圖：

算法-桶排序2.png

4.時間和空間復雜度分析

1.時間復雜度
第1步，時間復雜度1
第2步，時間復雜度n
第3步，時間復雜度n
第4步，時間復雜度1
第5步，時間復雜度n
第6步，時間復雜度1
第7步，時間復雜度n
第8步，時間復雜度期望為2-1/n（這個與排序數(shù)均勻分布在各個桶有關）
第9步，時間復雜度n
因此時間復雜度為O(n)。

2.空間復雜度
多了B[0..n-1]且B[i]是一個列表，B[i]的期望空間是1