桶排序算法C/C++代码图文讲解

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定，这篇文章就带大家认识一下桶排序。

一、桶排序

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。

一句话总结：划分多个范围相同的区间，每个子区间自排序，最后合并。

桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。

桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。

二、桶排序原理

（1）核心思想：就是将大问题化小（分治思想）

1. 例如：数组：

2. 观察知：数组的元素分布在（0~50）之间，我们可以将其分隔成五个区间分辨是[0~9],[19~19],[20~29],[30~39],[40~49];（桶的个数根据题意自定，只需确定好每个桶的存储范围就好；并非桶越多越好，也并非越少越好总之适当就好）;

3. 这五个区间看做五个桶；分别存放符合范围的数字；

4. 将这五个区间分别排序，再输出；

（2）图片解析过程

三、C语言代码实现如下：

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

#define random_set(a,b) ((rand()%(b-a))+a)//获取a~b范围内的随机数

int main(void)
{
    int array_stu[50];//用来保存每个同学的分数
    int array_out[100];//用来保存排序后的数据
    
    srand((int)time(NULL));//设置随机数的基准，这样保证每次的运行结果不同
    
    /*先初始化两个数组*/
    memset(array_stu, 0, sizeof(array_stu));
    memset(array_out, 0, sizeof(array_out));

    /*用程序随机数给50个学生打分*/
    for(int i=0;i<50;i++)
    {
        array_stu[i] = random_set(1,99);
    }

    /*把50个学生的分数分别扔到对应的桶里面去*/
    for(int i=0;i<50;i++)
    {
        for(int j=1;j<100;j++)
        {
            /*如果分数跟桶的编号一样，就把这个桶的数据增加*/
            if(array_stu[i] ==j)
            {
                array_out[j] ++;
            }
        }
    }
    
    /*把排序后的数据输出*/
    for(int i=0;i<100;i++)
    {
        /*有些同学的分数是一样的*/
        while(array_out[i] > 0)
        {
            printf("%d\n",i);
            array_out[i]--;
        }
    }

    return (0);
}

如果我们编译并运行上述程序，那么它应该产生以下结果：

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

四、复杂度分析

（1）时间复杂度：O(N + C)

对于待排序序列大小为 N，共分为 M 个桶，主要步骤有：

1. N 次循环，将每个元素装入对应的桶中

2. M 次循环，对每个桶中的数据进行排序（平均每个桶有 N/M 个元素）

一般使用较为快速的排序算法，时间复杂度为O(NlogN)，实际的桶排序过程是以链表形式插入的。

整个桶排序的时间复杂度为：

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

当 N = M 时，复杂度为 O ( N ) 

（2）额外空间复杂度：O(N + M)

五、稳定性分析

桶排序的稳定性取决于桶内排序使用的算法。