活动地址：CSDN21天学习挑战赛
本篇讲述最重要的问题类型
排序问题(sorting problem)要求我们按照升序重新排列给定列表中的数据项。当然，为了让这个问题有意义，列表中的数据项应该能够排序。在实践中，我们常常需要对数字、字符和字符串的列表进行排序，最重要的是，类似于学校维护的学生信息、图书馆维护的图书信息以及公司维护的员工信息的记录也需要按照数字或者字符的顺序进行排序。在对记录排序的时候，我们需要选取一段信息作为排序的依据。例如，我们可以按照学生姓名的字母顺序，也可以按照学号或者学生个人的平均分数来对学生记录进行排序。这段特别选定的信息称为键(key)。计算机科学家常常只关心如何对键的列表进行排序，哪怕表中的元素不是记录，也许仅仅是整数。
我们为什么需要有序列表呢？首先，有序列表可能是所求解问题的输出要求，例如对网上搜索结果进行排序，或对学生的平均成绩进行排序。其次，排序使我们更容易求解和列表相关的问题。其中最重要的是查找问题：这就是为什么字典、电话簿和班级名册都是排好序的。同样原因，在很多其他领域的重要算法(例如几何算法和数据压缩)中，排序也被作为一个辅助步骤。贪婪算法是本书后续章节将要讨论的一个重要算法设计技术，它也要求有序的输入。
到目前为止，计算机科学家已经开发出了几十种不同的排序算法。实际上，有人形象地把发明一种新的排序算法比喻为像设计一种更棒的捕鼠器那么困难。但我们很高兴地告诉大家，寻找更好的“捕鼠器”这个行动还在继续。这种百折不挠的精神是令人钦佩的，原因如下：一方面，有少数不错的排序算法，只需要做大约 nlog,n 次比较就能完成长度为n 的任意数组的排序；另一方面，没有一种基于“键”值比较(相对比较键值的部分内容而言)的排序算法能在本质上超过它们。
排序领域有着那么多的算法，为什么还会出现这种困境呢？这不是没有原因的。虽然有些算法的确比其他算法更好，但没有一种算法在任何情况下都是最优的。有些算法比较简单，但速度相对较慢；另外一些速度比较快，但更复杂。有些算法比较适合随机排列的输入，而另一些则更适合基本有序的列表。有些算法仅适合排列驻留在快速存储器中的列表，而另一些可以用来对存储在磁盘上的大型文件排序，如此等等。
排序算法有两个特性特别值得一提。如果一个排序算法保留了等值元素在输入中的相对顺序，就可以说它是稳定的(stable)。换句话说，如果一个输入列表包含两个相等的元素，它们的位置分别是i和j， i
查找问题(eeaching problem)就是在给定的集合(或者是多重集,它允许多个元素具有相同的值)中找一个给定的值(我们称之为查找键(search key)。有许多查找算法可供选择，其中既包括直截了当的顺序搜索，也包括效率极高但应用受限的折半查找，还有那些将原集合用另一种形式表示以方便查找的算法。最后一类算法对于现实应用具有特别重要的价值，因为它们对于大型数据库的信息存取来说是不可或缺的。
对于查找来说，也没有一种算法在任何情况下都是最优的。有些算法比其他算法速度快，但需要较多的存储空间；有些算法速度非常快，但仅适用于有序的数组。和排序算法不同，查找算法没有稳定性问题，但会发生其他问题。具体来说，如果应用里的数据相对于查找次数频繁变化，查找问题就必须结合另外两种操作一起考虑：在数据集合中添加和删除元素的操作。在这种情况下，必须仔细选择数据结构和算法，以便在各种操作的需求之间达到一个平衡。而且，对于用于高效查找(以及添加和删除)的特大型数据集合来说,如何组织其结构是一个不同寻常的挑战，而这对实际应用具有非常重要的意义。
近些年来，处理非数值数据的应用增长迅速，引发了研究人员和业界对字符串处理算法的极大兴趣。字符串(string)是字母表中的符号所构成的序列。我们尤其关心文本串，它是由字母、数字以及特殊符号构成的；位串是由“0”和“1”构成的：基因序列也可以用字符串模型来表示，只不过它的字母表只包含 4 个字母，即{A,C,G,T}。但需要指出的是，由于编程语言以及编译的需要，字符串处理算法在计算机科学中一直都非常重要。
如何在文本中查找一个给定的词，这一特殊问题引起了研究人员的特别关注，他们称其为字符串匹配(string matching)问题。针对此类查找的特性，人们发明了好几种算法。
算法中最古老也最有趣的领域是图算法。通俗地讲，可以认为图(graph)是由一些称为顶点的点构成的集合，其中某些顶点由一些称为边的线段相连(下一节将给出一个更严格的定义)。图之所以成为一个令人感兴趣的对象，既有理论上的原因，也有实践上的原因。图可以对广泛的、各种各样的实际应用进行建模，包括交通、通信、社会和经济网络，项目日程安排以及各种比赛。研究互联网在技术和社会层面的各种具体问题，是现阶段计算机科学家、经济学家和社会学家共同关注的热点问题。
基本的图算法包括图的遍历算法(如何能一次访问到网络中的所有节点)、最短路线算法(两个城市之间的最佳路线是哪条?)以及有向图的拓扑排序(一系列课程的预备课程是相互一致的，还是自相矛盾的？)。幸运的是，这些算法可以用来阐明一些通用的算法设计技术。
有一些图问题在计算上是非常困难的。其中最广为人知的恐怕要数旅行商问题和图填色问题了。旅行商问题(traveling salesman problem, TSP)就是找出访问n个城市的最短路径,并且保证每个城市只访问一次。它的主要应用包括路径规划，主要出现在一些现代应用中，例如电路板和超大规模集成电路的制造，X 射线晶体学以及基因工程等。图填色问题(graph-coloring problem)就是要用最少种类的颜色为图中的顶点填色，并保证任何两个邻接顶点的颜色都不同。这个问题源于若干应用，例如安排事务进度：如果用以边相连的顶点来代表事务，当且仅当独立事务无法排定同时发生时，图填色问题的解才能生成一张最优的日程表。
从更抽象的角度来看，旅行商问题和图填色问题都是组合问题(combinatorial problems）的特例。有一些问题要求(明确地或者隐含地)寻找一个组合对象，例如一个排列、一个组合或者一个子集，这些对象能够满足特定的条件并具有我们想要的特性，如价值最大化或者成本最小化。
一般说来，无论从理论角度还是实践角度来看，组合问题都是计算领域中最难的问题。这是出于以下原因。第一，通常，随着问题规模的增大，组合对象的数量增长极快，即使是中等规模的实例，其组合的规模也会达到不可思议的数量级。第二，还没有一种已知算法能在可接受的时间内，精确地解决绝大多数这类问题。而且，大多数计算机科学家认为这样的算法是不存在的。但这个猜想既没被证实，也没被证伪，所以这仍然是计算机科学理论领域中悬而未决的最重要问题。
有些组合问题用高效的算法求解，但我们应该把它们当作幸运的例外。这些例外中就包含前面提到的最短路径算法。
几何算法(geometric algorithm)处理类似于点、线、多面体这样的几何对象。古希腊人非常热衷于开发一些过程(当然，他们不会称其为算法")来解决各种各样的几何问题，包括用没有刻度的尺和圆规绘出简单的几何图形，如三角形、圆形等。二千多年以后，对几何算法一度消失的强烈兴趣，在计算机时代复兴了，虽然没有尺和圆规，但有比特、字节以及和古人相同的良好创造力。当然，如今人们对几何算法感兴趣是因为一些完全不同的应用，例如计算机图形学、机器人技术和断层×摄像技术等。
数值问题(numerical problem)是另一个广阔的具体应用领域，涉及具有连续性°的数学问题：像解方程和方程组，计算定积分以及求函数的值等。对于大多数这样的数学问题，我们都只能近似求解。另外一个主要的困难是因为这样一个事实：这类问题一般都要操作实数，而实数在计算机内部只能近似表示。而且，对近似数的大量算术操作可能会将人量的舍入误差叠加起来，导致个看似可靠的算法输出的是被严重歪曲的结果。
多年以来，人们在这个领域中开发出大量成熟的算法，这些算法在许多科学和工程应用中一直扮演着至关重要的角色。但在过去的三十年中，计算机业界将注意力转移到了商业应用。这些新的应用主要需要另外一些算法，它们能对信息存储、取出，再通过网络传输和呈现给用户。作为这种革命性变化的结果，数值分析丧失了它在计算机科学界和业界的应用统治地位。然而，对于计算机专业人士来说，至少掌握数值算法的基本概念还是非常重要的。