從《 基于比較的排序結(jié)構(gòu)總結(jié) 》中我們知道：全依賴“比較”操作的排序算法時間復(fù)雜度的一個下界O(N*logN)。但確實存在更快的算法。這些算法并不是不用“比較”操作，也不是想辦法將比較操作的次數(shù)減少到 logN。而是 利用對待排數(shù)據(jù)的某些限定性假設(shè) ，來避免絕大多數(shù)的“比較”操作。桶排序就是這樣的原理。

?

桶排序的基本思想

? ? ?? 假設(shè)有一組長度為N的待排關(guān)鍵字序列K[1....n]。首先將這個序列劃分成M個的子區(qū)間 (桶) 。然后基于 某種映射函數(shù) ，將待排序列的關(guān)鍵字k映射到第i個桶中(即桶數(shù)組B的下標(biāo) i) ，那么該關(guān)鍵字k就作為B[i]中的元素(每個桶B[i]都是一組大小為N/M的序列)。接著對每個桶B[i]中的所有元素進行比較排序(可以使用快排)。然后依次枚舉輸出B[0]....B[M]中的全部內(nèi)容即是一個有序序列。

?

[桶—關(guān)鍵字]映射函數(shù)

????? bindex=f(key)?? 其中，bindex 為桶數(shù)組B的下標(biāo)(即第bindex個桶), k為待排序列的關(guān)鍵字。桶排序之所以能夠高效，其關(guān)鍵在于這個映射函數(shù)，它必須做到： 如果關(guān)鍵字k1<k2，那么f(k1)<=f(k2)。也就是說B(i)中的最小數(shù)據(jù)都要大于B(i-1)中最大數(shù)據(jù)。 很顯然，映射函數(shù)的確定與數(shù)據(jù)本身的特點有很大的關(guān)系，我們下面舉個例子：

?

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

??????????????????????????????????????????????????????

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

?

桶排序代價分析

桶排序利用函數(shù)的映射關(guān)系，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當(dāng)于快排中劃分，已經(jīng)把大量數(shù)據(jù)分割成了基本有序的數(shù)據(jù)塊(桶)。然后只需要對桶中的少量數(shù)據(jù)做先進的比較排序即可。

?

對N個關(guān)鍵字進行桶排序的時間復(fù)雜度分為兩個部分：

(1) 循環(huán)計算每個關(guān)鍵字的桶映射函數(shù)，這個時間復(fù)雜度是O(N)。

(2) 利用先進的比較排序算法對每個桶內(nèi)的所有數(shù)據(jù)進行排序，其時間復(fù)雜度為? ∑ O(Ni*logNi) 。其中Ni 為第i個桶的數(shù)據(jù)量。

?

很顯然，第(2)部分是桶排序性能好壞的決定因素。盡量減少桶內(nèi)數(shù)據(jù)的數(shù)量是提高效率的唯一辦法(因為基于比較排序的最好平均時間復(fù)雜度只能達到O(N*logN)了)。因此，我們需要盡量做到下面兩點：

(1) 映射函數(shù)f(k)能夠?qū)個數(shù)據(jù)平均的分配到M個桶中，這樣每個桶就有[N/M]個數(shù)據(jù)量。

(2) 盡量的增大桶的數(shù)量。極限情況下每個桶只能得到一個數(shù)據(jù)，這樣就完全避開了桶內(nèi)數(shù)據(jù)的“比較”排序操作。 當(dāng)然，做到這一點很不容易，數(shù)據(jù)量巨大的情況下，f(k)函數(shù)會使得桶集合的數(shù)量巨大，空間浪費嚴(yán)重。這就是一個時間代價和空間代價的權(quán)衡問題了。

?

對于N個待排數(shù)據(jù)，M個桶，平均每個桶[N/M]個數(shù)據(jù)的桶排序平均時間復(fù)雜度為：

???????????? O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))= O(N+N*logN-N*logM)

當(dāng)N=M時，即極限情況下每個桶只有一個數(shù)據(jù)時。桶排序的最好效率能夠達到O(N)。

?

總結(jié)： 桶排序的平均時間復(fù)雜度為線性的O(N+C)，其中C=N*(logN-logM)。如果相對于同樣的N，桶數(shù)量M越大，其效率越高，最好的時間復(fù)雜度達到O(N)。 當(dāng)然桶排序的空間復(fù)雜度 為O(N+M)，如果輸入數(shù)據(jù)非常龐大，而桶的數(shù)量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩(wěn)定的。

?

其實我個人還有一個感受：在查找算法中，基于比較的查找算法最好的時間復(fù)雜度也是O(logN)。比如折半查找、平衡二叉樹、紅黑樹等。但是Hash表卻有O(C)線性級別的查找效率(不沖突情況下查找效率達到O(1))。大家好好體會一下：Hash表的思想和桶排序是不是有一曲同工之妙呢?

?

?

桶排序在海量數(shù)據(jù)中的應(yīng)用

?

一年的全國高考考生人數(shù)為 500 萬，分?jǐn)?shù)使用標(biāo)準(zhǔn)分，最低 100 ，最高 900 ，沒有小數(shù)，你把這 500 萬元素的數(shù)組排個序。

?

分析：對500W數(shù)據(jù)排序，如果基于比較的先進排序，平均比較次數(shù)為O(5000000*log5000000)≈1.112億。但是我們發(fā)現(xiàn)，這些數(shù)據(jù)都有特殊的條件：? 100=<score<=900。那么我們就可以考慮桶排序這樣一個 “投機取巧”的辦法、讓其在毫秒級別就完成500萬排序。

?

方法：創(chuàng)建801(900-100)個桶。將每個考生的分?jǐn)?shù)丟進f(score)=score-100的桶中。這個過程從頭到尾遍歷一遍數(shù)據(jù)只需要500W次。然后根據(jù)桶號大小依次將桶中數(shù)值輸出，即可以得到一個有序的序列。而且可以很容易的得到100分有***人，501分有***人。

?

實際上，桶排序?qū)?shù)據(jù)的條件有特殊要求，如果上面的分?jǐn)?shù)不是從100-900，而是從0-2億，那么分配2億個桶顯然是不可能的。 所以桶排序有其局限性，適合元素值集合并不大的情況。

?

?

源代碼

    #include<iostream.h>
#include<malloc.h>

typedef struct node{
	int key;
	struct node * next;
}KeyNode;

void inc_sort(int keys[],int size,int bucket_size){
	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; //記錄當(dāng)前桶中的數(shù)據(jù)量
		bucket_table[i]->next=NULL;
	}
	for(int j=0;j<size;j++){
		KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode));
		node->key=keys[j];
		node->next=NULL;
		//映射函數(shù)計算桶號
		int index=keys[j]/10;
		//初始化P成為桶中數(shù)據(jù)鏈表的頭指針
		KeyNode *p=bucket_table[index];
		//該桶中還沒有數(shù)據(jù)
		if(p->key==0){
			bucket_table[index]->next=node;
			(bucket_table[index]->key)++;
		}else{
			//鏈表結(jié)構(gòu)的插入排序
			while(p->next!=NULL&&p->next->key<=node->key)
				p=p->next;	
			node->next=p->next;
			p->next=node;
			(bucket_table[index]->key)++;
		}
	}
	//打印結(jié)果
	for(int b=0;b<bucket_size;b++)
		for(KeyNode *k=bucket_table[b]->next; k!=NULL; k=k->next)
			cout<<k->key<<" ";
	cout<<endl;
}

void main(){
	int raw[]={49,38,65,97,76,13,27,49};   
	int size=sizeof(raw)/sizeof(int);   
	inc_sort(raw,size,10);
}
  

?

?上面源代碼的桶內(nèi)數(shù)據(jù)排序，我們使用了基于單鏈表的直接插入排序算法。可以使用基于雙向鏈表的快排算法提高效率。

?

?

【排序結(jié)構(gòu)6】 桶排序