29、排序（1 / 1）

我们从周围世界获取的信息总是以文字或符号的形式来描述或存储，即使是计算机硬盘中存储的二进制序列，其本质也是文字与符号。文字与符号伴随着整个人类文明史，期间积累和存储了大量的信息，尤其是计算机和互联网的发明，使信息的存储量爆炸式的增长，并将人们带到了大数据时代。如何在大量信息中获取自己想要的信息，仅仅依靠简单的分类、索引和目录已经不够，因为随便某个细分的分支领域都包含大量的信息，这时，我们就需要对不同信息相对我们想要获得的答案的重要程度进行排序，将我们想知道的东西排在前面。对信息进行排序的想法和算法催生了谷歌这样的伟大的互联网公司。

如果将N组信息进行排序，显然有N的阶乘种可能的排序方式。阶乘函数是一类比普通的指数函数增长更快的方式，因此即使是数据的组数不是很大的情况下，其可能的排序方式也是天文数字级别的，这也为设计排序算法提供了几乎无限的可能。依据什么样的原则设计排序算法成了评价算法优劣的重要标准。在互联网初创时期，评价大量网页的优劣程度并进行排序成为一种重要的用户需求，许多搜索引擎公司应运而生。最初，他们进行排序的依据是网页的点击流量和网页上与用户输入关键字相同的数量，由于流量和关键字很容易造假，排序质量并不高，许多优秀网页被挤出第一页，而大量依靠刷流量和堆砌关键字的网页占据了显眼的位置。谷歌从文献检索中找到了灵感，不再以流量和关键字为主要依据，而是认为，一个网页如果与其它网页链接数量更多，也就是被其它网页引用的越多，它本身的价值就越大，排名也就越靠前。这种方式产生的搜索效果立竿见影，由于它的排序方式仅仅与网页在互联网中与其它网页链接的结构有关，因此可以自动运行，不需要等用户在搜索框内输入关键字之后再临时搜索，保证了搜索速度。正是这种看似寻常的解决问题的思路，成就了谷歌在互联网公司中的地位。

经典的旅行推销员问题也是一个搜索排序的例子，一位推销员从某个城市出发，经过N个城市，每个城市只经过一次，最后回到出发点，那么如何选择才能保证总路程最短。显然可能的路径条数也是由N的阶乘决定，仍然是一个天文数字的级别。寻找最优解是一个NP完全问题，也就是NP问题中最难的一类，因此寻找最优解目前是不现实的。然而，如同搜索引擎一样，我们的用户其实要求并不是太高，在许多场景中，没必要去寻找最好的那种选择，只要找到的答案足够好，达到或超过用户的预期即可。所以，旅行推销员问题也可以依据某种原则大幅度简化问题，从而在短时间内找到最优解的近似值。在A城和B城之间找到一点C城，找到A到C和C到B之间的最短路径要容易的多，而A到B的最短路径不可能比这两个最短路径的连接更长，这样就筛选掉了大量不可能最短的路径，如果需要进一步简化计算量，还可以插入更多的城市。因此，在求解最优近似解的过程中，没必要穷举所有的可能性，而GPS导航的算法就是依据这样的原理进行的。

由于阶乘函数极快的增长速度，我们只能在某些经验原则的基础上寻找近似值，所以我们可以大胆的说，谷歌的搜索引擎和GPS导航算法得到的结果，几乎不可能是最好的，因此这些领域仍然有提升的空间，或许在不久的将来，我们可以发明更好的搜索引擎和GPS导航仪。

对信息进行排序的目的是找到对我们来说重要的信息，而忽略那些无关紧要的细枝末节，从而节约时间，提高效率，这也是一种将非结构化信息结构化的方式。不同信息相对我们的重要程度也类似于二八法则，百分之二十的重要信息给予我们百分之八十的帮助，不同的信息存在不同的权重，信息的这一点属性有助于我们提高学习效率。比如记忆英语单词，英语单词量的保守估计在50万左右，而英语四六级要求掌握的单词只有4000到6000左右，而且每个单词在文章中出现的频率也有很大的差别。显然，按照单词出现频率进行排序后再记忆的方式要比抱着一本牛津词典从第一页翻到最后一页的效率要高。

很多时候，我们都会需要对信息进行检索，有时候我们也只需要前几条甚至第一条信息，搜索引擎及数据库的强大检索功能让我们如猫添翼，几乎可以说扩展了我们有限的小小的大脑功能。在这个互联网高速发展的大时代，许多传统的观念也必然受到了冲击，在大量杂乱无章的信息中快速找到期望中的答案的能力，显然要比单纯背诵和记忆信息更加重要。排序方法为我们的信息增加了一个维度，也就是相应于每一个信息，都对应一个权重值，当这个权重越高时，表明这个信息越重要，我们就越希望它能排在前面，被我们优先认识到。这样，在我们有限的时间与生命中，就可以优先学到重要的知识，使自己不至于迷失在信息的海洋里。

在排序问题上，我们在悠久的历史中总结出了许多经验规则。无论是大学餐厅里排队买饭的先来后到，还是通过考试、打分，择优录取的考试制度，或者互相攀比谁的公司大，谁挣钱多，再到某群人在某个人心中不同的分量，本质上都是一种排序的过程，甚至排序结果的好坏程度也是见仁见智，有时候也没有统一的标准。但这些规则的确在起作用，我们的经验准则、学生守则和企业规章制度等等，实际上就是一套在经验中总结出来的规则，不同规则下的不同排序方式，看上去就像是一场场游戏，制定规则，参与其中，或者成功，或者被淘汰，成了每个人生活的一部分。