【算法】排序算法之桶排序

在前幾回我們已經對 、 、 、 、 、 、 、 做了說明分析。本回，將對桶排序

一、排序算法系列目錄說明

二、桶排序（BucketSort）

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

1. 基本思想

桶排序的思想近乎徹底的分治思想。

桶排序假設待排序的一組數均勻獨立的分佈在一個範圍中，並將這一範圍劃分成幾個子範圍（桶）。

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

接著將各個桶中的數據有序的合併起來 : 對每個桶B[i] 中的所有元素進行比較排序 (可以使用快排)。然後依次枚舉輸出 B[0]….B[M] 中的全部內容即是一個有序序列。

補充： 映射函數一般是 f = array[i] / k; k^2 = n; n是所有元素個數

為了使桶排序更加高效，我們需要做到這兩點：

1. 在額外空間充足的情況下，儘量增大桶的數量

2. 使用的映射函數能夠將輸入的 N 個數據均勻的分配到 K 個桶中

同時，對於桶中元素的排序，選擇何種比較排序算法對於性能的影響至關重要。

2. 實現邏輯

• 設置一個定量的數組當作空桶子。
• 尋訪序列，並且把項目一個一個放到對應的桶子去。
• 對每個不是空的桶子進行排序。
• 從不是空的桶子裡把項目再放回原來的序列中。

3. 動圖演示

桶排序演示

分步驟圖示說明：設有數組 array = [63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 13, 28, 109]，對其進行桶排序：

4. 複雜度分析

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

最佳時間複雜度：O(n + k)

最差時間複雜度：O(n ^ 2)

空間複雜度：O(n * k)

穩定性：穩定

桶排序最好情況下使用線性時間O(n)，桶排序的時間複雜度，取決於對各個桶之間數據進行排序的時間複雜度，因為其它部分的時間複雜度都為O(n)。很顯然，桶劃分的越小，各個桶之間的數據越少，排序所用的時間也會越少。但相應的空間消耗就會增大。

5. 代碼實現

假設數據分佈在[0，100)之間，每個桶內部用鏈表表示，在數據入桶的同時插入排序。然後把各個桶中的數據合併。

<code>#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;
struct ListNode{
\texplicit ListNode(int i=0):mData(i),mNext(NULL){}
\tListNode* mNext;
\tint mData;
}; 

ListNode* insert(ListNode* head,int val){
\tListNode dummyNode;
\tListNode *newNode = new ListNode(val);
\tListNode *pre,*curr;
\tdummyNode.mNext = head;
\tpre = &dummyNode;
\tcurr = head;
\twhile(NULL!=curr && curr->mData<=val){
\t\tpre = curr;
\t\tcurr = curr->mNext;
\t}
\tnewNode->mNext = curr;
\tpre->mNext = newNode;
\treturn dummyNode.mNext;
}
ListNode* Merge(ListNode *head1,ListNode *head2){
\tListNode dummyNode;
\tListNode *dummy = &dummyNode;
\twhile(NULL!=head1 && NULL!=head2){
\t\tif(head1->mData <= head2->mData){
\t\t\tdummy->mNext = head1;
\t\t\thead1 = head1->mNext;
\t\t}else{
\t\t\tdummy->mNext = head2;
\t\t\thead2 = head2->mNext;
\t\t}
\t\tdummy = dummy->mNext;
\t}
\tif(NULL!=head1) dummy->mNext = head1;
\tif(NULL!=head2) dummy->mNext = head2;
\t
\treturn dummyNode.mNext;
}
void BucketSort(int n,int arr[]){
\tvector<listnode> buckets(BUCKET_NUM,(ListNode*)(0));
\tfor(int i=0;i\t\tint index = arr[i]/BUCKET_NUM;
\t\tListNode *head = buckets.at(index);
\t\tbuckets.at(index) = insert(head,arr[i]);
\t}
\tListNode *head = buckets.at(0);
\tfor(int i=1;i<bucket>\t\thead = Merge(head,buckets.at(i));
\t}
\tfor(int i=0;i\t\tarr[i] = head->mData;
\t\thead = head->mNext;
\t}
}/<bucket>/<listnode>/<vector>/<iostream>/<iterator>/<code> 

三、總結

桶排序是計數排序的變種，它利用了函數的映射關係，高效與否的關鍵就在於這個映射函數的確定。把計數排序中相鄰的m個”小桶”放到一個”大桶”中，在分完桶後，對每個桶進行排序（一般用快排），然後合併成最後的結果。

算法思想和散列中的開散列法差不多，當衝突時放入同一個桶中；可應用於數據量分佈比較均勻，或比較側重於區間數量時。

桶排序最關鍵的建桶，如果桶設計得不好的話桶排序是幾乎沒有作用的。通常情況下，上下界有兩種取法，第一種是取一個10n或者是2n的數，方便實現。另一種是取數列的最大值和最小值然後均分作桶.

下一篇預告：基數排序（Radix Sort）。欲知詳情，且聽下回分解。

PS: 更多精選內容資源分享，歡迎關注微信公眾號：『 developer1024 』

閱讀更多 休閒遊戲人 的文章

關鍵字: 算法 排序 冒泡排序