排序算法010-桶排序


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

happysneaker.com

图片来自《啊哈算法》

算法如下(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;  


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

108 100 50 22 15 6 1 1000 999 0

  运行结果是

1000 999 100 50 22 15 8 6 1 0


实在是简单。






Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论