一、算法描述

假設有一組長度為N的待排關鍵字序列K[1....n]。

首先將這個序列劃分成M個的子區間(桶)。

然后基于某種映射函數 ，將待排序列的關鍵字k映射到第i個桶中(即桶數組B的下標 i) ，那么該關鍵字k就作為B[i]中的元素(每個桶B[i]都是一組大小為N/M的序列)。

對每個桶B[i]中的所有元素進行比較排序(可以使用快排)。

然后依次枚舉輸出B[0]....B[M]中的全部內容即是一個有序序列。

二、圖示

假如待排序列K= {49、38 、35、 97 、 76、 73 、 27、 49 }。
這些數據全部在1—100之間。因此我們定制10個桶，然后確定映射函數f(k)=k/10。
則第一個關鍵字49將定位到第4個桶中(49/10=4)。
依次將所有關鍵字全部堆入桶中，并在每個非空的桶中進行快速排序后得到如下圖所示：

　　　　　　　　　　
對上圖只要順序輸出每個B[i]中的數據就可以得到有序序列了。

三、性能描述

　 ??數據結構 ：數組

　　最差時間復雜度 ：O(n²)

　　平均時間復雜度 ：O(n+k)

　　最差空間復雜度 ：O(n*k)

四、總結

箱排序費空間。

箱排序只適用于關鍵字取值范圍較小的情況，否則所需箱子的數目m太多導致浪費存儲空間和計算時間。

五、偽代碼

void BucketSon(R){ //對R[0..n-1]做桶排序，其中0≤R[i].key<1(0≤i<n)for(i=0，i<n;i++) //分配過程．將R[i]插入到桶B[「n(R[i].key)」]中； //可插入表頭上for(i=0;i<n;i++) //排序過程 當B[i]非空時用插人排序將B[i]中的記錄排序；for(i=0，i<n；i++) //收集過程 若B[i]非空，則將B[i]中的記錄依次輸出到R中；}

?

?

?

?參考文檔：

　　1.?圖解"數據結構-內部排序算法"分配排序：箱排序、基數排序

?　　http://www.myexception.cn/other/918080.html

　　2.?http://zh.wikipedia.org/wiki/桶排序

?

轉載于:https://www.cnblogs.com/butyoux/archive/2013/01/18/2866166.html

總結

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

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