最简单的排序算法

来源 :中国信息技术教育 | 被引量 : 0次 | 上传用户:xgz521521
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  在一次电视节目上,谷歌总裁施密特提出问题:“如何才能更有效地对一百万个32位长整数进行排序?”同在现场的奥巴马立刻响应道:“肯定不能用冒泡排序法。”施密特评价说:“天哪!他是从谁那里听说这个的。”
  冒泡排序很简单,其原理也比较容易理解,但冒泡排序效率很差。世上也存在着许多效率很高的排序算法,但它们又都比较难理解。本文将介绍一种简单又“高效”的排序算法——珠排序,大家不妨一起来玩玩。
  空间站里玩排序
  之所以要在“高效”两个字上打引号,是因为珠排序需要特殊的硬件支持。怎么个特殊法呢?为了方便说明问题,请想象在某个失重的空间站里,有一系列排列整齐、从1到n依次编了号码的透明管子,在管子里放入小球,小球的直径与管子横截面的直径相仿,只是略小一点,放球的规则如下:
  ①预先设定一系列未排序的数字,如5、4、8、1、2、3、6、4。
  ②按预先设定的数字往管子里放球,如果是5,就放5个球,但并不是把5个球都放到1个管子中,而是依次放入1号到5号管子。如果是4,就把4个球依次放入1号到4号管子(如图1A、B)。
  ③在空间站的无引力真空环境中,所有球都浮在空中,这时候若忽然施加重力,如用离心力模拟重力,于是所有的球都掉到了管子的底部,这时如果从侧面数球的个数,就能发现,先前的未排序数字,此时已经排序完成了(如图1C、D)。
  这个实验当然不一定非要在太空站里做,把原本水平放置的管子竖立起来,产生的效果也是一样的。
  记事本里玩排序
  即便没有管子和小球,也可以在记事本中模拟珠排序的过程。
  假设预设的未排序的数字为5、4、8、1、2、3、6、4,第一个数字是5,则在记事本的第一列(注意是列而不是行)写5个“1”,然后再在“1”下面多补充一些“0”,因为需要排列的数字最大是8,用8减去5得3,则最少补充3个“0”,当然多补充点“0”是没关系的,接着要排序的数字是4,则在记事本第二列寫4个“1”,再补充4个“0”,第三列8个“1”……以此类推(如图2)。
  把所有的1和0按次序排列好后,用记事本中的“编辑—替换”功能,将文本中的“10”全部替换成“01”,反复这个全部替换过程,当不再有可替换的对象时,排序也就完成了(如图3)。就这样,不用写一行代码就完成了排序。当然,若想要一本正经地把珠排序的代码写出来,也不是特别困难的事情,这个任务就交给有兴趣的朋友自行探索了。
  反复点“全部替换”按钮,最后替换就完成了,每一列的“1”的个数是1、2、3、4、4、5、6、8,正是5、4、8、1、2、3、6、4排序后的结果(如图4)。
其他文献
战略联盟是企业一种新的组织形式,根据企业综合优势理论,运用实证分析的方法,针对联盟对企业核心能力的影响分析,为企业如何保护核心能力,通过战略联盟来提升和创造核心能力
随着“微时代”的来临,近年来微课这一概念开始在中小学教学中悄然兴起。而微视频是微课的核心组成部分,微视频具有时间短、内容精、灵活性强的特点,可以碎化知识,直击重点、难点,具有较强的针对性。运用微视频可以更好地实现分层教学,培养学生的自主探究意识和创新精神,还能减少教师的重复劳动,从而提高信息技术课堂的教学效率。笔者在从事信息技术教学工作中发现,由于初中生的认知特点以及信息技术课独特的教学环境和方式
通过对多天线分集接收技术的分析,针对多径传输引起的衰落,提出一种多天线分集接收方法。本文将智能控制处理技术与空间分集接收天线技术相结合,通过智能控制选择合并算法。
探讨了校园网络安全的范畴.针对校园网络安全的隐患,从管理和技术两个方面对高校校园网络的安全体系做了论述,提出了校园网络安全体系架构,指出在管理上通过机构和制度来保证
会提醒你喝水的杯子Cuptime  不知道你是否留意,不知不觉在市场上出现了非常多的智能小物件。有智能路由器、智能灯泡、智能插座,等等。智能设备虽然层出不穷,但是真正让人眼晴一亮的并不多见。Cuptime智能水杯,非常巧妙地从健康的角度出发,并非常好地找准了我们日常忽视的细节,一个可以提醒你要记得喝水的杯子。  据说,当你感到口渴想要喝水的时候,体内的失水已经达到2%,口渴本身其实是体内已经严重缺
随着我国加入WTO和世界经济一体化的发展,我国的钢铁产业面临着严峻的挑战.目前,国有钢铁企业由于受传统计划经济的影响,在科技人员管理方面还存在一定的问题,突出地表现在对
应用负载均衡技术在应用交付方面具有良好的可用性和安全性。本文详细讲解了应用负载均衡技术的原理及实现算法,并就下一步新型应用负载均衡技术的发展方向进行了展望。
科学技术是第一生产力,而科技创新又是关键要素,是社会可持续发展的主导力量,是社会物质生产的直接推动力;科技创新不但为人类生存提供保证,还可以开辟新产业,是新世纪国际科
c语言是一门优秀的语言,其在多个领域都有着很好的应用。指针是c语言的精华所在。本文阐述了指针的概念,对指针的常见类型进行了分析,并对指针的运算和相关应用做了详细的实例讲
为了解决目前电信运营商在数据流量业务方面基于DCC协议的在线计费接口测试存在的工作量大、测试用例复杂易出错、测试重复性强等问题,本文提出了一种在线计费接口消息自动化测试系统。该系统将接口抓取的文件基于CAP等协议分割,同时自动筛选出全面的消息类型、并利用测试与工具开发解耦的自动化测试执行模块,实现了测试执行过程的全自动化,同时满足了测试效率、测试准确性和测试全面性要求,在生产运营中具有很强的可用性