桶排序Bucket Sort從1956年就開始被使用，該算法的基本思想是由E.J.Issac? R.C.Singleton提出來。本博介紹BucketSort算法相關知識。 #### 算法描述與偽代碼 假設輸入的待排序元素是等可能的落在等間隔的值區間內.一個長度為N的數組使用桶排序, 需要長度為N的輔助數組. 等間隔的區間稱為桶, 每個桶內落在該區間的元素. 桶排序是基數排序的一種歸納結果.算法的主要思想: 待排序數組A[1...n]內的元素是隨機分布在[0,1)區間內的的浮點數.輔助排序數組B[0....n-1]的每一個元素都連接一個鏈表.將A內每個元素乘以N(數組規模)取底,并以此為索引插入(插入排序)數組B的對應位置的連表中**.**最后將所有的鏈表依次連接起來就是排序結果.這個過程可以簡單的分步如下: 1. 設置一個定量的數組當作空桶子。 1. 尋訪序列，并且把項目一個一個放到對應的桶子去。 1. 對每個不是空的桶子進行排序。 1. 從不是空的桶子里把項目再放回原來的序列中。 注意:1)note: 待排序元素越均勻, 桶排序的效率越高. 均勻意味著每個桶在中間過程中容納的元素個數都差不多,不會出現特別少或者特別多的情況, 這樣在排序子程序進行桶內排序的過程中會達到最優效率.2)note: 將元素通過恰當的映射關系將元素盡量等數量的分到各個桶(值區間)里面, 這個映射關系就是桶排序算法的關鍵.桶的標記(數組索引Index)的大小也要和值區間有對應關系 ~~~ BUCKET_SORT (A) n ← length [A] For i = 1 to n do Insert A[i] into list B[nA[i]] For i = 0 to n-1 do Sort list B with Insertion sort Concatenate the lists B[0], B[1], . . B[n-1] together in order. ~~~ **映射函數**bindex=f(key)?? 其中，bindex 為桶數組B的下標(即第bindex個桶), k為待排序列的關鍵字。桶排序之所以能夠高效，其關鍵在于這個映射函數，它必須做到：如果關鍵字k1<k2，那么f(k1)<=f(k2)。也就是說B(i)中的最小數據都要大于B(i-1)中最大數據。很顯然，映射函數的確定與數據本身的特點有很大的關系. ### 算法效率分析 桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當于快排中劃分，已經把大量數據分割成了基本有序的數據塊(桶)。然后只需要對桶中的少量數據做先進的比較排序即可。對N個關鍵字進行桶排序的時間復雜度分為兩個部分： 1. ?循環計算每個關鍵字的桶映射函數，這個時間復雜度是O(N)。 1. ?利用先進的比較排序算法對每個桶內的所有數據進行排序，其時間復雜度為? ∑ O(Ni*logNi) 。其中Ni 為第i個桶的數據量。 很顯然，第2部分是桶排序性能好壞的決定因素。盡量減少桶內數據的數量是提高效率的唯一辦法(因為基于比較排序的最好平均時間復雜度只能達到O(N*logN)了)。因此，我們需要盡量做到下面兩點： 1. 映射函數f(k)能夠將N個數據平均的分配到M個桶中，這樣每個桶就有[N/M]個數據量。 1. 盡量的增大桶的數量。極限情況下每個桶只能得到一個數據，這樣就完全避開了桶內數據的“比較”排序操作。 當然，做到這一點很不容易，數據量巨大的情況下，f(k)函數會使得桶集合的數量巨大，空間浪費嚴重。這就是一個時間代價和空間代價的權衡問題了。 對于N個待排數據，M個桶，平均每個桶[N/M]個數據的桶排序平均時間復雜度為： O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM) 當N=M時，即極限情況下每個桶只有一個數據時。桶排序的最好效率能夠達到O(N)。 總結： 桶排序的平均時間復雜度為線性的O(N+C)，其中C=N*(logN-logM)。如果相對于同樣的N，桶數量M越大，其效率越高，最好的時間復雜度達到O(N)。 當然桶排序的空間復雜度 為O(N+M)，如果輸入數據非常龐大，而桶的數量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩定的。 ### 參考代碼 ~~~ void BucketSort(int *A, int bucket_size){ int size =sizeof(A)/sizeof(int); KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *)); for(int i=0;i<bucket_size;i++){ bucket_table[i]=(KeyNode *)malloc(sizeof(KeyNode)); bucket_table[i]->key=0; bucket_table[i]->next=NULL; } for(int j=0;j<size;j++){ KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode)); node->key=A[j]; node->next=NULL; int index=A[j]/10; KeyNode *p=bucket_table[index]; if(p->key==0){ bucket_table[index]->next=node; (bucket_table[index]->key)++; } else{ while(p->next!=NULL&&p->next->key<=node->key) p=p->next; node->next=p->next; p->next=node; (bucket_table[index]->key)++; } } } ~~~ 注：上述部分codes采用桶內數據排序，我們使用了基于單鏈表的直接插入排序算法。可以使用基于雙向鏈表的快排算法提高效率。 關于[程序算法藝術與實踐](http://blog.csdn.net/column/details/tac-programalgrithm.html)更多討論與交流，敬請關注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).