《生活中的算法 (Algorithms to live by)》第三章：排序
根据热力学第二定理，宇宙作为一个孤立系统，熵会随着时间流逝而增加，由有序走向无序，最终，整个宇宙将会走向寂灭。然而上帝在关上一扇门之后还会关上一扇窗，于是创造了处女座来对抗这走向无序的宇宙...
多年以后，已是著名发明家兼企业主的Danny Hillis，还会想起四十年前那个湿热漫长的夏日午后...
炎热的午后，Danny 醒来有睡去，睡去又醒来，然而视线里室友那不断从洗衣篮抽出袜子的忙碌身影，却自始至终存在着。他左手拿一只袜子，右手从洗衣篮一堆袜子中抽出另一只袜子，如一个严谨的科学家进行精确比照，如果吻合便严肃地点点头，小心翼翼地将两只袜子放在一起叠好；如果不是，便将袜子扔回洗衣篮，开始下一轮抽取...
Danny看不下去了，愤然而起：“处女座就忍了，但这么笨的处女座我就不能忍了，都不去好好读读安迪的写作间！” 摔门而出。
要求换房间。此刻，作为计算机科学家萌芽的Danny已隐隐察觉，这里还有更好的方法来整理那些袜子，那，就是排序算法。但是，此时的少年还不知道...
不扯了，这篇讲排序算法。当然排序算法不光是用来整理臭袜子，用处可大了，甚至可以说是排序促成了计算机的诞生。
排序的盛宴
19世纪末，美国人口大量增长，导致人口普查整理表格时需要花费大量时间。那时可没有Excel这么方便的排序功能，都得靠人力。
所幸Herman Hollerith发明了Hollerith机和配套的打孔卡系统，将搜集来的数据自动排序，不再要人辛辛苦苦整理了。当时的一些人看了说，这也就只能用于这样的政府事务。然而，若干年后Hollerith的排序机公司却成了今日的蓝色巨人--IBM。
此后，排序就不断刺激着计算机的发展，比如第一段计算机上的代码就是用于有效排序的。接下来，因为计算机比卡片机更高效排序的可能，说服了政府投入大量资金用于研发计算机。到19世纪60年代，世界上几乎四分之一的算力都是用于排序。
而如今，排序更是无处不在。微信上按时间排序的最新信息，淘宝上按热度排序的商品们，还有百度上按相关度排序的链接——搜索引擎其实就是“排序引擎”，不过是对大量爬取的网页排序，然后展现给你。
不光是计算机相关，在生活的其他角落排序也无处不在，各种竞赛，考试排名，甚至可能是整个人类社会。
排序之痛
规模效应或许是现代工业社会最大的一项创举，随着规模增大边际成本降低，于是就能够享受到各种廉价优质的商品与服务。然而当遇到排序时，规模效应却泄了气，不再起作用了。
这便是排序理论里最大的痛点，规模越大越难排序。
因此排序时，需要尽量避免过多对象。
但现实却是残酷的，很多问题并不是只有十几双袜子这么简单，特别是对于计算机科学家们来说，需处理的量级都非常庞大。如前面提到的搜索引擎需要处理的链接可能就是上亿。
于是我们需要一个标尺来度量在这样大量级下算法的性能。
Big-O 表示法
偷懒的计算机科学家们从数学里借来了Big-O表示法，O 表示 order of function (函数的阶)，而计算机科学里习惯称计算复杂度。
有意思的是，当计算机科学家用它来测量算法时，却不是测量算法最好的情况，而是最差的情况。因为只有最差的情况才能够真正比较出两个算法的本质不同。
比如说，排列一组打乱的牌。如果用随机52张牌的方式来排序的话，运气好的话，一次就搞定；而用后面提到的合并排序，可能最好情况也得几十次操作。乍一看好像随机排序还要好些，但是我们都知道并不是的。
再来看看最差情况，再用随机排序的话，就需要80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000次。而合并排序算法呢，大概两百来次，一下就看出了差距。
通过比较最坏情况就能看清不同算法的根本差距。之后根据最差情况的不同就可以对算法进行分类了。
首先是O(1)，也叫“常数复杂度”。比如说举办一个接待n个客人的宴会，得先打扫房间，那么无论多少人来，打扫的时间都是固定的。这里1只是习惯表示，表示计算时间与n无关。
再来是O(n)，线性复杂度。比如说宴会上一人一道菜，那准备菜的时间便会随人数n线性增长。如果此时你天真地问，到目前所需准备时间是不是O(n+1)啊，计算机科学家会不客气地将键盘拍你脸上，不是。
因为Big-O表示法是看大头不看小头，忽略细节。这是因为n非常大时，往往低级别的计算复杂度可以直接忽略。还有n前的常数项都要省去，比如2n和n的Big-O表示法都是O(n)。
之后便是O(n^2 )，又叫“平方复杂度”。同样宴会的例子，你和n个客人，总共n+1个人之间进行相互拥抱，那就需要抱n(n-1)/2次，取忽略低级便是平方复杂度O(n^2)了。
最后，还有指数复杂度O(2^n)，一种比较坏的情况，没增加一个对象花费翻倍。
平方级：冒泡算法和插入算法
下面来按照上面说的Big-O给排序算法分类吧。先是两种经典算法，冒泡排序和插入排序。有多经典呢，几乎是学习算法时必须学的算法，连奥巴马都知道。
然而，计算机科学与文学不同的是，经典往往意味着基本都不用了，就像神经网络里“经典”的Sigmoid激活函数。
这里用小学生按高矮顺序排队的例子来说明这两个算法。先假设一队高矮不一的小朋友杂乱地站成一列。
冒泡排序，就是从第一个小朋友开始，和后面的一位比，如果比他高就交换，矮就不变。然后第二个位置，和后面一位比，同样的操作... 当到达队尾，再循环回队头，直到将整个队伍过一遍，而没发生一次交换。这样交换的方式有点像气泡上浮的感觉，因此叫冒泡算法。
而插入排序，则是先随便挑个小朋友丢到排序组，然后从剩下的挑一个，和排序组的小朋友比，插入适当位置。之后挑下一个，和排序组里的比较，插入到适当位置... 直到把人都放入排序组。
这两个算法都是平方级的计算复杂度，效率不高，这里还有更好的方法。
打破二次(没有元)的壁垒: 分而治之
为什么一上来就讲平方级的冒泡和插入算法，前面的常数级和线性级呢？只是因为冒泡和插入比较经典吗？
还真不是，只是因为“臣妾做不到啊”。
试想一下有一个可变n个对象的序列，如何只用不变时间来比较排序？还有如何用只过一遍的线性时间，将n个对象进行相互比较？答案是，不可能。因为这违背了宇宙原理，就像最快也不 能超过光速一样。
那么既然都说了有比平方更好的，而常数和线性却不行。难道说...还有算法有介于O(n)与O(n^2)的复杂度？
没错！这就要说天才冯诺依曼提出的合并排序 (Merge Sort)算法了，它利用一种叫做分而治之(Divide and Conquer)的思想找到了一种介于O(n)与O(n^2)之间的复杂度，那就是线性对数 (Linearithmic)复杂度O(n logn).
此外，分而治之还是算法里面一个很重要的思想，将大问题分成一个个简单小问题，从而更快的解决。这启发了之后无数的算法。而合并排序这个距今70多年前提出的算法，现在也还在实际使用。
超越对数
在遥远美国东海岸的华盛顿，附近一个叫做普雷斯顿的小镇，传说镇上存在一个神秘组织，他们通过研究宇宙奥秘，找到了突破宇宙极限，到达线性复杂度的排序算法。这个组织就是——普雷斯顿排序中心。
好吧，其实他们也没研究什么宇宙原理，就是多用了几个桶子 (Bucket)，然后就在美国国家图书馆排序比赛中取得了两次冠军。
首先要声明，对一个序列进行完全排序的话，还是如之前所说线性复杂度是无法到达的。而这里能实现，是前提的：有时候并不需要对序列进行完全排序。比如说，只需要放入几个内部不用分类的桶子，然后对桶子进行排序就好了。这种方法叫做桶排序 (Bucket Sort) 法。
普雷斯顿排序中心就是将图书分成排好序的一些大类，然后将图书照着类放进去就好了。
假设有m个类和n本书，那需要比较的最大次数就是mn次，当n很大m比较小时，其中m可被忽略表示成O(n)，即线性复杂度。
做个理性的处女座：只对需要的排序
到这里，基本就已学完大致的排序算法。你或许早已饥渴难耐，想要赶快找上几册书，或者是几个小朋友排一排序吧。
但是计算机科学家会告诉你，慢着！
这样是没效率的，你这只是为了排序而排序，而真正的排序的目的是为了搜索而存在的。如果你都不搜索，你这样排出来的序又有何用呢。年轻人啊，不要too young too naive，不要出发太远就忘了初心...巴拉巴拉。计算机科学家真讨厌。
但他说的是对的，很多时候需要排的只是队列中一部分，而对整体进行排序无疑是巨大的浪费。比如说百度时我们真正关心的只是前面的链接，选秀节目只关心10进7、5进3，海选死去的千军万马没人关心。
前面桶排序的例子也是，有些大类里并不需要排序，因为人眼在这个范围内可以进行快速搜索，排序反而会花去更多精力。
一个科学成果也支持了这个观点，2011年有研究人员研究了人们整理邮件的习惯，结果发现大部分整理都是没必要的，纯粹是浪费时间。
更多例子：排序与赛制，还有排名的可信度
说到排名次，大家可能立刻会想到比赛的各种赛制。这些赛制，也和排序算法一样，结果无非是为了按照实力给选手们排序。
首先马上能想到的是单淘汰赛 (Single Elimination)，抓对厮杀，赢的进入下一轮，输的淘汰。牛津大学的数学讲师 Dodgson 就是这项赛制的坚决批评者之一，因为实在是太不科学了，真正的第二名可能早就战死在了前几轮和第一名的对战中了。
然后是循环赛 (Round-Robin)，每个队和剩下的n-1个队分别比赛，就像之前宴会拥抱的例子。虽然这种赛制非常好理解，但因为复杂度是O(n^2)的原因，因此也非常费劲。
还有种赛制叫做梯子 (Ladder) 赛，用现在大家熟悉的也可以叫，天梯赛。如今广泛用于各大竞技游戏中，排名接近的人之间进行比赛，根据比赛结果交换位置。有点像之前的冒泡算法。
那非常棒的合并排序算法呢，体育赛事中有没有呢。当然有，比如美国的NCAA锦标赛(相当中国的CUBA)，因为本人很爱国 (其实是不熟悉) 的原因。就举一个更熟悉的例子吧，其实聪明的中国古人早就已用上合并排序算法，那就是科举制。
科举制从上到下分为殿试、会试、乡试、院试，还有县试和府试，而天下读书人从最低的县试与府试开始排序，之后合并到上一级，重新排序，再到上一级... 正与合并排序的思想相同。也正是因为这种巧妙的科举制，所以才有李世民的那句：“天下英雄入我轂中矣！”。
关于这些赛制，还有一个很严肃的问题，那就是这样得出的排名有多大的可信度呢？因为现实世界是一个充满概率的世界，一次比赛的结果可能由很多因素决定。
就如从古至今科举制也漏掉了不少才子，你今晚吃到鸡，不一定就意味着你最强一般。我们还需要关心这个算法有多强的抗干扰性，即使在这样一个充满概率的世界中也能取得足够可信的结果。
上面提到过的算法中冒泡算法就是抗干扰能力比较强的算法，因为每次只在相邻对象间进行交换。但这里还有种叫比较计数排序 (Comparison Counting Sort)的算法比冒泡算法更稳健，一个对象与其他所有对象进行比较，获得一个计数，然后进行排序。很像之前说的循环赛。
这两种算法都是O(n^2)复杂度的算法，虽效率不高，但胜在可信度高，可以稳健地选出最好的几位。这也是为什么类似冒泡算法的天梯赛，还有循环赛在一些需要严谨排名的比赛中盛行的原因。
但从另一个角度来看，确定性即意味着无趣，人生之所以有趣，正因为其中的不确定性。不确定性意味着即使你是咸鱼，有朝一日也有可能大翻身，这无疑让人总能看到希望，感到刺激与挑战。这也是像吃鸡这样充满不确定性的游戏，让人沉迷的原因吧。
大自然也是处女座：啄序与优势等级
其实仔细看来，会发现大自然好像也是处女座，也喜欢排序。而且与之前说的自上而下的排序相反，它有着自己的一套自下而上自发的排序体系。
啄序 (Pecking Orders)，这个来自生物学的名词，指的是群居动物通过斗争取得社群地位的阶层化及支配等级。
对于大多数动物，当处在一个新群体，先要解决的便是如何分配群体内资源，于是就得决定啄序。如何决定呢？
先打上一架再说，比如说一个新鸡群，公鸡们就会大打出手，打得鸡毛四溅，直到决定出啄序。等级高的就理所当然地享有更多的食物和小母鸡。
科学家们还发现，这个决定啄序的过程竟然和排序算法也很类似。还会随着群体规模的增大，发生的争斗次数，也会像排序算法呈平方级或者线性对数级增长。
当决定出啄序之后，群体就会出现优势等级 (Dominance Hierarchies)，于是低啄序的就知道看见高啄序的得绕道走。直到群体中出现新的挑战者，开始新的一轮争斗，决定出新啄序。这其实就是一个转校生打败校园霸王，成为新一代校园霸主的故事。
为了世界和平，多来跑跑步吧
那么为了决定出优先次序，都得先打个死去活来吗？答案是否定的，我们不是鸡也不是猴子，我们有更有效的方法。
说到体育赛事，有种赛制只需常数时间就能决定出次序，那就是跑步。无论多少人，可以只用固定的时间。而类似跑步这样的比赛，伟大之处在于将我们看待排序的视角，从序数 (Order) 转向了基数 (Cardinal)。
之前排序得各个物体之间进行比较，这也是数量越大排序越难的主要原因；而通过设定基数，就变成了所有对象只需和基数比较，这也就大大减少了耗费的时间。
当我们进入工业化社会，建立起了大都市，数以百万计的人需共享同一个空间。如果按照上文说的鸡群，那么为了决定出一个次序，所需要进行斗争的数量将是个天文数字。因此就需要让我们的思想完成一次从序数到基数的跃迁，才能够获得更高的效率。
同时我认为也需要注意基数与序数之间的取舍。设置基数虽然高效，但高效的同时也显得过于粗糙与冰冷。现实世界是复杂的，人也是复杂的，不能仅仅利用一些简单的基数就将所有复杂的情况忽略掉，比如说你不能用钱这个基准就来单纯地衡量一个人的价值。
也如之前搜索的必要性里所提的，对于不是很重要的初步选择，可以设立基数快速筛选；而对于需要重视的部分，我们还是得进行仔细的排序与比较的。就如选秀节目的海选，和最后详细的晋级赛。
最后
最后回到主题，如何做一个最理性的处女座，亦或者我们人人都应该学习点理性处女座的精神。
我认为：对于任何需要处理大量排序的事物，首先建立几个基线标准，将大多数不重要的通过基线标准筛选掉，快速完成初选；之后对于满足基线标准的个体，再进行仔细的比较排序。
如果从这再回看第一章关于如何择偶的问题。这里也提供了一个很好的策略：给自己制定几个标准（嗯，我是一位有标准的男士），然后从大量的人中选择满足这些标准的，最后进行详细排序比较，选择出最好的。
