1700495053
算法之美：指导工作与生活的算法 [:1700494128]
1700495054
算法之美：指导工作与生活的算法 超越比较法：比对数更好的算法
1700495055
1700495056
在华盛顿州普雷斯顿镇附近有一个不起眼的工业公园，园内有许多不起眼的灰色入口，2011年和2013年美国国家图书馆分类排序冠军就“藏身”于其中一个入口的后面。一条长长的分段传送带以每分钟167本（每天85000本）的速度，运送图书从条形码扫描器前通过。随后，这些图书自动分流，进入投送舱门，被投送到96只不同的箱子中。
1700495057
1700495058
1700495059
1700495060
1700495061
合并排序示意图
1700495062
1700495063
注：书架上有次序混乱的8本书。首先，把相邻两本书配成一对并排序，再通过比较将两对书合并成一组，而且这4本书的先后次序都是正确的。随后，通过比较将两组书全部按照正确次序放到书架上。
1700495064
1700495065
普雷斯顿分类排序中心是世界上规模最大、效率最高的图书分类排序设施之一，主管单位是金县图书馆系统。金县图书馆与纽约公共图书馆的设施大致相仿，它们一直是竞争关系。由于势均力敌，4年来两个图书馆在竞争中打成平手。在2014年的最后决战打响之前，纽约图书馆图书运营服务部副主管萨尔瓦多·马加蒂诺说：“金县图书馆今年要打败我们？想都别想！”
1700495066
1700495067
理论家也可以在普雷斯顿分类排序中心发现一些值得关注的东西，因为这套系统为图书排序所用的时间是O（n），即线性时间。
1700495068
1700495069
从某种非常重要的意义上看，合并排序算法给出的O（nlogn）线性对数时间肯定是我们可以得到的最佳效果。已经有人证明，如果通过一系列面对面直接比较的方法对n个事物进行完全排序，比较的次数不可能少于O（nlogn）。这是一条普世法则，是不可能违背的。
1700495070
1700495071
但是，严格说来，这条法则并不能平息排序问题上的所有争议。有的时候我们并不需要完全排序，有的时候根本不需要逐项比较也能完成排序工作。正是因为有这两个原因，实践中的粗略排序速度也可以比线性对数时间快。桶排序算法非常漂亮地展现了这个特点，而普雷斯顿分类排序中心就是桶排序的一个完美实例。
1700495072
1700495073
在桶排序中，排序对象按照排序类别分成若干组，类别之间更精细的排序问题会被留到后面解决，在分组时不予考虑。（在计算机科学中，“桶”这个术语仅表示一组未排序的数据，但是，金县图书馆系统等现实世界中最有影响力的桶排序用户则把这个表达按照字面含义来理解。）对于这一步骤，有人提出反对意见：如果你希望将n个对象分装到m个桶中，分组工作需要的时间是O（mn），也就是说，时间一定与对象数量和桶数量的乘积成比例关系。但是，只要桶的数量与排序对象的数量相比显得比较小，大O符号就认为这个时间约等于O（n），即线性时间。
1700495074
1700495075
真正打破线性对数壁垒的关键，是了解排序对象的分布情况。如果桶选得不合适，排序的效果就不会太好。例如，如果所有的书都被投放到同一个箱子里，排序工作就没有任何进展。但是，如果桶选得非常合适，所有项目都被分到大小差不多的组里，就表明已经朝着完全有序前进了一大步（鉴于排序工作在本质上遵循“规模越大，难度越大”这条准则）。普雷斯顿分类排序中心的任务是按照目的地，而不是字母顺序，进行排序，因此在选桶的时候考虑的是流通统计数据。有的分支流通量比较大，因此他们就分配给这些分支两只箱子，有时甚至是三只箱子。
1700495076
1700495077
人在完成排序工作时，如果对排序对象有类似的了解，也会对他们有利。为了现场观看专家的排序工作，我们前往加州大学伯克利分校的主图书馆和墨菲特图书馆，进行了一次实地考察。这些图书馆的书架长度加起来至少有52英里，所有的书都靠人工整理。归还到图书馆的书首先被放到后台，然后根据美国国会图书馆藏书书目，重新放回到不同的书架上。例如，一组书架上放有一堆最近归还的书籍，藏书书目都在PS3000到PS9999之间。然后，学生助手将这些图书装到小车上，每车装150本，所有的书都以适当的顺序放置，以方便他们放回到图书馆的书架上。学生们都接受过一些基本的排序训练，但是一段时间之后，他们都会找到一些适合自己的办法。积累了一定经验之后，他们可以在不到40秒的时间里，就把小车上150本书全部排好次序。这些经验的主要作用是让他们预先知道这些书有哪些特点。
1700495078
1700495079
伯克利分校化学专业的学生乔丹·何是一位图书分类排序高手。他一边整理着PS3000-PS9999书架上的一大堆图书，一边告诉我们：
1700495080
1700495081
据我的经验，书目号在3500至3600之间的书很多，因此我首先找3500以下的书，先粗排，再细排。等3500以下的书都排好之后，我知道3500以上的书（也就是3500至3599这些书）是个大头，所以我想把这些书单独排好序。如果这些书的数量太多，我可能会进一步细分，分成3510-3519、3520-3529、3530-3539等。
1700495082
1700495083
乔丹总是把25本左右的书编成一组，全部排好序之后，装到小车上。排序的时候，他使用的确实是插入排序法。他精心想出来的办法是一种桶排序法。他事先就知道各种书目号对应的图书数量，因此他清楚应该如何选桶。结果，这个办法取得了非常好的效果。
1700495084
1700495085
1700495086
1700495087
1700495088
算法之美：指导工作与生活的算法 [:1700494129]
1700495089
算法之美：指导工作与生活的算法 排序是搜索的准备工作
1700495090
1700495091
掌握了这些排序算法，你下一次整理书架时就应该能派上用场。同奥巴马一样，你也会知道不能使用冒泡排序法。好的办法（得到图书馆工作人员和机器的共同认证）是使用桶排序，等到将排序对象分成足够小的组之后，再使用插入排序，或者干脆举办比萨派对，使用合并排序。
1700495092
1700495093
但是，如果你邀请计算机科学家帮助你完成这项工作，他们询问的第一个问题应该是：你到底为什么要整理这些图书？
1700495094
1700495095
老师经常告诉那些本科生，计算机科学研究的就是如何取舍的问题。在前面讲到观察与行动以及探索与利用之间的矛盾时，就已经讨论过这个观点。而排序与搜索之间的取舍是最重要的取舍问题之一，其基本原理是：人们投入精力为物品排序是一种先发制人的措施，目的是保证以后无须在搜索上投入精力。平衡点应该如何确定，取决于当时情况的具体参数，但是，如果认为排序的价值仅仅是为未来的搜索提供支持，那么你会有一个令人吃惊的发现：
1700495096
1700495097
混乱无序也无伤大雅！
1700495098
1700495099
如果你从来不在某些物品中搜索某个目标，那么为这些物品排序就纯粹是一种浪费。如果你从来不为某些物品排序，那么你在其中搜索的效率就会很低。
1700495100
1700495101
因此，摆在我们面前的问题已经变成如何提前预估未来的用途。
1700495102