本节书摘来自华章出版社《算法基础：打开算法之门》一书中的第3章，作者 ［美］托马斯 H 科尔曼（Thomas H Cormen），更多章节内容可以访问云栖社区“华章计算机”公众号查看

第3章

Algorithms Unlocked
排序算法和查找算法

在第2章中，我们看到了在数组上进行线性查找的三个算法。我们能做得更好吗？答案是：看情况。如果不清楚数组中的元素是否有序，我们是不可能做得更好的。在最坏情况下，我们必须查找数组的所有n个元素，因为如果在前n-1个元素中不能找到要找的值，那么要查找的元素可能在第n个位置上。因此，当我们不清楚数组中的元素是否有序时，我们不可能实现比Θ（n）更好的最坏情况运行时间。

然而，假定数组是以非递减顺序排序的，那么根据“非递减”的含义得出每个元素均小于或者等于它的后继。在这一章中，我们会看到当数组有序时，能够使用二分查找的简单技术来实现从包含n个元素的数组中查找元素的时间复杂度为O（lgn）的算法。正如第1章提到的，与n相比，lgn增长更缓慢，因此二分查找法在最坏情况下会优于线性查找。

如果你是一个非计算机专业人士，同时你未阅读14节，那么你应该回过头去阅读关于对数的那部分内容。

一个元素比另一个元素小意味着什么呢？当元素是数字时，结果是显然的。当元素是字符串时，我们会联想到字典序：如果在字典中某元素出现在另一个元素的前面，那么该元素就小于另一个元素。当元素是其他形式的数据时，我们必须自定义“小于”的含义。只要对“小于”有了清晰的概念，我们就能判定数组是否是有序的。

回忆第2章中在书架上查找书的例子，我们能将书籍按照作者名排序，也可以按照书名排序，如果书籍陈列在图书馆中，那么也可以按照索书号排序。在本章中，如果书籍是按照作者名的字母序从左到右排序，25则称书架上的书籍是有序的。然而，书架上也可能包含由同一个作者写的多本书，比如你有好几本由莎士比亚写的书。如果我们并非想要查找由莎士比亚所写的任意一本书，而是某本特定的书，那么如果两本书有相同的作者，我们就假定这两本书是按照书名的字母序从左到右排序。再或者，如果我们关心的仅仅是作者的名字，那么当进行查找的时候，任何一本由莎士比亚所写的书均可以作为我们要查找到的最终结果。我们称要匹配的信息为关键字。在书架的例子中，关键字是作者的名字，而不是作者名和书名的组合，后者是为了处理同一个作者有两部作品的情况。

那么，我们如何才能获得排好序的数组呢？这一章中，我们将看到4个算法——选择排序、插入排序、归并排序和快速排序——为了将一个数组排好序，我们要将其中一个算法应用到我们所讲的书架这个例子上。每种排序算法都有优点和缺点，在本章最后我们将回顾和比较这些排序算法。在本章中我们要学到的所有算法在最坏情况下的运行时间或者等于Θ(n2)，或者等于Θ(nlogn)。因此，如果仅仅需要执行几个查询，你***直接执行线性查找。但是如果你将进行多次查找，那么***先将数组排序，然后执行二分查找算法。

排序本身就是一个重要的问题，而不仅仅是二分查找的预处理步骤。考虑所有需要排序的数据，例如电话簿需要按照名字排序；每月银行对账单支票或者需要按照支票号排序，或者需要按照银行处理账单的日期排序；甚至由网络搜索引擎搜索的结果也需要按照与查询的相关性进行排序等。而且，排序通常是其他算法中的一个步骤。例如，在计算机图形学中，对象往往会相互层叠在一起。这时需要这样一个程序：它能够将屏幕上的对象按照“上方”关系排序以便能够实现按照从底部到顶部的顺序依次绘制对象。

在继续讲述前，还需说明我们要对什么进行排序。除了关键字（进行排序时，我们将其称为排序关键字）之外，通常我们将排序过程中的剩余元素称为卫星数据（satellite data）。尽管卫星数据可能来自卫星，但是通常它并非来自卫星。卫星数据是和排序关键字关联的信息，在重排元素时，卫星数据也需要随着关键字进行重排。例如书架这个例子，排序关键字是作者的名字，而卫星数据就是书本身。

我以下面这种方式给学生们解释卫星数据的含义，以保证他们能明白该词。我将学生的等级成绩保存至一份电子数据表中，26其中每行是按照学生的名字排序的。为了得出学期末的最终课程成绩，我重排了行，此时排序关键字是包含着学生课程分数的那一列，而其余列（包含学生姓名）均被称作卫星数据。我将分数按照降序排列，因此位于顶部的那些行的成绩为A，而靠近底部的那些行的分数为D或者E。

Dartmouth使用E而不是F来表示不及格的成绩。我不清楚为什么这样表示，但是通过将字母形式的等级成绩转化为四维的数值型等级成绩，而不是五维的，我猜测如此能更加简化计算机程序。

假设我仅仅重排了包含分数的那一列，而没有重排包含分数的整行，那么最终结果是学生姓名依然是按照字母顺序排序的。这就会让名字排在字母表前面的学生因为他们的分数高而很开心，而名字排在字母表后面的学生因他们的分数低而不开心了。

以下是关于排序关键字和卫星数据的其他例子。在电话簿中，排序关键字是名字，而卫星数据是地址和电话号码。在银行对账单中，排序关键字是支票号码，而卫星数据包含支票金额和标注的交易日期。在搜索引擎中，排序关键字是查询的相关性的评估结果，而卫星数据是网页的网址，再加上搜索引擎所存储的跟该网页相关的其他数据信息。

本章中我们针对数组进行讨论，同时假定每个元素仅仅包含一个排序关键字。如果要实现下述的任意一个排序算法，你一定要确保当重排元素时，相应的卫星数据也要进行相应的重排操作，或者保证当重新排序关键字时，指向卫星数据的指针要做相应的变换。为了将书架模拟为计算机数组，我们需要假定书架和书需要满足两个额外的特性，我承认这点不太切合实际。首先，书架上的所有书大小规格一样，因为在计算机数组中，数组中的所有项占用相同的空间大小。其次，我们能按照书架上书的位置对其从1到n进行编号，并且我们将每一个站位称为一个位置。位置1是最左侧的位置，而位置n代表最右侧的位置。正如你可能猜到的，书架上的每个位置均相应地对应着数组中的一项。

我也想说说“排序”（sorting）这个词。27一般意义上的排序和我们在计算使用中的排序的含义不同。我电脑中的在线词典上是这样定义的，“组内系统地整理；根据类型或者类别分类等”：例如你可能这样“排序”你的衣物，衬衫放在一个地方，裤子统一放在另一个地方，等等。在计算机算法领域中，排序意味着按照一个明确定义的顺序排列，此时“组内系统地整理”也称为“分桶”（bucketing）、“桶状的”（bucketizing）或者“装箱”（binning）等。