桶排序是計數(shù)排序的升級版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個映射函數(shù)的確定，這篇文章就帶大家認識一下桶排序。

一、桶排序

桶排序（Bucket sort）或所謂的箱排序，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶里。每個桶再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序），最后依次把各個桶中的記錄列出來記得到有序序列。

一句話總結(jié)：劃分多個范圍相同的區(qū)間，每個子區(qū)間自排序，最后合并。

桶排序是計數(shù)排序的擴展版本，計數(shù)排序可以看成每個桶只存儲相同元素，而桶排序每個桶存儲一定范圍的元素，通過映射函數(shù)，將待排序數(shù)組中的元素映射到各個對應(yīng)的桶中，對每個桶中的元素進行排序，最后將非空桶中的元素逐個放入原序列中。

桶排序需要盡量保證元素分散均勻，否則當所有數(shù)據(jù)集中在同一個桶中時，桶排序失效。

二、桶排序原理

（1）核心思想：就是將大問題化小（分治思想）

1. 例如：數(shù)組：

2. 觀察知：數(shù)組的元素分布在（0~50）之間，我們可以將其分隔成五個區(qū)間分辨是[0~9],[19~19],[20~29],[30~39],[40~49];（桶的個數(shù)根據(jù)題意自定，只需確定好每個桶的存儲范圍就好；并非桶越多越好，也并非越少越好總之適當就好）;

3. 這五個區(qū)間看做五個桶；分別存放符合范圍的數(shù)字；

4. 將這五個區(qū)間分別排序，再輸出；

（2）圖片解析過程

三、C語言代碼實現(xiàn)如下：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define random_set(a,b) ((rand()%(b-a))+a)//獲取a~b范圍內(nèi)的隨機數(shù)

int main(void)
{
    int array_stu[50];//用來保存每個同學(xué)的分數(shù)
    int array_out[100];//用來保存排序后的數(shù)據(jù)
    
    srand((int)time(NULL));//設(shè)置隨機數(shù)的基準，這樣保證每次的運行結(jié)果不同
    
    /*先初始化兩個數(shù)組*/
    memset(array_stu, 0, sizeof(array_stu));
    memset(array_out, 0, sizeof(array_out));

    /*用程序隨機數(shù)給50個學(xué)生打分*/
    for(int i=0;i<50;i++)
    {
        array_stu[i] = random_set(1,99);
    }

    /*把50個學(xué)生的分數(shù)分別扔到對應(yīng)的桶里面去*/
    for(int i=0;i<50;i++)
    {
        for(int j=1;j<100;j++)
        {
            /*如果分數(shù)跟桶的編號一樣，就把這個桶的數(shù)據(jù)增加*/
            if(array_stu[i] ==j)
            {
                array_out[j] ++;
            }
        }
    }
    
    /*把排序后的數(shù)據(jù)輸出*/
    for(int i=0;i<100;i++)
    {
        /*有些同學(xué)的分數(shù)是一樣的*/
        while(array_out[i] > 0)
        {
            printf("%d\n",i);
            array_out[i]--;
        }
    }

    return (0);
}

如果我們編譯并運行上述程序，那么它應(yīng)該產(chǎn)生以下結(jié)果：

2
2
6
7
10
10
16
16
16
20
27
28
33
34
36
39
40
42
42
43
44
44
46
46
46
52
54
56
57
59
62
62
63
74
74
78
78
78
79
81
83
84
85
89
91
93
94
96
96
97

四、復(fù)雜度分析

（1）時間復(fù)雜度：O(N + C)

對于待排序序列大小為 N，共分為 M 個桶，主要步驟有：

1. N 次循環(huán)，將每個元素裝入對應(yīng)的桶中

2. M 次循環(huán)，對每個桶中的數(shù)據(jù)進行排序（平均每個桶有 N/M 個元素）

一般使用較為快速的排序算法，時間復(fù)雜度為O(NlogN)，實際的桶排序過程是以鏈表形式插入的。

整個桶排序的時間復(fù)雜度為：

O(N)+O(M?(N/M?log(N/M)))=O(N?(log(N/M)+1))

當 N = M 時，復(fù)雜度為 O ( N ) 

（2）額外空間復(fù)雜度：O(N + M)

五、穩(wěn)定性分析

桶排序的穩(wěn)定性取決于桶內(nèi)排序使用的算法。