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

在有向图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过程。选择排序法是一个原地置换排序法，也是稳定排序法。