• 首页
  • 教育理念
  • 文章专题
  • 编程教程
    • – Scratch编程教程
    • – AppInventor编程
    • – Python编程教程
    • – NOIP信息学奥赛
    • – C/C++编程教程
    • – JS编程教程
  • 少儿编程学院
    • – 在线课程
    • – 学院名师
    • – 动态资讯
  • 少儿编程社区
    • – 在线编程
    • – 编程作品
    • – 专题创作
  • 更多
    • – APP客户端
    • – 关于我们
    • – 寻求合作
    • – 少儿编程联盟
投稿 登录 注册
  • 首页
  • 文章专题
  • 教育理念
  • 编程教程
  • 少儿编程学院
  • 微信公众号
  • APP客户端
少儿编程学院
少儿编程教育-微信公众号
首页 › 编程教程 › NOIP信息学奥赛 › 正文
NOIP信息学奥赛信息竞赛编程竞赛

【NOIP试题】桶排序(做题感悟)

主编主编 NOIP信息学奥赛 2017-07-29 8,379 31
【NOIP试题】桶排序(做题感悟)-少儿编程教育网

关于桶排序的文章,我几乎是没有见过。见过也看不懂,所以只好学会以后自己写一个了。

桶排序特点:

  1. 桶排序是稳定的
  2. 桶排序是常见排序里最快的一种,比快排还要快…大多数情况下
  3. 桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法

桶排序与其他排序的比较:

基数排序,与选择,冒泡,插入排序不同的是,前者都属于【比较性】排序,而基数排序是【分配式】排序,所以他又称”桶排“;

桶排,顾名思义,就是透过数据的部分资讯,将待排序的元素分配至某些【桶】中,从而达到排序的作用,他属于稳定性的排序。

下面举例子来讲吧:Codevs1487 大批整数排序

【题目描述】

CodeVS开发者有话说:

codevs自从换了评测机,新评测机的内存计算机制发生变化

计算内存的时候会包括栈空间 swap空间

这题的2M是单指内存空间。。。十分抱歉!

现在有一大批(总数不超过10000000个)1到10之间的整数,现在请你从小到大进行排序输出。

(测试数据将超过11MB。)

输入描述 Input Description

第一行表示将下排序的个数N;

第2行到最后一行,每行一个数,表示有待排序的数(均是1-10之间的数,含1和10)

(注:最后有一空行)

输出描述 Output Description

输出N个从小到大排列好的数,每行一个(注:最后有一空行)

样例输入 Sample Input

11
9
10
1
2
3
4
5
6
7
8
9

样例输出 Sample Output

1
2
3
4
5
6
7
8
9
9
10

分析:根据题目不难想起解题方法。肯定是排序之后又是什么排序。我最先想到的是STL的sort。之后试了一下。

第二个数据点没有过。之后我重新审了一下题目【现在有一大批(总数不超过10000000个)1到10之间的整数】很明显。SORT承受不了这么多组数。受不了受不了受不了,这日子没发过了啊。怎么办……

之后呢,聪明的古人发明了快速简洁的排序——桶排序(没找到发明人和日期。)

对此题目有了其他解法。(桶排序似乎出现早

#include <cstdio>

#include <iostream>

using namespace std;

int n,a[11],x;

int main()

{

   menset(a,0,sizeof(a));

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&x);

        a[x]++;

    }

    for(int i=1;i<=10;i++)

    if(a[i]!=0)

    {

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

        printf("%d\n",i);

    }

    return 0;

}

首先n为输出N个从小到大排列好的数。之后就进入了核心代码。【1到10之间的整数】这一个条件,就可以得到需要10个【桶】就OK。在学数组的时候学过,需要把数组开大一点。【桶】也要大一点。就开十一个。下面就考虑桶的表示。等等==刚刚说了什么数组?

嗯?数组=桶。

for(int i=1;i<=n;i++)

    {

        scanf("%d",&x);

        a[x]++;

    }

就将其分为11个桶(一个桶备用)。X为1~10的数。也为每输入一个数就判断在哪一个桶里并放入。桶内数量+1.这段代码应该不难理解。看下一段。

for(int i=1;i<=10;i++)

    if(a[i]!=0)

    {

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

        printf("%d\n",i);

    }

判断并输出。首先遍历10个桶。之后判断桶内数量是否为0.如果0下一个,如果不是0,是几就输出几。

好哒,桶排就这么简单,下次再见!

 

喜欢 (31)
打赏
  • 打赏支付宝扫一扫
  • 打赏微信扫一扫
微博 微信 QQ

微信扫一扫,分享到朋友圈

微信公众号
编程少年Scratch实物积木
少儿编程教育-微信公众号
上一篇

【NOIP试题】某科学的矩阵

下一篇

机器人编程比赛含金量到底有多少,值得我的孩子参加吗?

猜你喜欢

  • 第二届全国中学生网络安全竞赛即将在西安电子科大举办!

    第二届全国中学生网络安全竞赛即将在西安电子科大举办!

  • 严查违规竞赛,29项全国中小学生竞赛活动名单公布!

    严查违规竞赛,29项全国中小学生竞赛活动名单公布!

  • 教育部:2019年度中小学生全国性竞赛活动名单公示

    教育部:2019年度中小学生全国性竞赛活动名单公示

  • 第二十届全国中小学电脑制作活动通知

    第二十届全国中小学电脑制作活动通知

  • 2018年全国青少年创意编程大赛,终评活动即将开启!

    2018年全国青少年创意编程大赛,终评活动即将开启!

  • STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

    STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

主编
主编官方

我真的不是自黑!

中国STEAM教育2018年度风云榜

微信公众号

推荐专题

  • 有趣的少儿编程游戏推荐

    查看专题
  • 国外优秀的少儿编程教育

    查看专题
  • S科学-T技术-E工程-M数学

    查看专题

猜你喜欢

  • 广东粤教版教材Scratch少儿编程-第15课-听话的机器人
    2018-01-26

    广东粤教版教材Scratch少儿编程-第15课-听话的机器人

  • 亲身经历青少年AI人工智能技术等级考试!北京大学出题,工信部发证!

    亲身经历青少年AI人工智能技术等级考试!北京大学出题,工信部发证!

    2019-11-09
  • 中国STEAM教育专题报道:创新正在发生!

    中国STEAM教育专题报道:创新正在发生!

    2018-10-08
  • 过去的2017年不平凡,这10件事与你息息相关,你却不一定知道!

    过去的2017年不平凡,这10件事与你息息相关,你却不一定知道!

    2018-01-02
  • NOIP复赛复习(十七)尺取法与折半枚举

    NOIP复赛复习(十七)尺取法与折半枚举

    2017-10-18

热门文章

    暂无文章

热门标签

鲨鱼公园高考改革高考加分青橙创客青少儿防疫阿部和广错误观念逻辑思维费米科学贝尔科教谷歌教育计算机科学计算机思维解决方案西瓜创客

微信公众号

热门文章 热门标签 年度归档 少儿编程教育联盟

Copyright © 2021 少儿编程教育网 粤ICP备17057575号 · Designed by shaoerbc.org

大家都在搜

  • Scratch教程
  • scratch2下载
  • Scratch编程
  • 编程思维
  • 信息学奥赛
  • STEM教育
  • 编程一小时
  • 自主招生
  • 少儿编程竞赛

关注我们的公众号

微信公众号