重要的问题类型

本节，我们开始讲述最重要的问题类型：

排序问题要求我们按照升序重新排列给定列表中的数据项。

在实践中，常常需要对各种字母，字母表中的字符和字符串等数据构成的列表进行排序。这段特别选定的信息称为键.

我们为什么需要有序列表呢？

其中最重要的是为了查找。

不同的排序算法应对不同的实际情况。有些算法简单，但是速度相应较慢；有些算法较快，却很复杂；有些算法较适合随机排列的输入；有些算法更适合基本有序的列表；有些算法仅适合排列驻留在快速存储器中的列表；有些算法可以用来对存储在磁盘上的大型文件排列。

排序算法两个特性。

若一个排序算法保留了等值元素在输入中的相对顺序，我们就说它是稳定的。一般来说，分开很远的键相互交换的算法是不稳定的，但往往速度很快。后面，我们将会看到这段通用注解是如何应用于重要的排序算法的。

第二个值得注意的特性是算法需要的额外存储空间。如果一个算法除了个别存储单元以外，不需要额外的存储空间，我们称它为在位的。

查找问题涉及到从给定的集合（或者是多重集)中找寻一个给定的值，称为查找键.

查找算法有直截了当的顺序搜索，效率极高但应用受限的折半查找，将原来集合表示为另一种形式以方便查找的算法。最后这类算法对于现实应用特别重要，因为它们对于大型数据库的信息存取来说是不可或缺的。

对于查找，没有一种算法对于任何情况都是最适合的。

查找算法常遇到一个问题。如果支撑应用的数据，相对于查找次数频繁变化，查找就必须结合添加和删除元素的操作。

在本本中查找一个给定的词为串匹配问题。

我们会在第3章介绍蛮力字符串匹配算法，在第7章讨论Horspool算法和Bayer-Moore算法。

图是由称为顶点的点构成的集合，某些顶点由一些称为边的线段相连。

图可以对实际应用建模，包括交通和通讯网络，项目时间表和各种竞赛。最近一个令人感兴趣的应用是估计因特网的直径，即顺着两个网页之间的最短路线会经过的最大链接数。

基本图算法包括遍历算法（如何能一次访问到网络中的所有节点），最短路线算法以及有向图的拓扑排序（一系列过程的前提条件是相互一致的还是自相矛盾的？）。

计算上困难的图问题有旅行商问题和图填色问题。

旅行商问题就是找出访问n个城市的最短路径，并且保证每个城市只访问一遍。

图填色问题要用最少种类的颜色为图中的顶点填色，并保证任何两个邻接顶点的颜色不同。这个问题源于这些应用，比如安排事务进度，用顶点代表事务，当且仅当相互关联的事务不能安排在同一时间发生时，图填色问题的解才生成一个最优的事务进度。

旅行商和图填色问题是组合问题的特例。

有一些问题要求寻找一个组合对象，比如一个排列，一个组合或者一个子集，这些对象能够满足特定的条件并具有我们想要的特性（比如：价值最大化或成本最小化）。

几何问题处理类似于点，线，多面体这样的几何对象。

本书讨论两个经典的计算几何问题：最近对问题和凸包问题。

最近对问题求的是给定平面上的n个点中，距离最近的两个点。

凸包问题要求找一个能把给定几何中所有点包含都在里面最小凸多边形。

数值问题涉及具有连续性的数学对象问题：像解方程和方程组，计算定积分以及求函数的值等等。

对于这些问题，我们仅能近似求解。主要是因为，这类问题一般操作实数，而实数在计算机内部只能近似表示。对近似数做大量算术操作将大量的舍入误差叠加起来，导致一个被严重歪曲的输出。

我们将6.2节高斯消去法，10.4节数值算法的挑战和11.4节解非线性方程算法讨论。