箱排序的變種。為了區(qū)別于上述的箱排序，姑且稱它為桶排序（實(shí)際上箱排序和桶排序是同義詞）。
桶排序的思想是把[0，1)劃分為n個大小相同的子區(qū)間，每一子區(qū)間是一個桶。然后將n個記錄分配到各個桶中。因?yàn)殛P(guān)鍵字序列是均勻分布在[0，1)上的，所以一般不會有很多個記錄落入同一個桶中。由于同一桶中的記錄其關(guān)鍵字不盡相同，所以必須采用關(guān)鍵字比較的排序方法(通常用插入排序)對各個桶進(jìn)行排序，然后依次將各非空桶中的記錄連接(收集)起來即可。
注意：
這種排序思想基于以下假設(shè)：假設(shè)輸入的n個關(guān)鍵字序列是隨機(jī)分布在區(qū)間[0，1)之上。若關(guān)鍵字序列的取值范圍不是該區(qū)間，只要其取值均非負(fù)，我們總能將所有關(guān)鍵字除以某一合適的數(shù)，將關(guān)鍵字映射到該區(qū)間上。但要保證映射后的關(guān)鍵字是均勻分布在[0，1)上的。
桶排序的平均時間復(fù)雜度是線性的，即O(n)。
箱排序只適用于關(guān)鍵字取值范圍較小的情況，否則所需箱子的數(shù)目m太多導(dǎo)致浪費(fèi)存儲空間和計算時間。
例如n=10，被排序的記錄關(guān)鍵字ki取值范圍是0到99之間的整數(shù)(36，5，16，98，95，47, 32，36，48)時，要用100個箱子來做一趟箱排序。（即若m=n2時，箱排序的時間O(m+n)=O(n2)）。

例子
一年的全國高考考生人數(shù)為500 萬，分?jǐn)?shù)使用標(biāo)準(zhǔn)分，最低100 ，最高900 ，沒有小數(shù)，你把這500 萬元素的數(shù)組排個序。
分析：對500W數(shù)據(jù)排序，如果基于比較的先進(jìn)排序，平均比較次數(shù)為O(5000000*log5000000)≈1.112億。但是我們發(fā)現(xiàn)，這些數(shù)據(jù)都有特殊的條件：  100=<score<=900。那么我們就可以考慮桶排序這樣一個“投機(jī)取巧”的辦法、讓其在毫秒級別就完成500萬排序。
方法：創(chuàng)建801(900-100)個桶。將每個考生的分?jǐn)?shù)丟進(jìn)f(score)=score-100的桶中。這個過程從頭到尾遍歷一遍數(shù)據(jù)只需要500W次。然后根據(jù)桶號大小依次將桶中數(shù)值輸出，即可以得到一個有序的序列。而且可以很容易的得到100分有***人，501分有***人。
實(shí)際上，桶排序?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ù)排序，我們使用了基于單鏈表的直接插入排序算法。可以使用基于雙向鏈表的快排算法提高效率。

最新評論