桶排序 Bin Sort

平均情況下桶排序以線性時間運行。像計數排序一樣，桶排序也對輸入作了某種假設， 因而運行得很快。具體來說，計數排序假設輸入是由一個小范圍內的整數構成，而桶排序則 假設輸入由一個隨機過程產生，該過程將元素一致地分布在區間[0，1)上。

桶排序的思想就是把區間[0，1)劃分成n個相同大小的子區間，或稱桶，然后將n個輸入數分布到各個桶中去。因為輸入數均勻分布在[0，1)上，所以一般不會有很多數落在 一個桶中的情況。為得到結果，先對各個桶中的數進行排序，然后按次序把各桶中的元素列 出來即可。

在桶排序算法的代碼中，假設輸入是個含n個元素的數組A，且每個元素滿足0≤ A[i]<1。另外還需要一個輔助數組B[O..n-1]來存放鏈表實現的桶，并假設可以用某種機制來維護這些表。

桶排序的算法如下，其中floor(x)是地板函數，表示不超過x的最大整數。

procedure Bin_Sort(var A:List); begin 1 n:=length(A); 2 for i:=1 to n do 3 將A[i]插到表B[floor(n*A[i])]中; 4 for i:=0 to n-1 do 5 用插入排序對表B[i]進行排序; 6 將表B[0],B[1],...,B[n-1]按順序合并; end;

?

圖1 Bin_Sort的操作

圖1演示了桶排序作用于有10個數的輸入數組上的操作過程。(a)輸入數組A[1..10]。(b)在該算法的第5行后的有序表(桶)數組B[0..9]。桶i中存放了區間[i/10，(i+1)/10]上的值。排序輸出由表B[O]、B[1]、...、B[9]的按序并置構成。

要說明這個算法能證確地工作，看兩個元素A[i]和A[j]。如果它們落在同一個桶中，則它們在輸出序列中有著正確的相對次序，因為它們所在的桶是采用插入排序的。現假設它們落到不同的桶中，設分別為B[i']和B[j']。不失一般性，假設i'<j'。在算法的代碼中，當第6行中將B中的表并置起來時，桶B[i']中的元素先于桶B[j']中的元素，因而在輸出序列中A[i]先于A[j]。現在要證明A[i]≤A[j]。假設情況正好相反，我們有：

?i'=floor(n*A[i])≥floor(n*A[j])=j'

得矛盾 (因為i'<j')，從而證明桶排序能正確地工作。

現在來分析算法的運行時間。除第5行外，所有各行在最壞情況的時間都是O(n)。第5行中檢查所有桶的時間是O(n)。分析中唯一有趣的部分就在于第5行中插人排序所花的時間。

為分析插人排序的時間代價，設n_i為表示桶B[i]中元素個數的隨機變量。因為插入排序以二次時間運行，故為排序桶B[i]中元素的期望時間為E[O(n_i²)]=O(E[n_i²])，對各個桶中的所有元素排序的總期望時間為：

(1)

為了求這個和式，要確定每個隨機變量n_i的分布。我們共有n個元素，n個桶。某個元素落到桶B[i]的概率為l/n，因為每個桶對應于區間[0，1)的l/n。這種情況與投球的例子很類似：有n個球 (元素)和n個盒子 (桶)，每次投球都是獨立的，且以概率p=1/n落到任一桶中。這樣，n_i=k的概率就服從二項分布B(k;n,p)，其期望值為E[ni]=np=1，方差V[ni]=np(1-p)=1-1/n。對任意隨機變量X，有:

　 (2)

將這個界用到(1)式上，得出桶排序中的插人排序的期望運行時間為O(n)。因而，整個桶排序的期望運行時間就是線性的。

下面的Java Applet程序演示了桶排序的基本思想。

很抱歉，您的瀏覽器不支持Java Applet或者沒有打開Java Applet支持。

在該演示程序中，線性表的元素類型為整型，桶的標號為整數，算法將值為i的元素放入標號為i的桶中，再按照桶的標號的順序將元素依次取出，就得到了最終的排序結果。

返回頁首

---

本頁最后一次更新于10/13/2003
Email: Starfish.H@China.com
?2000 算法與數據結構 http://algorithm.126.com/ 版權所有 轉載請保留出處

總結

以上是生活随笔為你收集整理的桶排序 Bin Sort的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。