排序算法010-桶排序

问题：请输入一串数字，并且输出从小到大的排序。

图片来自《啊哈算法》

算法如下（C语言）：

1. #include <stdio.h>  

2. int main()  

3. {  

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

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

6.         a[i]=0;  //初始化为0  

7.       

8.     for(i=1;i<=5;i++)  //循环读入5个数  

9.     {  

10.         scanf("%d",&t);  //把每一个数读到变量t中  

11.         a[t]++;  //进行计数  

12.     }  

13.   

14.     for(i=0;i<=10;i++)  //依次判断a[0]~a[10]  

15.         for(j=1;j<=a[i];j++)  //出现了几次就打印几次  

16.             printf("%d ",i);  

17.   

18.     getchar();getchar();   

19.     //这里的getchar();用来暂停程序，以便查看程序输出的内容  

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

21.     return 0;  

22. }

但是我们要求是从大到小排序，这该怎么办呢？其实很简单。只需要将 for(i=0;i<=10;i++) 改为 for(i=10;i>=0;i--) 就OK啦。

现在你可以请尝试一下输入n个0~1000之间的整数，将他们从大到小排序。提醒一下如果需要对数据范围在0~1000之间的整数进行排序，我们需要1001个桶，来表示0~1000之间每一个数出现的次数，这一点一定要注意。另外此处的每一个桶的作用其实就是“标记”每个数出现的次数，因此我喜欢将之前的数组a换个更贴切的名字book（book这个单词有记录、标记的意思），代码实现如下（C语言）：

1. #include <stdio.h>  

2. int main()  

3. {  

4.     int book[1001],i,j,t,n;  

5.     for(i=0;i<=1000;i++)  

6.         book[i]=0;   

7.     scanf("%d",&n);//输入一个数n，表示接下来有n个数  

8.     for(i=1;i<=n;i++)//循环读入n个数，并进行桶排序  

9.     {  

10.         scanf("%d",&t);  //把每一个数读到变量t中  

11.         book[t]++;  //进行计数，对编号为t的桶放一个小旗子  

12.     }  

13.     for(i=1000;i>=0;i--)  //依次判断编号1000~0的桶  

14.         for(j=1;j<=book[i];j++)  //出现了几次就将桶的编号打印几次  

15.              printf("%d ",i);  

16.   

17.     getchar();getchar();  

18.     return 0;  

19. } 

可以输入以下数据进行验证

108 100 50 22 15 6 1 1000 999 0

　　运行结果是

1000 999 100 50 22 15 8 6 1 0

实在是简单。

本文为 Jason 原创文章,转载请注明来自 7vs10.com

• 上一篇： Python入门准备
• 下一篇： Unity项目_《高仿微信跳一跳》