现在的位置: 首页 > 综合 > 正文

最快最简单的排序——(桶排序)

2014年10月31日 ⁄ 综合 ⁄ 共 1288字 ⁄ 字号 评论关闭

如果想看此类更多的请点击:http://ahalei.blog.51cto.com/4767671/1362789


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


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


  首先我们需要申请一个大小为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分。


113320lz09fp0o7ff7h8xf.png


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

113321w4iew2smzki8kmec.png


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

113321rmecknx06n92ppu7.png


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

113321a4euiehmeehcgpeb.png


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

113321k7vs6474q39bo517.png


  你发现没有,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”

     输入数据为
5 3 5 2 8 

代码如下:

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int a[11]={0},i,j,t=0;
    for(i=1;i<=5;i++)
    {
       cin>>t;
        a[t]++;
    }
    for(i=0;i<=10;i++)
    {
        for(j=1;j<=a[i];j++)
        {
           cout<<i<<" ";
        }
    }
    getchar();
    return 0;
}

抱歉!评论已关闭.