1700495025
算法之美：指导工作与生活的算法 [:1700494127]
1700495026
算法之美：指导工作与生活的算法 打破平方时间的魔咒：分治算法
1700495027
1700495028
看到两个完全合理的方法都会导致平方时间之后，我们不禁要问：真的有更快的排序方法吗？
1700495029
1700495030
这个问题听起来像是一个关于生产力的问题。但是，与计算机科学家讨论这个问题，就会发现它更接近于空谈，类似于思考光速，时光之旅，超导体，或者热力学中的熵。宇宙的基本规则和极限是什么？哪些是可能的？哪些是允许的？计算机科学家就像粒子物理学家和宇宙学家一样，通过这种方式一点一滴地窥探上帝的蓝图。整理出秩序，至少需要付出多少努力？
1700495031
1700495032
我们能否找到一种常数时间，也就是O（1）算法，无论规模大小，耗费的时间都不会有任何变化（就像在客人蜂拥而至之前打扫房间一样）？即使证实书架上的n本书已经排好序，也不可能在常数时间里完成，因为我们需要检查所有书的位置。因此，用常数时间完成图书分类排序工作其实是根本不可能的。
1700495033
1700495034
线性时间O（n）呢？可不可以像在餐桌上传递一道菜那样高效，排序对象增加一倍，工作量也仅仅增加一倍？想一想上面的那些例子，就会发现很难有这样的方法。在各种情况下，n2都与你需要移动n本书这个事实有关，而且每次将书移动位置所需的工作量与n也成某种比例关系。怎么可以把大小为n、次数也为n的工作变得只剩下一个n？在冒泡排序中，运行时间O（n2）是因为我们需要逐本移动n本书的位置，而且每次移动时需要跨越n个位置。在插入排序中，之所以是平方时间，是因为我们需要逐本处理n本书，而且在插入之前还要将每本书与n本书进行比较。线性时间排序意味着每本书都需要常数时间，无须考虑有多少本书需要排位的问题。这好像也是不可能做到的。
1700495035
1700495036
因此，我们知道我们至少可以在平方时间里完成任务，但是可能无法在线性时间里把所有书都排好序。我们的极限或许就在线性时间与平方时间之间的某个位置。在线性与平方之间，即n与n×n之间，是否可以找到合适的算法呢？
1700495037
1700495038
答案是肯定的，而且这些算法近在眼前。
1700495039
1700495040
前面说过，信息处理开始于19世纪的美国人口普查，是由赫尔曼·霍尔瑞斯及后来的IBM公司根据实体打孔卡排序设备开创形成的。1936年，IBM开始生产一系列名为“比较者”的机器，它可以将分别排序的两叠扑克牌合并到一起。只要两叠牌本身是排好序的，就可以在线性时间内，非常轻松地将它们合并到一起，并且排好序。该程序非常简单，首先把两叠牌最上面的那两张相互比较，将较小的那张放在新的那叠牌中。重复这个步骤，直到把所有牌都放好。
1700495041
1700495042
1945年，约翰·冯·诺伊曼为了展示存储程序计算机的威力，编写了一个程序。在这个程序的最终结论中，就包含有比较的概念。为两张牌排序很简单，把较小的那张牌放在上面就可以了。如果有两叠牌，每叠包含两张排好序的牌，我们可以很容易地将这四张牌整理成排好序的一叠牌。重复几次，就可以整理出越来越多且排好序的牌垛。很快，你就可以把完整的一副牌整理得井然有序。在最后一次合并时，你可以通过与交错式洗牌非常相似的手法，将扑克牌整理出你需要的次序。
1700495043
1700495044
这种方法现在被称作“合并排序”，是计算机科学中的传奇算法之一。正如1997年的一篇论文所指出的：“合并排序在排序历史中的重要地位与排序在计算历史中的重要地位旗鼓相当。”
1700495045
1700495046
合并排序威力巨大，是因为它的复杂程度位于线性时间和平方时间之间。具体来说，O（nlogn）被称为“线性对数”时间。每一次操作都会把有序牌叠的规模增加一倍，所以要对n张牌完全排序，你需要的操作次数就等于2通过自乘变成n时所需的次数，换句话说，就是以2为底的对数。你可以通过两次比较操作，为4张牌排序；第三次操作之后，排好序的牌就会有8张；第四次操作，16张。合并排序的分治法问世之后，人们很快受到启发，提出了一系列其他线性对数排序算法。把线性对数复杂程度说成对平方复杂程度的一个改进，远不足以体现出两者之间的差距。如果需要排序的项目数量与人口普查差不多，那么两者的差距就相当于对数据集进行29次操作和3亿次操作之间的差别。各行业在解决大规模排序问题时都青睐这种方法，原因就不难理解了。
1700495047
1700495048
在家庭内部处理小规模排序问题时，合并排序也能找到合适的舞台。它之所以应用广泛，原因之一是它非常适合并行处理。如果你还在苦苦思索对付那个书架的办法，合并排序策略就会建议你订一个比萨，然后邀请几个朋友来分享。把书平均分配，并让每个人负责整理其中一堆。接着，让朋友们两两配对，把他们负责的书合并到一起。重复这个过程，直到最后剩下两堆书，再一次性地合并到书架上。需要注意的是，不要让比萨弄脏了那些书。
1700495049
1700495050
1700495051
1700495052
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