啊哈!算法[试读]

第1节　最快最简单的排序——桶排序 在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序，考试的名次需要按照分数排序，网上购物的时候会按照价格排序，电子邮箱中的邮件按照时间排序……总之很多东东都需要排序，可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。 首先... 查看全部[ 第1节　最快最简单的排序——桶排序 ]

简化版的桶排序不仅仅有上一节所遗留的问题，更要命的是：它非常浪费空间！例如需要排序数的范围是0~2100000000，那你则需要申请2100000001个变量，也就是说要写成int a[2100000001]。因为我们需要用2100000001个“桶”来存储0~2100000000每一个数出现的次数... 查看全部[ 第2节　邻居好说话——冒泡排序 ]

上一节的冒泡排序可以说是我们学习的第一个真正的排序算法，并且解决了桶排序浪费空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了O(N2)。假如我们的计算机每秒钟可以运行10亿次，那么对1亿个数进行排序，桶排序只需要0.1秒，而冒泡排序则需要1千万秒，达到115天之久，是不是很吓人？那... 查看全部[ 第3节　最常用的排序——快速排序 ]

排序算法还有很多，例如我在《啊哈C！思考快你一步》一书中讲过的选择排序，另外还有计数排序、基数排序、插入排序、归并排序和堆排序等等。堆排序是基于二叉树的排序，我会在后面的章节讲到。现在来看一个具体的例子“小哼买书”（根据全国青少年信息学奥林匹克联赛NOIP2006普及组第一题改编），来实践一下本章所... 查看全部[ 第4节　小哼买书 ]