1700494935
算法之美：指导工作与生活的算法 排序狂潮
1700494936
1700494937
排序是计算机的核心内容。事实上，从很多方面看，如果没有排序，计算机就不会变成现实。
1700494938
1700494939
19世纪末期，美国人口每10年就会增加30%。1870年，美国人口普查只有5个“调查科目”，到1880年，就增加到了200多个。1880年人口普查的制表工作花了8年，在1890年人口普查即将开始时才勉强完工。当时，有一位作家评论说：“调查人员整天埋头整理那些令人头皮发麻的统计数字，竟然没有失明，也没有发疯，这真是一大奇迹。”所有从事人口普查的工作人员都不堪重负，濒临崩溃。这个局面已经到了不得不改变的地步。
1700494940
1700494941
发明家赫尔曼·霍尔瑞斯从当时使用的打孔火车票那里找到灵感，发明了一种可以存储信息的打孔统计卡和一种机器，用来完成计数与排序工作。他把这套系统称作“霍尔瑞斯计算机”。1889年，霍尔瑞斯获得专利，美国政府在1890年的人口普查中采用了霍尔瑞斯计算机。在这之前，从来没有人看到过这样的机器。一位惊叹不已的旁观者说：“这个装置就像众神的磨坊一样准确无误，速度则完胜对方。”然而，另一个人认为这项发明的用途十分有限：“除了政府以外，没有人愿意使用它，因此发明者不可能发财。”霍尔瑞斯把这个预言制成剪报并保存了下来，但是事实证明，这个预言并不完全正确。1911年，霍尔瑞斯公司与另外几家公司合并，变成了计算-制表-记录公司。几年之后，公司改名为国际商用机器公司，即IBM。
1700494942
1700494943
从计算机诞生直到进入20世纪，排序一直是推动计算机发展的一大动力。为“存储程序”计算机编写的第一个代码是一个高效排序程序。事实上，正是因为计算机的能力超越了IBM的专用卡片分类机，所以美国政府相信它们在通用机器上投入巨额资金的决定是正确的。到20世纪60年代，一项研究估计，世界上超过1/4的计算资源被用于排序。难怪排序对于处理几乎任何类型的信息来说都是至关重要的。无论是查找最大值或最小值，最常见数据或最罕见数据，还是清点、索引、标记副本，或者根据你的要求进行查找，其核心工作通常都是排序。
1700494944
1700494945
但是，排序不仅用于这些方面。毕竟，排序的主要原因之一是将内容变成方便人眼观察的形式，这意味着排序也是人类信息体验的关键。排序列表无处不在。就像鱼儿问“水是什么”一样，我们只有有意识地去感知，才会发现排序无处不在。
1700494946
1700494947
即使电子邮件收件箱有数千封邮件，它也通常会根据收件时间显示排在前面的50封。利用点评网站Yelp寻找餐厅时，它也会将成百上千家餐厅根据邻近程度与用户评分排序，然后为你显示前十几名。博客按日期对博文进行排序，显示一个不是很长的博文清单。脸书的动态信息、推特的信息流和红迪网的主页都是根据某些属性对内容进行排序，然后以列表的形式显示出来。我们把谷歌和必应等网站称作“搜索引擎”，但是这个称呼并不是非常恰当，因为它们其实都是排序引擎。作为接收全球信息的一种手段，谷歌占有非常明显的优势，究其原因，与其说是它可以在成千上万的网页中找到我们需要的文本（20世纪90年代，谷歌的竞争对手同样可以出色地完成这个任务），不如说是因为谷歌可以将这些网页进行有效地排序，然后只把关系最密切的前10个网页显示出来。
1700494948
1700494949
从很多方面看，在庞大排序表的顶部截取一部分，就可以当作通用的用户界面。
1700494950
1700494951
计算机科学可以帮助我们了解所有上述情况的深层次内容。当我们被账单、文件、书本、袜子等团团包围，希望厘出头绪（这种情况每天都会发生，而且比我们想象的还要多）时，这些知识又可以转化为一种深刻认识，帮助我们解决难题。通过量化混乱状况的缺点（和优点），计算机科学还告诉我们，在一些情况下，我们其实根本不应该排出次序。
1700494952
1700494953
此外，当我们开始看排序结果时，我们知道被排序的不仅是信息——被我们排序的其实是人！建立先后次序的计算机科学最适合大展身手的舞台可能是运动场和拳击场，因此，学会排序有助于理解人类可以和谐相处、偶尔才会拳脚相向的原因。也就是说，排序可以为我们提供一些令人吃惊的线索，帮助我们了解社会的本质。所谓社会，就是我们维持的另外一种更重要、规模更大的秩序。
1700494954
1700494955
1700494956
1700494957
1700494959
算法之美：指导工作与生活的算法 排序带来的苦恼
1700494960
1700494961
1955年，詹姆斯·霍斯肯在第一篇公开发表的关于排序的科学论文中写道：“为了降低单位产出的成本，人们通常会增加他们的业务规模。”这是任何一名商科学生都很熟悉的规模经济。但是，在排序这个问题中，规模往往会招致灾难：如果扩大排序的规模，“排序的单位成本就会不降反升”。排序往往呈现非常明显的规模不经济现象，这与普通人认为大批量处理问题有诸多好处的直觉正好相反。一般来说，做两个人的饭并不比做一个人的饭难，肯定比为一个人做两次饭要容易得多。但是，整理好装有100本书的书架，比整理两个各有50本书的书架更费时：因为你需要整理的东西是后者的两倍，而且每件东西可以放置的位置也是后者的两倍。需要整理的东西越多，难度就越大。
1700494962
1700494963
这是排序理论的第一个，也是最基本的深刻见解：规模越大，难度越大。
1700494964
1700494965
由此我们可以推断，在排序的过程中，最大限度地减少痛苦的办法就是在排序时尽可能减少排序对象的数量。的确，降低袜子排序计算难度的一个最有效的预防措施就是勤洗衣服。如果洗衣服的频率增加到原来的3倍，排序时的难度就会变为原先的1/9。如果希利斯的室友继续采用他的那套独特程序，那么把洗衣服的间隔时间从14天改为13天，为袜子配对时从洗衣篮中拿袜子的总次数就可以减少28次。（间隔时间增加1天，拿袜子的次数就会增加30次。）
1700494966
1700494967
即使在14天这样一个不大不小的时间范围内，我们也可以看到排序的规模已经开始变得难以处理。然而，计算机通常需要一口气为数百万个项目排序。面对这种情况，我们可以借用电影《大白鲨》的一句台词：我们需要一艘更大的船以及更好的算法。
1700494968
1700494969
但是，要回答如何排序、哪种排序方法效果最佳这个问题，就需要先弄明白另外一个问题：如何计分。
1700494970
1700494971
1700494972
1700494973
1700494975
算法之美：指导工作与生活的算法 大O符号：衡量最坏情况的标准
1700494976
1700494977
根据《吉尼斯世界纪录大全》，为一副扑克牌整理次序的最快记录是捷克魔术师兹德涅克·布拉德克保持的。2008年5月15日，布拉德克仅用时36.16秒就把52张扑克牌排好了先后次序。[1]他是怎么做到的？是什么排序技术让他获得这项殊荣的？答案可能与一些有趣的排序理论有关，但是布拉德克拒绝置评。
1700494978
1700494979
对于布拉德克的灵巧与技能，我们只能表示尊敬，但是我们百分之百地确定我们自己也可以打破他的纪录。事实上，我们非常确定，只要向这项殊荣发起80658175170943878571660636856403766975289505440883277824000000000000次挑战，就一定可以创造一个无法打破的纪录。这个数字比10的66次方的80倍略大一点儿，是52的阶乘，数学上记作“52！”——包含52张牌的一副扑克牌可以排出这么多不同的次序。在经过大约这么多次的尝试之后，我们迟早可以为经过洗牌变得杂乱无序的扑克牌快速排序，然后，我们可以自豪地让克里斯汀·格里菲斯这个名字载入《吉尼斯世界纪录大全》，然后在旁边标明一个不太难看的排序时间——0分00秒。
1700494980
1700494981
公正地说，在宇宙进入热寂状态之前，我们可能都需要不停地尝试，才有可能创造出这个完美的纪录。尽管如此，我们从中可以清楚地看到纪录保持者和计算机科学家之间最大、最根本的区别。吉尼斯纪录的工作人员只关心最好的成绩（和娱乐性）。当然，他们的行为也无可厚非，因为所有的体育纪录也都只能反映出最佳表现。然而，计算机科学几乎从不关心最好的情况。相反，计算机科学家可能想知道像布拉德克等人的平均排序时间：让他对所有8×1066副扑克牌或者合理大小的样本进行排序，然后记录平均速度。（这下你知道他们为什么不会让计算机科学家来做这些事情了吧？）
1700494982
1700494983
不仅如此，计算机科学家还希望知道最慢的排序速度。分析最糟糕的情况，可以让我们放心地做出硬性保证——确保关键程序可以及时完成，确保不会超出最后期限。因此，在本章剩余部分（事实上，是全书的剩余部分）里，除非另有说明，否则我们讨论的都是算法的最差表现。
[
上一页 ]
[ :1.700494934e+09 ]
[
下一页 ]