时间:2021-05-02
理解:
桶排序是计数排序的变种,把计数排序中相邻的m个"小桶"放到一个"大桶"中,在分完桶后,对每个桶进行排序(一般用快排),然后合并成最后的结果。
基本思想:
桶排序假设序列由一个随机过程产生,该过程将元素均匀而独立地分布在区间[0,1)上。我们把区间[0,1)划分成n个相同大小的子区间,称为桶。将n个记录分布到各个桶中去。如果有多于一个记录分到同一个桶中,需要进行桶内排序。最后依次把各个桶中的记录列出来记得到有序序列。
效率分析:
桶排序的平均时间复杂度为线性的O(N+C),其中C为桶内快排的时间复杂度。如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。此外,桶排序是稳定的。
桶排序的缺点是如果只排几个数,但是数字的范围却非常大(10个数,数的范围再0~10000000),那么我们需要10000001个桶才可以,即便是10个数。
举例
问题1:随机输入 5 个数,从大到小输出。
思路:借助一个根据输入数字最大值和最小值的范围数组,每当输入一个数字的时候,将数字插入对应数组的序号。
问题2:对0-1000的整数进行排序
? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include<stdio.h> int main() { int book[1001],i,j,t; //初始化桶数组 for(i=0;i<=1000;i++) { book[i] = 0; } //输入一个数n,表示接下来有n个数 scanf("%d",&n); for(i = 1;i<=n;i++) { //把每一个数读到变量中去 scanf("%d",&t); //计数 book[t]++; } //从大到小输出 for(i = 1000;i>=0;i--) { for(j=1;j<=book[i];j++) printf("%d",i); } getchar();getchar(); return 0; }声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了C语言基本排序算法之桶式排序。分享给大家供大家参考,具体如下:桶式排序是对一个有n个整型元素的数组a[n],其中对任意i,0
Linux的rename命令有两个版本,一个是C语言版本的,一个是Perl语言版本的,早期的Linux发行版基本上使用的是C语言版本的,现在已经很难见到C语言版
本文实例为大家分享了数据结构c语言版迷宫问题栈实现的具体代码,供大家参考,具体内容如下程序主要参考自严蔚敏老师的数据结构c语言版,在书中程序的大体框架下进行了完
前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。本文从最简单的一个排序算法——桶排序开始,分析桶排序的实现思路,代码实现
桶排序桶排序(Bucketsort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方