守望者--AIR技术交流

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
热搜: ANE FlasCC 炼金术
查看: 296|回复: 1

[数学算法] 最快最简单的排序——桶排序

[复制链接]
  • TA的每日心情
    擦汗
    11 小时前
  • 签到天数: 433 天

    [LV.9]以坛为家II

    1739

    主题

    2091

    帖子

    12万

    积分

    超级版主

    Rank: 18Rank: 18Rank: 18Rank: 18Rank: 18

    威望
    457
    贡献
    24
    金币
    50924
    钢镚
    1419

    开源英雄守望者

    发表于 2016-8-15 16:06:12 | 显示全部楼层 |阅读模式

    在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总之很多东东都需要排序,可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。

    首先出场的是我们的主人公小哼,上面这个可爱的娃就是啦。期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有5个同学,这5个同学分别考了5分、3分、5分、2分和8分,哎,考得真是惨不忍睹(满分是10分)。接下来将分数进行从大到小排序,排序后是8 5 5 3 2。你有没有什么好方法编写一段程序,让计算机随机读入5个数然后将这5个数从大到小输出?请先想一想,至少想15分钟再往下看吧(*^__^*)。

    我们这里只需借助一个一维数组就可以解决这个问题。请确定你真的仔细想过再往下看哦。

    首先我们需要申请一个大小为11的数组int a[11]。OK,现在你已经有了11个变量,编号从a[0]~a[10]。刚开始的时候,我们将a[0]~a[10]都初始化为0,表示这些分数还都没有人得过。例如a[0]等于0就表示目前还没有人得过0分,同理a[1]等于0就表示目前还没有人得过1分……a[10]等于0就表示目前还没有人得过10分。

    下面开始处理每一个人的分数,第一个人的分数是5分,我们就将相对应的a[5]的值在原来的基础增加1,即将a[5]的值从0改为1,表示5分出现过了一次。

    第二个人的分数是3分,我们就把相对应的a[3]的值在原来的基础上增加1,即将a[3]的值从0改为1,表示3分出现过了一次。

    注意啦!第三个人的分数也是5分,所以a[5]的值需要在此基础上再增加1,即将a[5]的值从1改为2,表示5分出现过了两次。

    按照刚才的方法处理第四个和第五个人的分数。最终结果就是下面这个图啦。
     

    你发现没有,a[0]~a[10]中的数值其实就是0分到10分每个分数出现的次数。接下来,我们只需要将出现过的分数打印出来就可以了,出现几次就打印几次,具体如下。

    a[0]为0,表示“0”没有出现过,不打印。

    a[1]为0,表示“1”没有出现过,不打印。

    a[2]为1,表示“2”出现过1次,打印2。

    a[3]为1,表示“3”出现过1次,打印3。

    a[4]为0,表示“4”没有出现过,不打印。

    a[5]为2,表示“5”出现过2次,打印5 5。

    a[6]为0,表示“6”没有出现过,不打印。

    a[7]为0,表示“7”没有出现过,不打印。

    a[8]为1,表示“8”出现过1次,打印8。

    a[9]为0,表示“9”没有出现过,不打印。

    a[10]为0,表示“10”没有出现过,不打印。

    最终屏幕输出“2 3 5 5 8”,完整的代码如下。
     

    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;  

    守望者AIR技术交流社区(www.airmyth.com)
    回复

    使用道具 举报

  • TA的每日心情
    郁闷
    2016-8-19 16:08
  • 签到天数: 7 天

    [LV.3]偶尔看看II

    4

    主题

    31

    帖子

    2628

    积分

    少尉

    Rank: 6Rank: 6

    威望
    0
    贡献
    8
    金币
    320
    钢镚
    25
    发表于 2016-8-17 16:43:05 | 显示全部楼层
    学习了。。。。。
    我是一个兵
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    
    关闭

    站长推荐上一条 /4 下一条

    QQ|手机版|Archiver|网站地图|小黑屋|守望者 ( 京ICP备14061876号

    GMT+8, 2017-10-19 22:30 , Processed in 1.250000 second(s), 30 queries .

    守望者AIR

    守望者AIR技术交流社区

    本站成立于 2014年12月31日

    快速回复 返回顶部 返回列表