桶排序算法的理解及C语言版代码示例

2025-05-27 0 84

理解:
桶排序是计数排序的变种,把计数排序中相邻的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 个数,从大到小输出。
思路:借助一个根据输入数字最大值和最小值的范围数组,每当输入一个数字的时候,将数字插入对应数组的序号。

?

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

28
#include <stdio.h>

int main()

{

int a[11],i,j,t;

//初始化桶数组

for(i=0;i<=10;i++)

{

a[i] = 0;

}

//循环读入5个数

for(i = 1;i<=5;i++)

{

//把每一个数读到变量中去

scanf("%d",&t);

//计数

a[t]++;

}

//从大到小输出

for(i = 10;i>=0;i--)

{

for(j=1;j<=a[i];j++)

printf("%d",i);

}

getchar();getchar();

//getchar()用来暂停程序,以便查看程序输出的内容

//也可以用system("pause");来代替

return 0;

}

问题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;

}

收藏 (0) 打赏

感谢您的支持,我会继续努力的!

打开微信/支付宝扫一扫,即可进行扫码打赏哦,分享从这里开始,精彩与您同在
点赞 (0)

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

快网idc优惠网 建站教程 桶排序算法的理解及C语言版代码示例 https://www.kuaiidc.com/74521.html

相关文章

发表评论
暂无评论