啊哈!算法[试读]
第1节 最快最简单的排序——桶排序
第1节 最快最简单的排序——桶排序 在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总之很多东东都需要排序,可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。 首先出场的是我们的主人公小哼,上面这个可爱的娃就是啦。期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有5个同学,这5个同学分别考了5分、3分、5分、2分和8分,哎,考得真是惨不忍睹(满分是10分)。接下来将分数进行从大到小排序,排序后是8 5 5 3 2。你有没有什么好方法编写一段程序,... 查看全部[ 第1节 最快最简单的排序——桶排序 ]
第2节 邻居好说话——冒泡排序
简化版的桶排序不仅仅有上一节所遗留的问题,更要命的是:它非常浪费空间!例如需要排序数的范围是0~2100000000,那你则需要申请2100000001个变量,也就是说要写成int a[2100000001]。因为我们需要用2100000001个“桶”来存储0~2100000000每一个数出现的次数。即便只给你5个数进行排序(例如这5个数是1、1912345678、2100000000、18000000和912345678),你也仍然需要2100000001个“桶”,这真是太浪费空间了!还有,如果现在需要排序的不再是整数而是一些小数,比如将5.56789、2.12、1.1、3.123、4.12... 查看全部[ 第2节 邻居好说话——冒泡排序 ]
第3节 最常用的排序——快速排序
上一节的冒泡排序可以说是我们学习的第一个真正的排序算法,并且解决了桶排序浪费空间的问题,但在算法的执行效率上却牺牲了很多,它的时间复杂度达到了O(N2)。假如我们的计算机每秒钟可以运行10亿次,那么对1亿个数进行排序,桶排序只需要0.1秒,而冒泡排序则需要1千万秒,达到115天之久,是不是很吓人?那有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢? 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,这就是一个用来参照的数,待会儿你就知道... 查看全部[ 第3节 最常用的排序——快速排序 ]
第4节 小哼买书
排序算法还有很多,例如我在《啊哈C!思考快你一步》一书中讲过的选择排序,另外还有计数排序、基数排序、插入排序、归并排序和堆排序等等。堆排序是基于二叉树的排序,我会在后面的章节讲到。现在来看一个具体的例子“小哼买书”(根据全国青少年信息学奥林匹克联赛NOIP2006普及组第一题改编),来实践一下本章所学的三种排序算法。 小哼的学校要建立一个图书角,老师派小哼去找一些同学做调查,看看同学们都喜欢读哪些书。小哼让每个同学写出一个自己最想读的书的ISBN号(你知道吗?每本书都有唯一的ISBN号,不信的话你去找本书翻到背面看看)。当然有一些好书会有很多同学都喜欢,这样就会收集到很多重复的ISBN号... 查看全部[ 第4节 小哼买书 ]