桶排序算法C/C++代码图文讲解 |
您所在的位置:网站首页 › 五个手指的命名法 › 桶排序算法C/C++代码图文讲解 |
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定,这篇文章就带大家认识一下桶排序。 一、桶排序 桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),最后依次把各个桶中的记录列出来记得到有序序列。 一句话总结:划分多个范围相同的区间,每个子区间自排序,最后合并。 桶排序是计数排序的扩展版本,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过映射函数,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序,最后将非空桶中的元素逐个放入原序列中。 桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。 二、桶排序原理 (1)核心思想:就是将大问题化小(分治思想) 1. 例如:数组: 2. 观察知:数组的元素分布在(0~50)之间,我们可以将其分隔成五个区间分辨是[0~9],[19~19],[20~29],[30~39],[40~49];(桶的个数根据题意自定,只需确定好每个桶的存储范围就好;并非桶越多越好,也并非越少越好总之适当就好); 3. 这五个区间看做五个桶;分别存放符合范围的数字; 4. 将这五个区间分别排序,再输出; (2)图片解析过程 三、C语言代码实现如下: #include #include #include #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 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |