瘋子的算法總結(六) 複雜排序算法 ② 桶排序

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

桶排序的基本思想

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

[桶—關鍵字]映射函數

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

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

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

桶排序代價分析

桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當于快排中劃分，已經把大量資料分割成了基本有序的資料塊(桶)。然後隻需要對桶中的少量資料做先進的比較排序即可。

對N個關鍵字進行桶排序的時間複雜度分為兩個部分：

(1) 循環計算每個關鍵字的桶映射函數，這個時間複雜度是O(N)。

(2) 利用先進的比較排序算法對每個桶内的所有資料進行排序，其時間複雜度為 ∑ O(Ni*logNi) 。其中Ni 為第i個桶的資料量。

很顯然，第(2)部分是桶排序性能好壞的決定因素。盡量減少桶内資料的數量是提高效率的唯一辦法(因為基于比較排序的最好平均時間複雜度隻能達到O(N*logN)了)。是以，我們需要盡量做到下面兩點：

(1) 映射函數f(k)能夠将N個資料平均的配置設定到M個桶中，這樣每個桶就有[N/M]個資料量。

(2) 盡量的增大桶的數量。極限情況下每個桶隻能得到一個資料，這樣就完全避開了桶内資料的“比較”排序操作。 當然，做到這一點很不容易，資料量巨大的情況下，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)，如果輸入資料非常龐大，而桶的數量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩定的。

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

桶排序在海量資料中的應用

一年的全國聯考考生人數為500 萬，分數使用标準分，最低100 ，最高900 ，沒有小數，你把這500 萬元素的數組排個序。

實際上，桶排序對資料的條件有特殊要求，如果上面的分數不是從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; //記錄目前桶中的資料量  
        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;  
        //映射函數計算桶号  
        int index=keys[j]/10;  
        //初始化P成為桶中資料連結清單的頭指針  
        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)++;  
        }  
    }  
    //列印結果  
    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);  
}