Design Iterative Algorithms

If you are designing describing and proving correct an algorithm using loop invariants, the following is the list the things must consider.

Specification: Define the problem (pre and post conditions): likely defined by the problem.

Define Loop Invariant: It needs to be a picture of what is true every time the algorithm is at the top of the loop. 

Establishing the Loop Invariant:

  <pre-cond> & code_pre-loop => <Loop Invariant>

·      state what you know about the input instance because of <pre-cond>

·      state the effect of the code before the loop

·      State how it then follows that <loop invariant> has been established.

Different types of Iterative Algorithms

Here are a few classic types of iterative algorithms to help you design a measure of progress and a loop invariant.

More of the Output:  if the solution is a structure composed of many pieces (e.g., an array of integers, a set, or a path), a natural thing to try is to construct the solution one piece at a time.

·      Measure of Progress:  The amount of the output constructed.

·      Loop Invariant: The output constructed so far is correct

More of the Input:  Suppose the input consists of n objects ( e.g., an array of n integers or a graph with n nodes). It would be reasonable for the algorithm to read them in one at time.

·      Measure of Progress:  The amount of the input considered.

·      Loop Invariant: Pretending that this prefix of the input is the entire input, I have a complete solution.

Narrowing the Search Space: If you are searching for something, try narrowing the search space, maybe decreasing it by one or, even better, cutting it in half.

·      Measure of Progress: the size of the space in which you have narrowed the search.

·      Loop Invariant: If the thing be searched for is anywhere, then it is in this narrowed sublist.

GCD LIKE: substitute the input with other instance much easier or smaller.

·      Measure of Progress: the new instance replacing the original input has smaller size or easier.

·      Loop Invariant:  if the new instance has been constructed whose solution is the same as the original instance, then I have the solution

算法总结系列之八:复读机的故事 - 散列表.NET应用的研究(下集)

估计写这么个题目会被扔鸡蛋, 因为实在是太大了. 各位不要期望太高啊,我写这东西,就是为了给自己个备忘. 你们要是把它当垃圾看, 说不定还能发现点什么东西.

言归正题. 说实话, .NET Framework的实现可能比我们认为的要好一些, 比如线程安全, 代码效率, 甚至以及代码风格方面. 比如HashTable 的实现就是一个比较好的佐证.

上文说到, .NET Framework 中的哈希表, 使用了双重散列的方式来计算散列值. 那么到底精确的来说, 是采用了什么关系式呢? 实际上很简单, 这个关系式就是:

h(key, n) = h1(key) + n*h2(key)

算法总结系列之八:复读机的故事-散列表及其在.NET中的应用浅析(上集)

记得3年前还在上一家公司的时候, 一天下午一个哥们很激动的在偶旁边念叨"散列表真是个好东西,散列表真是个好东西...."绵绵不绝, 偶石化继而抓狂,奋起曰:"你复读机啊你复读机啊你复读机啊...".

散列表不是复读机, 散列表更像是一个大池子(但是不是所有的大池子都可以认为是散列表). 这个特殊的大池子有这样的特点, 它的容量总是要比你想要存储的元素数量大, 它能利用大出一部分容量的特点, 让你能更加快速的查找定位某一元素.

牺牲一点点内存,换取更高效的表现, 有人问值不值得?  大哥,现在1G的内存都100多块钱了...

第一部分: 散列表的基本知识

散列表是这样一种数据结构: 它利用散列函数(通常称为函数h(k))计算元素关键字(标记k)的散列值, 并根据该散列值, 直接确定(或者通过简单数学计算)该元素在散列表中的存储位置(散列表中的存储位置我们称为槽Slot). 如果两个元素关键字通过散列函数的计算获得了同样的散列值, 从而指向散列表中的同一个槽, 我们称这种现象为"碰撞(Collision)".由于元素关键字域U的容量大于散列表T的容量m, 所以完全避免碰撞是不可能的. 这就引申出了散列表最为重要的两个问题:

算法总结系列之七:选择问题(Randomized Select)

"能否以O(n)的时间复杂度, 从一个未排序的整数数组中选取第i大的整数出来?"

你面试的时候,有人问过你这样的问题吗?

这类有关大小排序选取的选择问题是极容易出现在面试题目中的问题,在算法学上,我们把这类问题统称为"选择问题", 也称之为"中位数问题".

选择问题的解决, 不一定要先排序然后遍历(事实上这是比较慢的做法,排序的时间复杂度决定了它不可能比O(nlgn)快). 通常选择问题只是要求知道第i大/小的元素, 所以我们可以将它当作排序算法的简化. 我们以快速排序为例, 我们以划分的区间判断,选择问题我们只追究可能出现问题解的一个区间,而快速排序要处理两个区间.

当待选择元素足够均匀时, 本文的RandomizedSelect算法可以达到O(n)的时间复杂度, 而最坏情况下,它的时间复杂度可能是O(n * n).这里有必要着重说明一下, O(n*n)的算法复杂度是RandomizedSelect算法的上限, 而不是它的平均复杂度, 除非是特别设计(样本间元素满足特定关系多项式)的样本, RandomizedSelect算法一般可以认为它的平均时间复杂度是O(n).

算法总结系列之六: 桶排序(Bucket Sort)

桶排序是另外一种以O(n)或者接近O(n)的复杂度排序的算法. 它假设输入的待排序元素是等可能的落在等间隔的值区间内.一个长度为N的数组使用桶排序, 需要长度为N的辅助数组. 等间隔的区间称为桶, 每个桶内落在该区间的元素. 桶排序是基数排序的一种归纳结果

算法的主要思想: 待排序数组A[1...n]内的元素是随机分布在[0,1)区间内的的浮点数.辅助排序数组B[0....n-1]的每一个元素都连接一个链表.将A内每个元素乘以N(数组规模)取底,并以此为索引插入(插入排序)数组B的对应位置的连表中. 最后将所有的链表依次连接起来就是排序结果.

这个过程可以简单的分步如下:

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。

算法总结系列之五: 基数排序(Radix Sort)

基数排序是非比较排序算法,算法的时间复杂度是O(n). 相比于快速排序的O(nlgn),从表面上看具有不小的优势.但事实上可能有些出入,因为基数排序的n可能具有比较大的系数K.因此在具体的应用中,应首先对这个排序函数的效率进行评估.

基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序(我们常用上一篇blog介绍的计数排序算法, 因为每个位可能的取值范围是固定的从0到9).这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

比如这样一个数列排序: 342 58 576 356, 以下描述演示了具体的排序过程(红色字体表示正在排序的数位)

算法总结系列之三 : 计数排序(CountingSort

计数排序, 基数排序, 桶排序等非比较排序算法,平均时间复杂度都是O(n). 这些排序因为其待排序元素本身就含有了定位特征,因而不需要比较就可以确定其前后位置,从而可以突破比较排序算法时间复杂度O(nlgn)的理论下限.

计数排序是最简单的特例,它要求待排序元素是位于0到k之间的正整数, 因而它是很特殊的情况,基本上没有特别的应用价值; 但是另一方面, 它又是基数排序的基础,或者说是一部分,所以简单的描述一下:

输入数组 A : 元素特征是 0-k的正整数,可以有重复值;

输出数组 B : 输出A的一个非减序列

中间数组 C : 大小是k, 它的i( 0<= i <= k)索引位置存储的是A元素集合中值是k的元素的个数有关.

算法总结系列之二: 快速排序(QuickSort)

快速排序是现有的比较排序算法中,效率最好的一种排序算法.

所谓比较排序,是对排序对象的值的比较, 它不特定于排序对象本身的额外特征或排序对象因特定的数据结构而获得的额外条件.

快速排序主要体现分而治之的思想, 主要做法是不断的"选取基准点 - 划分子序列",直至子序列长度为1.

假定数组A[p.......r] - p,r都是数组下标.

算法总结系列之一:堆排序(Heap Sort)

    在软件设计相关领域,"堆(Heap)"的概念主要涉及到两个方面:

• 一种数据结构, 逻辑上是一颗完全二叉树,存储上是一个数组对象(二叉堆).
• 垃圾收集存储区,是软件系统可以编程的内存区域.

    本文所说的堆,指的是前者.另外, 这篇文章中堆中元素的值, 均以整型为例.

    堆排序的时间复杂度是O(nlgN),与快速排序达到相同的时间复杂度. 但是在实际应用中,我们往往采用快速排序而不是堆排序. 这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现. 堆排序的主要用途,是在形成和处理优先级队列方面. 另外, 如果计算要求是类优先级队列(比如, 只要返回最大或者最小元素, 只有有限的插入要求等), 堆同样是很适合的数据结构.

比较排序算法——桶排序（Bin Sort）

平均情况下桶排序以线性时间运行。像计数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具体来说，计数排序假设输入是由一个小范围内的整数构成，而桶排序则 假设输入由一个随机过程产生，该过程将元素一致地分布在区间［0，1）上。 桶排序的思想就是把区间［0，1）划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在［0，1）上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。 在桶排序算法的代码中，假设输入是个含n个元素的数组A，且每个元素满足0≤ A[i]<1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶，并假设可以用某种机制来维护这些表。桶排序的算法如下，其中 floor(x)是地板函数，表示不超过x的最大整数。

并行算法——指针转移（欧拉回路技术

为了在PRAM中存储二叉树，我们采用了简单的二叉树表示法。每个结点i有三个域 parent[i],left[i],right[i]，分别指向结点i的父母、左子女和右子女。假定每个结点用一个非负整数来表示。我们为每个结点联接 三个而不是一个处理器，其原因我们在下面将会明白。称这三个处理器为结点的A，B和C处理器，我们可以很容易地在结点与其三个处理器之司找出对应关系。例 如，结点i可以与处理器3i，3i+1和3i+2相联接。 在串行RAM上，计算包含n个结点的树中每个结点的深度所需运行时间为O(n)。采用一种简单的并行算法来计算结点深度时，算法可以从树的根结点开始把一种“波”向下传输。这种波同时到达深度相同的所有结点，因此通过对波载计数器增值，我们就能计算出每个结点的深度。 这种并行算法对完全二叉树很适用，这是因为其运行时间与树的高度成正此。而树的高度最大为n-1，这时算法的运行时间为O(n)，这并不优于串行算法。 但是，如果我们运用欧拉回路技术，不论树的高度是多少，都能够在EREW PRAM上用O(lgn)的运行时间计算出结点的深度。 一 个图的欧拉回路是通过图的每条边一次一个回路，当然，在此过程中它可以多次访问一个结点。根据图论算法可知，一个有向连通图具有欧拉回路当且仅当对所有结 点v，v的出度等于v的入度。因为无向图每条无向边(u，v)对应于相应的有向图中的两条边(u，v)和(v，u)，因此任何无向连通图改成的有向图均包 含欧拉回路，这对无向树也自然成立。 （a） （b） 图4 运用欧拉回路技术来计算每个结点在二叉树中的深度 为了计算二叉树T中结点的深度，首先在改写的有向树T中形成一个欧拉回路。该回路对应于树的遍历过程，如图4(a)所示，它可以用一个连接树中所有结点的链表来表示。其结构如下： 1. 如果结点的左子女存在，则结点的A处理器指向其左子女的A处理器，否则就指向自身的B处理器； 2. 如果结点存在右子女，则结点的B处理器指向其右子女的A处理器，否则就指向其自身的C处理器。 3. 如果一个结点是其父母结点的左子女，则结点的C处理器指向其父母的B处理器，如果该结点是其父母结点的右子女，则结点的C处理器指向其父母的C处理器。根结点的C处理器指向NIL。 因此，根据欧拉回路形成的链表的表头是根结点的A处理器，表尾是根节点的C处理器。如果已知构成原始树的指针，则我们可以在O(1)的时间内构造出欧拉回路。 在我们获得表示T的欧拉回路的链表后，我们在每个A处理器中放入值1，在每个B处理器中放入值0，在每个C处理器中放入值-1，如图4(a)所示。然后如第1.2节中那样，我们运用满足结合律的普通加法来执行并行前缀计算。图4(b)说明了并行前缀计算的结果。 我们说，在执行完并行前缀计算过程后，每个结点的深度值在结点的C处理器中。为什么呢？我们按以下要求把数放入A，B和C三个处理器中：访问子树的最后 结果是把运行和加上0。每个结点i的A处理器对其左子女树的运行和加1，这表明i的左子女的深度比i的深度大1。B处理器对运行和没有影响，这是因为i的 左子女的深度与其右子女的深度相等。C处理器使运行和减1，以便对i的父母结点来说，对以i为根结点的子树进行访问后运行和不会改变。 我们可以在O(1)的时间内计算出表示欧拉回路的列表。列表中包含3n个对象，所以执行并行前缀计算过程仅需O(lgn)的运行时间。因此，计算所有结 点深度所花费的全部运行时间为O(lgn)。又因为算法执行中不需要对有存储器执行并发存取操作，所以该算法是一个EREW算法。

并行算法——指针转移（表排序）

我们介绍的第一个并行算法是有关列表的。列表在PRAM中的存储方式与普通的 RAM相同。为了便于并行地对列表中的对象进行操作，我们为每个对象分配一个“响应”处理器。假定处理器数目与列表中的对象一样多，并且第i个处理器负责 处理第i个对象。例如，图2(a)说明了一个由对象序列<3,4,6,1,0,5>组成的链表。由于每个对象对应于一个处理器，所以表中的每 个对象都可由其响应处理器在O(1)的时间内对其进行操作。 （a） （b） （c） （d） 图2 运用指针转移在O(lgn)时间内求出n个对象组成的链表中每个对象到表尾的距离 假定已知一个包含n个对象的单链表L，我们希望计算出表L中的每个对象到表尾的距离。更形式地说，如果next是指针域，我们希望计算出表中每个对象i的值d[i]，使得： 我们把这一计算d值的问题称为表排序问题。 解决表排序问题的一种方法是从表尾把距离往回传输。因为表中从末端开始的第k个对象必须等到其后的k-1个对象确定了它们到表尾的距离后才能确定其自身到表尾的距离，所以这一方法需要O(n)的运行时间。实际上，这一解决方法是一种串行算法。 下面的代码给出了一种有效的并行算法，其运行时间仅为O(lgn)。 List-Rank(L) 1. for 每个处理器i，并行地执行 2.   do if next[i]=NIL 3.        then d[i]←0 4.        else d[i]←1; 5. while 存在一个对象i，满足next[i]≠NIL 6.   do for 每个处理器i，并行地执行 7.        do if next[i]≠NIL 8.             then d[i]←d[i]+d[next[i]]; 9.                  next[i]←next[next[i]]; 图2说明了算法是如何计算出各个距离值的。图中的每个部分说明了执行第5-9行的while循环的迭代操作以前列表的状态。在第一次迭代中，表中开头5个对象的指针不为NIL，所以由其响应处理器分别执行第8-9行的操作。其操作结果见图中的(b)部分。 在第二次迭代中，只有前面4个对象的指针不是NIL，该次迭代后的结果见图中的(c)部分，在第3次迭代中，只对表中开头2个对象进行操作，最后所有对象的指针均变为NIL，其结果见图中的(d)部分。 在第9行中，对所有非NIL指针next[i]，我们置next[i]← next[next[i]]，它实现的设计思想称为指针转移。注意，由于指针转移操作改变了指针域，因而也就破坏了链表的结构。如果必须保持链表结构，则 我们可以对next指针做备份并使用该备份来计算距离的值。 正确性 List-Rank维持以下不变条件：在第5-9行while循环中每次迭代开始时，对每个对象i，如果对以i作表头的子表的各个d值求和，就得到了从i 到初始表L尾的正确距离。例如，在图2(b)中，对象3作表头的子表是序列<3,6,0>，其d值分别为2,2,和1，它们的和为5，这就是 该对象到初始表尾的距离。上述不变条件成立的原因是当每个对象与其在表中的后继进行“拼接”时，它把其后继的d值加到自身的d值中。 必须注意，为使指针转移算法能正确执行，必须使并行的存储器存取保持同步。每次执行第9行代码可以对数个next指针进行更新。我们要求赋值式右边的存储器读操作（读 next[next[i]]）出现在赋值式左边的任何存储器写操作（写next[i]）之前。 现在让我们看看List-Rank是一个EREW算法的原因。因为每个处理器至多响应一个对象，所以第2-7行的每个读操作和写操作都是互斥的，第8-9行的写操作也是如此。请注意指针转移维持下列不变条件： 对任意两个不同的对象i和j，或者有next[i]≠next[j]，或者有next[i]=next[j]=NIL。对初始表这一条件显然成立，并且通过第9行操作该条件一直保持成立。因为所有非NIL的next值都是不同的，所以第9行中的读操作也是互斤的。 如果所有读操作都是互斥的，我们就无需假设在第8行中执行了某种同步操作。特定地，我们要求所有处理i只能先读d[i]，然后才能读 d[next[i]]。有了这种同步要求，如果一个对象i有next[i]≠NIL，并且有另外一个对象j指向i（即next[j]=i），则第1个读操 作为处理器i取得值d[i]，然后第 2个读操作才能为处理器j取得值d[i]。因此，所以 List-Rank是一种EREW算法。 从现在起，我们忽略有关同步的细节描述并假定PRAM与其伪代码设计环境都以始终如一的同步方式进行操作，所有处理器可同时执行读操作与写操作。 分析 我们现在来证明如果表L中有n个对象，则List-Rank的运行时间为O(lgn)。因为初始化占用的时间为O(1)，并且while循环中的每次迭代所需时间也是O(1)，所以只需证明总共有 「lgn」次迭代操作就可以了。 我们注意到关键是：指针转移的每一步把每个表转化为交错的两个表：一个表由偶数位置上的对象构成，另一个表由奇数位置上的对象构成。因此每个指针转移步使表的数目增加一倍而使其长度减为一半。因此，在「lgn」次迭代结束时，所有的表均包含一个对象。 第5行中的终止条件测试所需时间为O(1)。事实上，只要在循环体内用一个变量记录next[i]≠NIL的i的个数，就可以在O(1)的时间内完成第5行的测试。 除了并行的运行时间外，对于并行算法还存在另一种有趣的性能评价方法。我们定义并行算法执行的工作为其运行时间与所需的处理器数目的积。从直观上看，工作是一个串行RAM模拟并行算法时所执行的计算量。 过程List-Rank执行了O(nlgn)的工作，这是因为它需要n个处理器且其运行时间为O(lgn)。关于表排序问题的简单的串行算法的运行时间为O(n)，这说明List-Rank执行的某些工作并不是必需的，但两者仅差一个对数因子。 已知一个PRAM算法A和求解同一个问题的另一种（串行或并行）算法B，如果A执行的工作不超过B执行的工作乘以一个常数因子，我们就说算法A对于算法 B来说高效。如果算法A对于串行RAM上最好的算法来说是高效的，我们就更简单地称PRAM算法A高效。因为在串行RAM上关于表排序的最好算法的运行时 间为O(n)，所以List-Rank不是高效的算法。

图论算法——有向图的强连通分支

在有向图G中，如果任意两个不同的顶点相互可达，则称该有向图是强连通的。有向图G的极大强连通子图称为G的强连通分支。 把有向图分解为强连通分支是深度优先搜索的一个经典应用实例。下面介绍如何使用两个深度优先搜索过程来进行这种分解，很多有关有向图的算法都从分解步骤 开始，这种分解可把原始的问题分成数个子问题，其中每个子子问题对应一个强连通分支。构造强连通分支之间的联系也就把子问题的解决方法联系在一起，我们可 以用一种称之为分支图的图来表示这种构造。 定义有向图G=(V,E)的分支图为GSCC=(VSCC,ESCC),其中VSCC包含的每一个结点对应于G的每个强连通分支。如果图G的对应于节点u的强连通分支中，某个结点和对应于v的强连通分支中的某个结点之间存在一条有向边，则边(u,v)∈ESCC。图1给出了一个实例。显而易见对于分支图有以下定理： 定理1 有向图G的分支图GSCC是一个有向无回路图。 图1展示了一个有向图的强连通分支的实例。(a)为有向图G，其中的阴影部分是G的强连通分支，对每个顶点都标出了其发现时刻与完成时刻，黑色边为树 枝；(b)G的转置图GT。图中说明了算法Strongly_Connected_Components第3行计算出的深度优先树，其中黑色边是树枝。 每个强连通子图对应于一棵深度优先树。图中黑色顶点b,c,g和h是强连通子图中每个顶点的祖先，这些顶点也是对GT进行深度优先搜索所产生的深度优先树的树根。(c)把G的每个强连通子图缩减为单个顶点后所得到的有向无回路子图（即G的分支图）。 寻找图G=(V,E)的强连通分支的算法中使用了G的转置，其定义为：GT=(V,ET)，其中ET={(v,u)∈V×V:(u,v)∈E}，即ET由G中的边改变方向后组成。若已知图G的邻接表，则建立GT所需时间为O(V+E)。注意到下面的结论是很有趣的：G和GT有着完全相同的强连通支，即在G中u和v互为可达当且仅当在GT中它们互为可达。图1(b)即为图1(a)所示图的转置，其强连通支上涂了阴影。 下列运行时间为θ(V+E)的算法可得出有向图G=(V,E)的强连通分支，该算法使用了两次深度优先搜索，一次在图G上进行，另一次在图GT上进行。 procedure Strongly_Connected_Components(G); begin  1.调用DFS(G)以计算出每个结点u的完成时刻f[u];  2.计算出GT;  3.调用DFS（GT），但在DFS的主循环里按针f[u]递减的顺序考虑各结点（和第一行中一样计算）;  4.输出第3步中产生的深度优先森林中每棵树的结点，作为各自独立的强连通支。 end; 这一貌似简单的算法似乎和强连通支无关。下面我们将揭开这一设计思想的秘密并证明算法的证确性。我们将从两个有用的观察资料入手。 引理1 如果两个结点处于同一强连通支中，那么在它们之间不存在离开该连通支的通路。 证明： 设u和v是处于同一强连通支的两个结点，根据强连通支的定义，从u到v和从v到u皆有通路，设结点w在某一通路u→w→v上，所以从u可达w、又因为存 在通路 v→u，所以可知从w通过路径w→v→u可达u，因此u和w在同一强连通支中。因为w是任意选定的，所以引理得证。（证毕） 定理2 在任何深度优先搜索中，同一强连通支内的所有顶点均在同一棵深度优先树中。 证明： 在强连通支内的所有结点中，设r第一个被发现。因为r是第一个被发现，所以发现r时强连通支内的其他结点都为白色。在强连通支内从r到每一其他结点均有 通路，因为这些通路都没有离开该强连通支（据引理1），所以其上所有结点均为白色。因此根据白色路径定理，在深度优先树中，强连通支内的每一个结点都是结 点r的后裔。（证毕） 在下文中，记号d[u]和f[u]分别指由算法Strongly_Connected_Components第1行的深度优先搜索计算出的发现和完成时刻。类似地，符号u→v是指G中而不是GT中存在的一条通路。 为了证明算法Strongly_Connected_Components的正确性，我们引进符号Φ(u)表示结点u的祖宗w，它是根据算法第1行的深 度优先搜索中最后完成的从u可达的结点（注意，与深度优先树中祖先的概念不同）。换句话说，Φ(u)是满足u→w且f[w]有最大值的结点w。 注意有可能Φ(u)=u，因为u对其自身当然可达，所以有 f[u]≤f[Φ[u]]                      (1) 我们同样可以通过以下推理证明Φ(Φ(u))=Φ(u)，对任意结点u,v∈V， u→v说明f[Φ(v)]≤f[Φ(u)]          (2) 因为{w|v→w}包含于{w|u→w}，且祖宗结点是所有可达结点中具有最大完成时刻的结点。又因为从u可达结点Φ(u)，所以(2)式表明订 f[Φ(Φ(u))]≤f[Φ(u)]，用Φ(u)代入(1)式中的u同样有f[Φ(u)]≤f[Φ(Φ(u))]，这样 f[Φ(Φ(u))]=f[Φ(u)]成立。所以有Φ(Φ(u))=Φ(u)，因为若两结点有同样的完成时刻，则实际上两结点为同一结点。 我们将发现每个强连通分支中都有一结点是其中每一结点的祖宗，该结点称为相应强连通分支的“代表性结点”。在对图G进行的深度优先搜索中，它是强连通支中最先发现且最后完成的结点。在对GT的深度优先搜索中，它是深度优先树的树根，我们现在来证明这一性质。 第一个定理中称Φ(u)是u的祖先结点。 定理3 已知有向图G=(V,E)，在对G的深度优先搜索中，对任意结点u∈V,其祖宗Φ(u)是u的祖先。 证明： 如果Φ(u)=u，定理自然成立。如果Φ(u)≠u，我们来考虑在时刻d[u]各结点的颜色，若Φ(u)是黑色，则f[Φ(u)] 1. 若每一中间结点均为白色，那么由白色路径定理知Φ(u)是u的后裔，则有f[Φ(u)] 2. 若有某个中间结点不是白色，设t是从u到Φ(u)的通路上最后一个非非白节点，则由于不可能有从黑色结点到白色结点的边存在，所以t必是灰色。这 样就存在一条从t到Φ(u)且由白色结点组成的通路，因此根据白色路径定理可推知Φ(u)是t的后裔，这表明f[t]>f[Φ(u)]成立，但从u 到t有通路，这巧我们对Φ(u)的选择相矛盾。（证毕） 推论1 在对有向图G=(V,E)的任何深度优先搜索中，对所有u∈V，结点u和Φ(u)处于同一个强连通分支内。 证明： 由对祖宗的定义有u→Φ(u)，同时因为Φ(u)是u的祖先，所以又有Φ(u)→u。（证毕） 下面的定理给出了一个关于祖宗和强连通分支之间联系的更强有力的结论。 定理4 在有向图G=(V,E)中，两个结点u,v∈V处于同一强连通分支当且仅当对G进行深度优先搜索时两结点具有同一祖宗。 证明： →：假设u和v处于同一强连通分支内，从u可达的每个结点也满足从v可达，反之亦然。这是由于在 u和 v之间存在双向通路，由祖宗的定义我们可以推知Φ(u)=Φ(v)。 ←：假设Φ(u)=Φ(v)成立，根据推论1，u和Φ(u)在同一强连通分支内且v和Φ(v)也处于同一强连通分支内，因此u和v也在同一强连通支中。（证毕） 有了定理4，算法Strongly_Connected_Components的结构就容易掌握了。强连通分支就是有着同一组总的节点的集合。再根据定理3和括号定理可知，在算法第1行所述的深度优先搜索中，祖宗是其所在强连通分支中第一个发现最后一个完成的结点。 为了弄清楚为什么在算法Strongly_Connected_Components的第3行要对GT进行深度优先搜索，我们考察算法的第1行的深度优 先搜索所计算出的具有最大完成时刻的结点r。根据祖宗的定义可知结点r必为一祖宗结点，这是因为它是自身的祖宗：它可以到达自身且图中其他结点的完成时刻 均小于它。在r的强连通分支中还有其他哪些节点？它们是那些以F为祖宗的结点——指可达r但不可达任何完成时刻大于f[r]的结点的那些结点。 但由于在G中r是完成时刻最大的结点，所以r的强连通分支仅由那些可达r的结点组成。换句话说，r的强连通支由那些在GT中从r可达的顶点组成。在算法第3行的深度优先搜索识别出所有属于r强连通支的结点，并把它们置为黑色（宽度优先搜索或任何对可达结点的搜索可以同样容易地做到这一点）。 在执行完第3行的深度优先搜索并识别出r的强连通分支以后，算法又从不属于r强连通分支且有着最大完成时刻的任何结点r'重新开始搜索。结点，r'必为其自身的祖宗，因为由它不可能达到任何完成时刻大于它的其他结点（否则r'将包含于r的强连通分支中）。 根据类似的推理，可达r'且不为黑色的任何结点必属于r'的强连通分支，因而在第3行的深度优先搜索继续进行时，通过在GT中从r'开始搜索可以识别出属于r'的强连通分支的每个结点并将其置为黑色。 因此通过第3行的深度优先搜索可以对图“层层剥皮”，逐个取得图的强连通分支。把每个强连通分支的祖宗作为自变量调用DFS_Visit过程，我们就可 在过程DFS的第7行识别出每一支。DFS_Visit过程中的递归调用最终使支内每个结点都成为黑色。当DFS_Visit返回到DFS中时，整个支的 结点都变成黑色且被“剥离”，接着DFS在那些非黑色结点中寻找具有最大完成时刻的结点并把该结点作为另一支的祖宗继续上述过程。 下面的定理形式化了以上的论证。 定理5 过程Strongly_Connected_Components(G)可正确计算出有向图G的强连通分支。 证明： 通过对在GT上 进行深度优先搜索中发现的深度优先树的数目进行归纳，可以证明每棵树中的结点都形成一强连通分支。归纳论证的每一步骤都证明对GT进行深度优先搜索形成的 树是一强连通分支，假定所有在先生成的树都是强连通分支。归纳的基础是显而易见的，这是因为产生第一棵树之前无其他树，因而假设自然成立。 考察对GT进行深度优先搜索所产生的根为r的一棵深度优先树T，设C(r)表示r为祖宗的所有结点的集合： C(r)={v∈V|Φ(v)=r} 现往我们来证明结点u被放在树T中当且仅当u∈C(r)。 →：由定理2可知C(r)中的每一个结点都终止于同一棵深度优先树。因为r∈C(r)且r是T的根，所以C(r)中的每个元素皆终止于T。 ←：通过对两种情形f[Φ(w)]>f[r]或f[Φ(w)]f[r]的任何结点w不在树T中，这是由于在选择到r时，w已经被放在根为Φ(w)的树中。 满足f[Φ(w)]<f[r]的任意结点w也不可能在树T中，这是因为若w被放入T中，则有w→r：因此根据式(2)和性质r=Φ(r)，可得 f[Φ(w)]≥f[Φ(r)]=f[r]，这和f[Φ(w)]<f[r]相矛盾。这样树T仅包含那些满足Φ(u)=r的结点u，即T实际上就是强 连通支C(r)，这样就完成了归纳证明。（证毕）

图论算法——拓扑排序

有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)， 则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列）。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的 有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。 有向无回路图经常用于说明事件发生的先后次序，图1给出一个实例说明早晨穿衣的过程。必须先穿某一衣物才能再穿其他衣物（如先穿袜子后穿鞋），也有一些衣物可以按任意次序穿戴（如袜子和短裤）。 图1 早晨穿衣的过程 图1(a)所示的图中的有向边(u,v)表明衣服u必须先于衣服v穿戴。因此该图的拓扑排序给出了一个穿衣的顺序。每个顶点旁标的是发现时刻与完成时刻。图1(b)说明对该图进行拓扑排序后将沿水平线方向形成一个顶点序列，使得图中所有有向边均从左指向右。 下列简单算法可以对一个有向无回路图进行拓扑排序。 procedure Topological_Sort(G); begin  1.调用DFS(G)计算每个顶点的完成时间f[v];  2.当每个顶点完成后，把它插入链表前端;  3.返回由顶点组成的链表; end; 图1(b)说明经拓扑排序的结点以与其完成时刻相反的顺序出现。因为深度优先搜索的运行时间为θ(V+E)，每一个v中结点插入链表需占用的时间为θ(1)，因此进行拓扑排序的运行时间θ(V+E)。 为了证明算法的正确性，我们运用了下面有关有向无回路图的重要引理。 引理1 有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边。 证明： →：假设有一条反向边(u,v)，那么在深度优先森林中结点v必为结点u的祖先，因此G中从v到u必存在一通路，这一通路和边(u,v)构成一个回路。 ←：假设G中包含一回路C，我们证明对G的深度优先搜索将产生一条反向边。设v是回路C中第一个被发现的结点且边(u,v)是C中的优先边，在时刻 d[v]从v到u存在一条由白色结点组成的通路，根据白色路径定理可知在深度优先森林中结点u必是结点v的后裔，因而(u,v)是一条反向边。（证毕） 定理1 Topological_Sort(G)算法可产生有向无回路图G的拓扑排序。 证明： 假设对一已知有问无回路图G=(V,E)运行过程DFS以确定其结点的完成时刻。那么只要证明对任一对不同结点u,v∈V，若G中存在一条从u到v的有向边，则f[v] 因此，v必定是白色或黑色结点。若v是白色，它就成为u的后裔，因此f[v] 另一种拓扑排序的算法基于以下思想：首先选择一个无前驱的顶点（即入度为0的顶点，图中至少应有一个这样的顶点，否则肯定存在回路），然后从图中移去该 顶点以及由他发出的所有有向边，如果图中还存在无前驱的顶点，则重复上述操作，直到操作无法进行。如果图不为空，说明图中存在回路，无法进行拓扑排序；否 则移出的顶点的顺序就是对该图的一个拓扑排序。 下面是该算法的具体实现： procedure Topological_Sort_II(G); begin  1  for 每个顶点u∈V[G] do d[u]←0;  //初始化d[u],d[u]用来记录顶点u的入度 2  for 每个顶点u∈V[G] do 3    for 每个顶点v∈Adj[u] do d[v]←d[v]+1;  //统计每个顶点的入度 4  CreateStack(s);  //建立一个堆栈s 5  for 每个顶点u∈V[G] do  6    if d[u]=0 then push(u,s);  //将度为0的顶点压入堆栈 7  count←0; 8  while (not Empty(s)) do      begin 9      u←top(s);  //取出栈顶元素 10     pop(s);     //弹出一个栈顶元素 11     count←count+1; 12     R[count]←u;   //线性表R用来记录拓扑排序的结果 13     for 每个顶点v∈Adj[u] do //对于每个和u相邻的节点v       begin 14     d[v]←d[v]-1; 15     if d[v]=0 then push(v,s);  //如果出现入度为0的顶点将其压入栈    end;              end; 16 if count<>G.size then writeln('Error! The graph has cycle.') 17                  else 按次序输出R; end; 上面的算法中利用d[u]来记录顶点u的入度，第2-3行用来统计所有顶点的入度，第5-6行将入度为0的顶点压入堆栈，第8-15行不断地从栈顶取出 顶点，将该顶点输出到拓扑序列中，并将所有与该顶点相邻的顶点的入度减1，如果某个顶点的入度减至0，则压入堆栈，重复该过程直到堆栈空了为止。显而易见 该算法的复杂度为O(VE)，因为第2-3行的复杂性就是O(VE)，后面8-15行的复杂性也是O(VE)。这个算法虽然简单，但是没有前面一个算法的 效率高。

并行算法

随着并行处理硬件性能的迅速提高，人们对并行算法的兴趣也日益增加。所谓并行算法是指一次可执行多个操作的算法。对并行算法 的研究现在已发展为一个独立的研究领域。很多用串行算法解决的问题也已经有了相应的并行算法。在本文中，我们将阐述一些简单的并行算法以说明一些基本概念 和技术。 这里介绍的并行算法将用一种流行的理论模型即并行随机存取计算机(PRAM)来描述。很多关于数组、表、树和图的并行算法都 可以很容易地用PRAM模型来描述。如果一个PRAM算法在性能上超过另一个PRAM算法，则当两个算法在一台实际的并行计算机上运行时其相对性能不会有 很大变化。 PRAM模型 图1说明了PRAM的基本结构。其中有n个普通的串行处理器p0,p1,...,pn-1共享一个全局存储器。所有处理器都可以“并行地”（同时）从全局存储器读出信息或向全局存储器写入信息。各处理器也可以并行地执行各种算术和逻辑操作。 图l PRAM的基本构造 在PRAM模型中关于算法性能的最关键的一点是：假设运行时间可以用算法执行的并行的存储器存取次数来衡量。这一假设是对普通的RAM模型的直接推 广，并且用存储器存取次数来衡量运行时间对PRAM模型也是很适合的。这一简单的假设对于我们研究并行算法有很大帮助，不过真正的并行计算机并不能做到在 单位时间内对全局存储器并行地执行存取操作：对存储器进行存取操作所需的时间随着并行计算机中处理器数目的增加而相应增加。 然而，对于以任意方式对数据进行存取的并行计算机来说，可以证明存取操作为单位时间的假设是成立的。实际中的并行计算机都包含一个通讯网络以便支持一个抽象的全局存储器。与算术操作等其他操作相比，通过网络存取数据是相当慢的。 因此，计算出两种并行算法所执行的并行的存储器存取次数就可以对其相对性能作出精确的估计。实际的计算机与 PRAM的单位时间抽象不一致，主要在于某种存储器存取模式可能比其他模式快。但是，作为一种近似描述，PRAM模型的单位时间存取的假设还是合乎情理的。 并行算法的运行时间既依赖于执行算法的处理器数目，也依赖于输入问题本身的规模。一般来说，在分析PRAM算法时我们必须同时讨论其时间和处理器数目， 这与串行算法完全不同，在串行算法中我们主要集中于对时间的分析。当然，我们在算法使用的处理器数目与其运行时间之间要进行权衡。 并发存储器存取方式与互斥存储器存取方式 并发读算法是指在算法执行过程中多处理器可以同时对共享存储器的同一位置进行读操作的一种PRAM算法。互斥读算法是指在算法执行中任何两个处理器都不能同时对共享存储器的同一位置进行读操作的一种PRAM算法。 类似地，我们根据多处理器能否在同一时刻对共享存储器的同一位置执行写操作也可以把PRAM算法划分为并发写算法和互斥写算法。我们所遇到的算法类型一般采用以下缩写形式： ·EREW：互斥读且互斥写； ·CREW：并发读且互斥写； ·ERCW：互斥读且并发写； ·CRCW：并发读且并发写。 在这些算法类型中，最常见的是EREW和CRCW。仅支持EREW算法的PRAM称为EREW PRAM，仅支持CRCW算法的PRAM称为CRCW PRAM。一个CRCW PRAM当然能够执行EREW算法，但EREW PRAM不能直接支持CRCW算法所要求的并发存储器存取操作。 EREW PRAM的底层硬件相对来说比较简单，并且因为它无需对相互冲突的存储器读写操作进行处理，因此运行速度也比较快。如果单位时间假设能相当精确地衡量算法 的性能，则CRCW PRAM就需要更多的硬件支持，但可以证明它能够提供一种比EREW PRAM更直接的操作设计模型。 在剩下的 两种算法类型CREW和ERCW中，有关的论文书籍更重视CREW。但是从实际应用的角度来看，要支持并发写操作并不比支持并发读操作更困难，在本文中， 如果算法包含并发读或并发写操作，我们一般就把它作为CREW而不再进行细分。我们将在第2节中更详细地讨论这一区分方法。 在 CREW算法中当多处理器对同一存储器位置进行写操作时，如果我们不作详细论述，并行写的结果就没有完备的定义。在本文中，我们使用公用CREW模型：当 多个处理器对存储器的同一位置进行写操作时，它们写入的必须是公用值(相同的值)。在处理这个问题的有关文献中，在与上述不同的假设前提下存在着几种可选 择的PRAM类型，包括： ·任意型：实际存储的是写入的这些值中的一个任意值； ·优先级型：存储的是具有最高优先级的处理器所写入的值； ·组合型：实际存储的值是写入值的某个特定组合。 在最后一种情况中，特定组合是指满足结合律的某种函数，如加法（存储写入值的和）或最大值函数（仅存储写入值中的最大值）。 同步与控制 PRAM算法必须高度同步以保证其正确执行。如何获得这一同步特征？另外，PRAM算法中的处理器常常必须测试循环的终止条件，而这一终止条件又往往取 决于所有处理器的状态。如何实现这种控制功能？许多并行计算机采用了一种连接各处理器的控制网络，以帮助实现同步和对终止条件进行测试。在特定情况下，控 制网络实现这些功能的速度可以与路径选择网络实现对全局存储语句的速度一样快。 为方便起见，我们假设各个处理器固有严格同步的特征。所有处理器同时执行相同的语句。处理器执行代码的进度也保持一致。当我们学习第一个并行算法时，我们将指出在何处我们需要假设处理器是同步执行的。 为了能对依赖于所有处理器状态的并行循环终止条件进行测试，我们假定控制网络能够在O(1)的运行时间内对并行的终止条件进行测试。在一些文件中的EREW PRAM模型没有作这一假设，并且测试循环终止条件所需的（对数）时间必定包含在整个运行时间内。

线性时间排序算法——基数排序（Radix Sort）

基数排序是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化" 以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放12个盒子里。这样，操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个 位置穿孔的其次，等等。 对十进制数字来说，每列中只用到10个位置(另两个位置用于编码非数值字符)。一个d位数占用d个列。因为卡片排序器一次只能查看一个列，要对n张片上的d位数进行排序就要有个排序算法。 直感上，大家可能觉得应该按最重要的一位排序，然后对每个盒子中的数递归地排序，最后把结果合并起来。不幸的是，为排序每一个盒子中的数，10个盒子中的9个必须先放在一边，这个过程产生了许多要加以记录的中间卡片堆。 与人们的直感相反，基数排序是首先按最不重要的一位数字排序来解决卡片排序问题的。同样，把各堆卡片收集成一迭，其中0号盒子中的在1号盒子中的前面，后者又在2号盒子中的前面，等等。然后对整个一迭卡片按次重要位排序，并把结果同样地合并起来。 重复这个过程，直到对所有的d位数字都进行了排序。所以，仅需要n遍就可将一迭卡片排好序。图1说明了基数排序作“一迭”7个三位数的过程。第一列为输入，其余各列示出了对各个数位进行逐次排序后表的情形。垂直向上的箭头指示了当前要被加以排序的数位。 图1 基数排序作用于一个由7个3位数组成的表上的过程 关于这个算法很重要的一点就是按位排序要稳定。由卡片排序器所故的排序是稳定的，但操作员在把卡片从盒子里拿出来时不能改变他们的次序，即使某一盒子中所有卡片在给定列上的穿孔位置都相同。 在一台典型的顺序随机存取计算机上，有时采用基数排序来对有多重域关键字的记录进行排序。例如，假设我们想根据三个关键字处、月和日来对日期排序。对这 个问题，可以用带有比较函数的排序算法来做。给定两个日期，先比较年份，如果相同，再比较月份，如果再相同，再比较日。这儿我们可以采用另一个方法，即用 一种稳定的排序方法对所给信息进行三次排序：先对日，其次对月，再对年。 基数排序的代码是很简单的、下面的过程假设长度为n的数组A中的每个元素都有d位数字，其中第1位是最低的，第d位是最高位。 procedure Radix_Sort(var L:List;d:integer); var i:integer; begin 1  for i:=1 to d do 2     使用一种稳定的排序方法来对数组L按数字i进行排序; end; 基数排序的正确性可以通过对正在被排序的列进行归纳而加以证明。对本算法时间代价的分析要取决于选择哪种稳定的中间排序算法。当每位数字都界于l到k之 间，且k不太大时，可以选择计数排序。对n个d位数的每一遍处理的时间为O(n+k)，共有d遍，故基数排序的总时间为θ(dn+kd)。当d为常 数，k=O(n)时，基数排序有线性运行时间。 某些计算机科学家倾向于把一个计算机字中所含位数看成是θ(lgn)。具体一点说，假 设共有dlgn位数字，d为正常数。这样，如果待排序的每个数恰能容于一个计算机字内，我们就可以把它视为一个以n为基数的d位数。看一个例子：对一百万 个64位数排序。通过把这些数当作是以216为基数的四位数，用基数排序四遍就可完成排序。 这与一个典型的O(nlgn)比较排序相 比要好得多，后者对每一个参加排序的数约要lgn=20次操作。但有一点不理想，即采用计数排序作为中间稳定排序算法的基数排序版本不能够进行原地置换排 序，而很多O(nlgn)比较排序算法却是可以的。因此，当内存比较紧张时，一般来说选择快速排序更合适些。

线性时间排序算法——计数排序（Counting Sort）

计数排序是一个非基于比较的线性时间排序算法。它对输入的数据有附加的限制条件，在这两个条件下，计数排序的复杂性为O(n)。 1. 输入的线性表的元素属于有限偏序集S； 2. 设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。 计数排序算法的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出 序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值 时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。 假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序算法可以描述如下： 1. 扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)； 2. 扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。 具体的实现如下。 注意：在以下的讨论中，为了方便，我们假设线性表是用数组来实现的，并且假设线性表的元素类型TElement为整型，其值在1..k之间，线性表的长度为n，且k=O(n)。这些假设对计数排序算法没有实质的影响，但是可以使以下介绍的算法看起来容易理解。 在下面的计数排序算法中，我们假设L为输入的长度为n的线性表，输出的排序结果存放在线性表R中。算法中还用到一个辅助表tmp用于对输入元素进行计数。 Type TElement=1..k; TList=array [1..maxlength] of TElement; TPosition=integer; procedure Counting_Sort(var L,R:TList); var i,j:integer; tmp:TList; begin 1 for i:=1 to k do tmp[i]:=0; 2 for j:=1 to n do inc(tmp[L[j]]);    //执行完上面的循环后，tmp[i]的值是L中等于i的元素的个数 3 for i:=2 to k do tmp[i]:=tmp[i]+tmp[i-1];    //执行完上面的循环后，tmp[i]的值是L中小于等于i的元素的个数 4 for j:=n downto 1 do  //注意这里的downto保证了排序的稳定性    begin 5   R[tmp[L[j]]]:=L[j];//L[j]存放在输出数组R的第tmp[L[j]]个位置上 6   dec(tmp[L[j]]); //tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的个数    end; end; 图1所示的是Counting_Sort作用于一个输入数组L[1..8]上的过程，其中L的每一个元素都是不大于k=6的正整数。 　　图1 计数排序算法演示 容易理解，算法的第(l)行是对数组 tmp初始化。第(2)行检查每个输入元素。如果输入元素的键值为i，则tmp[i]增1。因此，在第(2)行执行结束后，tmp[i]中存放着值等于i 的输入元素个数，i=1,2,..,k。算法的第(3)行，对每个i=1,2,..,i，统计值小于或等于i的输入元素个数。最后在(4)-(8)行中， 将每个元素L[j]存放到输出数组R中相应的最终位置上。 如果所有n个元素的值都不相同，则共有tmp[L[j]]个元素的键值小于 或等于L[j]，而小于L[j]的元素有tmp[L[j]]-1个，因此tmp[L[j]]就是L[j]在输出数组R中的正确位置。当输入元素有相同的值 时，每将一个L[j]存放到数组R时，tmp[L[j]]就减1，使下个值等于L[j]的元素存放在输出数组R中存放元素L[j]的前一个位置上。 计数排序算法的计算时间复杂性很容易分析。其中，第(1)行需要O(k)时间；第(2)行需要O(n)时间，第(3)行需要O(k)时间；第 (4)-(8)行的for循环需要O(n)时间。这样，整个算法所需的计算间为O(n+k)。当k=O(n)时，算法的计算时间复杂性为O(n)。 我们看到，计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而 它的计算时间下界不再是Ω(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。 如果k=n2,n3,..，就得不到线性时间的上界。 此外，我们还看到，由于算法第4行使用了downto语句，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，换句话说，计数排序算法是一个稳定的排序算法，但显然不是原地置换排序算法。

比较排序算法——插入排序（Insertion Sort）

插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的 适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个 位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。 图1 对4个元素进行插入排序 在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。所以，我们设元素的类型 ElementType中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定L[i]是否向前移动之前检查当前位置是 否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将L[i]放入L[0]中，这样也可以保证在适当的时候结束第i 遍处理。下面的算法中将对当前位置进行判断。 插入排序算法如下： procedure Selection_Sort(var L:List); var i,j:position; v:ElementType; begin 1 for i:=First(L)+1 to Last(L) do     begin 2     v:=L[i]; 3     j:=i; 4     while (j<>First(L))and(L[j-1]< v) do  //循环找到插入点         begin 5         L[j]:=L[j-1];  //移动元素 6         j:=j-1;         end; 7     L[j]:=v;  //插入元素     end; end; 下面考虑算法Insertion_Sort的复杂性。对于确定的i，内while循环的次数为O(i)，所以整个循环体内执行了∑O(i)=O(∑i)，其中i从2到n。即比较次数为O(n2)。如果输入序列是从大到小排列的，那么内while循环次数为i-1次，所以整个循环体执行了∑(i-1)=n(n-1)/2次。由此可知，最坏情况下，Insertion_Sort要比较Ω(n2)次。 如果元素类型是一个很大的纪录，则算法第5行要消耗大量的时间，因此有必要分析移动元素的次数。经过分析可知，平均情况下第5行要执行n(n-1)/4 次，分析方法与冒泡排序的分析相同。如果移动元素要消耗大量的时间，则可以用链表来实现线性表，这样Insertion_Sort可以改写如下（当然前一 个算法同样也适用于链表，只不过没下面这个好，但是下面算法这个比较复杂）： 注意：在下面的算法中链表L增加了一个哨兵单元，其中的元素为-∞，即线性表L的第一个元素是L^.next^ procedure Selection_Sort_II(var L:PList); var i,j,tmp:Position; begin 1  if L^.next=nil then exit; //如果链表L为空则直接退出 2  i:=L^.next;  //i指向L的第一个元素，注意，L有一个哨兵元素，因此L^.next^才是L的第一个元素 3  while i^.next<>nil do      begin 4      tmp:=i^.next;  //tmp指向L[i]的下一个位置 5      j:=L; 6      while (j<>i)and(tmp^.data>=j^.next^.data) do //从前向后找到tmp的位置，tmp应该插在j后面 7      j:=j^.next; 8      if j<>i then  //j=i说明不需要改变tmp的位置          begin    9          i^.next:=tmp^.next;  //将tmp从i后面摘除 10         tmp^.next:=j^.next;  //在j后面插入tmp 11         j^.next:=tmp;          end 12     else i:=i^.next;  //否则i指向下一个元素     end; end; 上述改进算法主要是利用链表删除和插入元素方便的特性，对于数组则不适用。 插入排序法是一个原地置换排序法，也是一个稳定排序法。插入法虽然在最坏情况下复杂性为θ(n2)，但是对于小规模输入来说，插入排序法是一个快速的原地置换排序法。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序和桶排序。

比较排序算法——选择排序（Selection Sort）

选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。 选择排序算法可实现如下： procedure Selection_Sort(var L:List); var i,j,s:position; begin 1  for i:=First(L) to Last(L)-1 do     begin 2   s:=i; 3   for j:=i+1 to Last(L) do 4     if L[j]< L[s] then 5     s:=j;             //记录L[i..n]中最小元素的位置 6   swap(L[i],L[s]);       //交换L[i],L[s]  end;  end; 算法Selection_Sort中里面的一个for循环需要进行n-i次比较，所以整个算法需要 次比较。 显而易见，算法Selection_Sort中共调用了n-1次swap过程。选择排序法是一个原地置换排序法，也是稳定排序法。

比较排序算法——冒泡排序（Bubble Sort）

最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而 要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正 确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。 显然，处理一遍之后，“最轻”的元素就浮到了最高位 置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不 必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。这个算法可实现如下。 procedure Bubble_Sort(var L:List); var i,j:position; begin 1 for i:=First(L) to Last(L)-1 do 2  for j:=First(L) to Last(L)-i do 3     if L[j]>L[j+1] then 4           swap(L[j],L[j+1]);   //交换L[j]和L[j+1] end; 上述算法将较大的元素看作较重的气泡，每次最大的元素沉到表尾。其中First(L)和Last(L)分别表示线性表L的第一个元素和最后一个元素的位 置，swap(x,y)交换变量x,y的值。上述算法简单地将线性表的位置当作整数用for循环来处理，但实际上线性表可能用链表实现；而且上述算法将线 性表元素的值当作其键值进行处理。不过这些并不影响表达该算法的基本思想。今后如果不加说明，所有的算法都用这种简化方式表达。 容易看出该算法总共进行了n(n-1)/2次比较。如果swap过程消耗的时间不多的话，主要时间消耗在比较上，因而时间复杂性为O(n2)。但是如果元素类型是一个很大的纪录，则Swap过程要消耗大量的时间，因此有必要分析swap执行的次数。 显然算法Bubble_Sort在最坏情况下调用n(n-1)/2次Swap过程。我们假设输入序列的分布是等可能的。考虑互逆的两个输入序列L1=k1,k2,..,kn和L2=kn,kn-1,..,k1。我们知道，如果ki>kj，且ki在表中排在kj前面，则在冒泡法排序时必定要将kj换到ki前面，即kj向前浮的过程中一定要穿过一次ki，这个过程要调用一次Swap。 对于任意的两个元素ki和kj，不妨设ki>kj，或者在L1中ki排在kj前面，或者L2在中ki排在kj前面，两者必居其一。因此对于任意的两个元素ki和kj，在对L1和L2排序时，总共需要将这两个元素对调一次。n个元素中任取两个元素有Cn2 种取法，因此对于两个互逆序列进行排序，总共要调用Cn2 =n(n-1)/2次Swap，平均每个序列要调用n(n-1)/4次Swap。那么算法Bubble_Sort调用Swap的平均次数为n(n-1)/4。 可以对冒泡算法作一些改进，如果算法第二行的某次内循环没有进行元素交换，则说明排序工作已经完成，可以退出外循环。可以用一个布尔变量来记录内循环是否进行了记录交换，如果没有则终止外循环。 冒泡法的另一个改进版本是双向扫描冒泡法（Bi-Directional Bubble Sort）。设被排序的表中各元素键值序列为： 483 67 888 50 255 406 134 592 657 745 683 对该序列进行3次扫描后会发现，第3此扫描中最后一次交换的一对纪录是L[4]和L[5]： 50 67 255 134 | 406 483 592 657 683 745 888 显然，第3次扫描(i=3)结束后L[5]以后的序列都已经排好序了，所以下一次扫描不必到达Last(L)-i=11-4=7，即第2行的for 循环j不必到达7，只要到达4-1=3就可以了。按照这种思路，可以来回地进行扫描，即先从头扫到尾，再从尾扫到头。这样就得到双向冒泡排序算法： procedure Bi-Directional_Bubble_Sort(var L:List); var low,up,t,i:position; begin 1  low:=First(L);up:=Last(L); 2  while up>low do     begin 3     t:=low; 4     for i:=low to up-1 do 5       if L[i]>L[i+1] then           begin 6           swap(L[i],L[i+1]); 7           t:=i;           end; 8     up:=t; 9     for i:=up downto low+1 do 10      if L[i]< L[i-1] then           begin 11          swap(L[i],L[i-1]); 12          t:=i;           end; 13    low:=t;       end; end; 算法利用两个变量low和up记录排序的区域L[low..up]，用变量t 记录最近一次交换纪录的位置，4-7行从前向后扫描，9-12行从后向前扫描，每次扫描以后利用t所记录的最后一次交换记录的位置，并不断地缩小需要排序的区间，直到该区间只剩下一个元素。 直观上来看，双向冒泡法先让重的气泡沉到底下，然后让轻的气泡浮上来，然后再让较大气泡沉下去，让较轻气泡浮上来，依次反复，直到排序结束。冒泡排序法 和双向冒泡排序法是原地置换排序法，也是稳定排序法，如果算法Bubble_Sort中第3行的比较条件L[j]>L[j+1]改为 L[j]>= L[j+1]，则不再是稳定排序法。

排序问题的计算复杂性

对排序算法计算时间的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间（如，当键是较长的字符串时），常以键比较次数作为排序算法计算时间复杂性的度量。 当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比 较的次数作为复杂性的度量。为了对有n个元素的线性表进行排序，至少必须扫描线性表一遍以获取这n个元素的信息，因此排序问题的计算复杂性下界为 Ω(n)。 如果我们对输入的数据不做任何要求，我们所能获得的唯一信息就是各个元素的具体的值，我们仅能通过比较来确定输入序列的元素间次序。即给定两个元素ai和aj，通过测试aiaj中的哪一个成立来确定ai和aj间的相对次序。这样的排序算法称为比较排序算法。下面我们讨论一下比较排序算法在最坏情况下至少需要多少次比较，即比较排序算法的最坏情况复杂性下界。 我们假设每次比较只测试ai≤aj，如果ai≤aj成立则ai排在aj前面，否则ai排在aj后面。任何一个比较排序算法可以描述为一串比较序列： (ai,aj),(ak,al),..,(am,an),... 表示我们首先比较(ai,aj)，然后比较(ak,al)，...，比较(am,an)，...，直到我们获取了足够的信息可以确定所有元素的顺序。显而易见，如果我们对所有的元素两两进行一次比较的话（总共比较了Cn2次），就一定可以确定所有元素的顺序。但是，如果我们运气足够好的话，我们可能不必对所有元素两两进行一次比较。 比如说对于有三个元素a1,a2,a3的线性表进行排序，如果我们先比较a1和a2，得到a1≤a2；然后比较a2和a3，得到a2≤a3；则不必比较a1和a3，因为根据偏序集的传递性，必有a1≤a3；但是如果a2≥a3，我们还必须比较a1和a3才能确定a1和a3的相对位置。如果我们适当的安排比较的次序的话，也可以减少比较的次数。这样我们可以用一棵二叉树表示比较的顺序，如下图所示： 该树的每一个非叶节点表示一次比较，每一根树枝表示一种比较结果，每一个叶节点表示一种排列顺序。这样的一棵二叉树叫做决策树，它用树枝表示了每次决策做出的选择。如此我们可以将任何一个比较排序算法用一棵决策树来表示。 请注意上图只表明了对三个元素的一种比较算法，这种比较算法依次比较(a1,a2)(a2,a3)(a1,a3)，一旦中间某步得到足够的信息就可以停止比较，但是当算法执行完后（三次比较后），一定可以确定三个元素间的次序。因此我们有理由将算法在最坏情况下的比较次数作为算法复杂性的度量，对于本例该算法在最坏情况下要进行C32=3次比较。 显然，一棵决策树中最高叶节点的高度就是该决策树对应的算法在最坏情况下所需的比较次数，而决策树中最低叶节点的高度就是该决策树对应的算法在最好情况 下所需的比较次数。我们的问题就变为：对于任意一棵决策树（任意一种比较排序算法），它的最高的树叶的高度是多少？这个高度就对应于比较排序算法所需的最 多比较次数（在运气最坏的情况下）；换句话说，对于任何一个输入，该算法至少需要比较多少次就可以对元素进行排序。 我们发现，决策树的每个叶节点对应一个n个元素的排列，其中可能有重复的；但是由于决策树表明了所有可能遇到的情况，因而n个元素的所有排列都在决策树中出现过。n个元素共有n!种排列，即决策树的叶节点数目至少为n!。 又因为一棵高度为h的二叉树（指二叉树的最高树叶高度为h）的叶节点数目最多为2h个（这时正好是满二叉树，即每个非叶节点都有两个子节点），因此n!≤2h，得到h≥log(n!)，其中log以2为底。根据Stirling公式有n!>(n/e)n，于是h>nlogn-nloge，即h=Ω(nlogn)。这样我们就证明了对于任意一种利用比较来确定元素间相对位置的排序算法，其最坏情况下复杂性为Ω(nlogn)。 在下文中我们将讨论几种比较排序算法，其中快速排序在平均情况下复杂性为O(nlogn)，最坏情况下复杂性为O(n2)；堆排序和合并排序在最坏情况下复杂性为O(nlogn)，因此堆排序和合并排序是渐进最优的比较排序算法。 排序算法是否还能够改进呢？从前文我们知道，如果要改进排序算法的效率，就不能只利用比较来确定元素间相对位置。因此我们还需要知道元素的其他附加信 息，光知道元素的大小信息是不够的。下文中我们介绍的计数排序，基数排序和桶排序是具有线性时间复杂性的排序算法，这些算法无一例外地对输入数据作了某些 附加限制，从而增加已知的信息，因此可以不通过比较来确定元素间的相对位置。

排序算法（Sorting）

排序算法（Sorting）

作者：未知    文章来源：算法与数据结构

排序问题的输入是一个线性表，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继。 设R为非空集合A上的二元关系，如果R满足自反性（对于每一个x∈A，(x,x)∈R），反对称性（(x,y)∈R∧(y,x)∈R→x=y）和传递性（(x,y)∈R∧(y,x)∈R→(x,z)∈R），则称R为A上的偏序关系，记作≤。如果(x,y)∈R，则记作x≤y，读作“x小于等于y”。存在偏序关系的集合A称为偏序集。 注意，这里的≤不是指数的大小，而是指在偏序关系中的顺序性。x≤y的含义是：按照这个序，x排在y前面。根据不同的偏序定义，≤有不同的解释。例如整 除关系是偏序关系≤，3≤6的含义是3整除6。大于或等于关系也是偏序关系，针对这个关系5≤4是指在大于或等于关系中5排在4的前面，也就是说5比4 大。 在实际应用中，经常遇到的偏序关系是定义在一个记录类型的数据集合上的。在该记录类型中有一个主键域key，key域的类型是某一个偏序集，记录的其他域称为卫星数据。比较线性表中的两个元素Li和Lj的大小，实际上是比较Li.key和Lj.key的大小（这种比较当然也是偏序集中的比较）。 举例而言，某公司的数据库里记录了员工的数据，每一项纪录包括姓名，编号，年龄，工资等几个域，如果以编号为key域对员工记录排序，则是将员工记录按 照编号排序；如果以工资为key域对员工记录排序，则是将员工记录按照工资高低排序；如果以姓名为key域对员工记录排序，则是以员工姓名的汉语拼音按照 字典顺序排序。 关于偏序集的具体概念和应用，请参见离散数学的相关资料。 如果一个排序算法利用输入的线性表在原地重排其中元素，而没有额外的内存开销，这种排序算法叫做原地置换排序算法（in place sort）；如果排序后并不改变表中相同的元素原来的相对位置，那么这种排序算法叫做稳定排序算法（stable sort）。 排序问题一般分为内排序（internal sorting）和外排序（external sorting）两类： 1. 内排序：待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中； 2. 外排序：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存。