计算机算法基础2

算法：求解问题的一组规则

检索问题\/分治策略

排序问题发现।贪心策略

路径问题规则的设计＜一设也略动态规划

最优化问题〃指导

n1|检索与周游

遍历问题,、回溯与分支限界

形成算法产生算法设计的指

导思想和基本规律

第二章分治法(DivideandConquer)

——“分”而治之

2.1一般方法

■如何求解规模较大问题？

分析问题的特征，寻找合适的解决问题的方法

何谓规模较大？相对而言

■利用分治法求解大规模问题

一种“大事化小”，“从小事做起”的解决问题的策略

最常用的算法设计策略之一

.分治策略基本思想逐步细化的过程

1，子问题二厂子问题求帧、

当问题的规模较大而无aqlal

法直接求解时，将整个问题

分成若干个小问题，然后分问题子结果

Qaq2►a2»A

而治之。分解合并

并在获得较小子问题的

解之后，再将子问题的解合

►qk►ak

并成原始问题的解。

yy

__J

•子问题的划分是一个递归过程。

・通常情况下，要求划分出的子问题与原始问题具有相

同的“类型，，，“同质”

2.分治策略的抽象化控制过程——二分策略

算法2.1分治策略的抽象化控制注：

procedureDANDC(p,q)ak=2:二分是最常用的分解策略；

globaln.A(1:n);aSMALL(p.q)：布尔函数，判断输

入规模q-p+1是否足够小而无需再

integerm,p,q;//1WpWqWn〃进一步分就可求解；

ifSMALL(p,q)

>G(p,q)：当SMALL(p,q)为真时，

thenreturn(G(p,q))对输入规模为q-p+1的子问题求解;

else>DIVIDE(p.q)：当规模q-p+1还较

m—DIVIDER,q)//p<m<q//大时，对规模为q-p+1的子问题进

retum(COMBINE(DANDC(p,m),一步分解，返回值为［p,q］区间进

一步的分割点；

DANDC(m+1,q)))

：子结果的合并函

endif>COMBINE(x,y)

数,将区间［p,m］和［m+1,q］上的子

endDANDC问题的解合并成区间［p,q］上的

“较完整”的解。当p=1,q=n时,

最初的调用：DANDC(1,n)就得到整个问题的解。

■DANDC的计算时间

若所分成的两个子问题的规模大致相等，则DANDC总的

计算时间可用递归关系式表示如下：

rg(n)n足够小

T(n)=<

I2T(n/2)+f(n)否则

>T(n)：表示输入规模为n时的DANDC计算时间

>g(n)：表示对足够小的输入规模直接求解的计算时间

>f(n)：表示COMBINE对两个子区间的子结果进行合并

的时间

(该公式针对具体问题有各种不同的变形)

2.2二分检索——折半查找

1.问题的描述

有序表上的检索问题：已知一个按非降次序排列的元素

表a］，a2,…,小，判定某给定的元素x是否在该表中出现。

>若是，则找出x在表中的位置并返回其所在位置的下标

>若非，贝1J返回。值。

问题的形式描述:

l=(n,a1,a2,...,an,x)

■问题分解：选取下标k,由此将I分解为3个子问题：

11一a2，.…,,x)◄——规模较大

12=(1,ak,x)-------规模足够小

b—(n-k,8+1，E，…,a^x)<规模较大

>对于叨若a1x,则有解k,对「不用再求解;否则，

>若xv%,则只在中求解，对卜不用求解；

>若X〉为,则只在I3中求解，对「不用求解；

>对l1、I3的求解可再次采用分治方法求解-----递归过程

2.二分检索

二分检索：每次选取中间元素的下标

算法2.3二分检索

procedureBINSRCH(A,n,x,j)

integerlow,high,mid,j,n;注：

low—1;high—n;给定一个按非降次序排列

whilelow<highdo的元素数组A(1:n),n》l,

mid<—|_(low+high)/2J判断x是否出现。

case

:x〈A(mid):high—mid-1•若是,置j,使得x=A(j)

:x>A(mid):low<—mid+1•若非，j=0

:else:j<—mid;return

endcase

repeat

jJ。

endBINSRCH

789

例2.1：设A(1:9)=(-15,-6,0,7,9,23,54,82,101)

在A中检索x=101,-14，82o执行轨迹见下表1

表i运行轨迹示例

x=101x=-14x=82

lowhighmidlowhighmidlowhighmid

195195195

697142697

898111898

99921找不到找至IJ

找至U

成功的检索不成功的检索成功的检索

定理2.1过程BINSRCH(A,n,xJ)能正确运行

证明：

1)在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都

能按要求正确运行——即首先满足确定性和能行性

2)终止性

算法初始部分置low-1,high—n

①若n=0,不进入循环，j置0,算法终止

②否则，进入循环，计算mid,

>或x=A(mid),j置为mid,算法终止；

>或xvA(mid),置high—mid",搜索范围实际缩小为［low,mid-1］,

进入下次循环，对［mid+1,high］区间不做进一步搜索；

>或x>A(mid),置low—mid+1,进入下次循环；搜索范围实际缩小

为［mid+1,high］,对［low,mid-1］区间不做进一步搜索;

因low,high,mid都是整型变量，故按照上述规则，在有限步内，或

找到某个mid,有A(mid)=x；或变得low>high,在A市没有找到任何兀

素等于x,算法终止。

3.性能分析

1)空间特性

n+5个空间位置(A,x,j,mid,low,high)-----O(n)

2)时间特性

区分以下情况进行分析

•成功和不成功检索情况：

>成功检索：指所检索的X恰好在A中出现。

由于A中共有n个元素，故成功检索恰好有n种可能的情况

>不成功检索：指x不出现在A中。

根据取值，不成功检索共有n+1种可能的情况(取值区间)：

x<A(1)或A(i)<x<A(i+1),l^i<n-l或x>A(n)

・最好、最坏、平均检索情况——与数据配置有关

A成功/不成功检索的最好情况：最少几次能达到目的

执行步数最少，计算时间最短

▲成功检索的最好情况：若x恰好是A中的某个元素，最少

几次确定x在A中的出现位置：1次

▲不成功检索的最好情况：若x不是A中的任何元素，最少

几次能判断出这一结论

A成功/不成功检索的最坏情况：最多几次能达到目的

执行步数最多，计算时间最长

＞成功/不成功检索的平均情况：典型数据配置下的执行

情况，为一般情况下计算时间的平均值

实例分析（例2.1）

运算的频率计数procedureBINSRCH(A,n,x,j)

1.while循环体外语句的频integerlow,high,mid,j,n;

率计数为1匚>low<—1;high<—n;

whilelow<highdo

2.集中考虑while循环中x与Amid<—(low+high)/2j

中元素的比较运算"\case

——其它运算的频率计数:x<A(mid):high<—mid-1

与比较运算有相同的数量7:x>A(mid):low-mid+1

:else:j<-mid;return

级。4endcase

3.case语句的分析：假定只repeat

需一次比较就可确定casej-。

语句控制是三种情况的哪endBINSRCH

一种。

实例分析(例2.1)

每种查找情况所需的元素比较次数统计如下:

A(1)(2)(3)(4)(5)(6)(7)(8)(9)

元素-15-6079235482101

成功检索比较次数323@0323©

不成功检索比较次数3334433344

成功检索

最好：1次

最坏：4次

平均：(3+2+3+4+1+3+2+3+4)/9"2.77次

■不成功检索

最好：3次

最坏：4次

平均：(3+3+3+4+4+3+3+3+4+4)/10=3.4次

二元比较树

算法执行过程的主体是X与一系列

中间元素A(mid)比较。可用一棵二元树

描述这一过程，称为二元比较树

■结点：分为内结点和外结点两种

»内结点：•代表一次元素比较

•用圆形结点表示

•存放一个mid值(下标)

•代表成功检索情况

»外结点：•用方形结点表示，

,表示不成功检索情况

■路径：代表检索中元素的比较序列

■分支：“小于”进入左分支，“大于”

例2.1的二元比较树

进

入右分支。

二元比较树的查找过程

□若x在A中出现，则算法的执行过

程在一个圆形的内结点处结束

□若x不在A中出现，则算法的执行

过程在一个方形的外结点处结束

注：外结点不代表元素的比较，因

为比较过程在该外结点的上一

级的内结点处结束。

例2.1的二元比较树

定理2.2若n在区域［2-2）中，则对于一次成功的检索，

BINSRCH至多做k次比较；对于一次不成功的检索，

或者做k-1次比较，或者做k次比较。

证明要点：

>二分检索中，每次mid取中值，故其二元比较树是一种“结点平衡”的树

★当2k-〔Wn<2k时，结点分布情况为：

内结点：1至k级

外结点：k级或k+1级，

★外部结点在相邻的两级上——最深一层或倒数第2层

»比较过程：

院成功检索在内结点处结束，不成功检索在外结点处结束

a成功检索在i级的某个内结点终止时，所需要的元素比较次数是i,

等于根到该内结点的路径长度+1。

a不成功检索在i级的外部结点终止所需的元素比较次数是i-1,

等于根到该外结点的路径长度。

BINSRCH的计算复杂度

n引2R2k)

k-logn

1)外结点在最末的两级上，故不成功检索的最好、

最坏和平均情况的计算时间均为0(logn)

2)成功检索的最好情况下计算时间为0(1)

成功检索的最坏情况下计算时间为®(logn)

3)平均情况下的成功检索的计算时间

利用外部结点和内部结点到根距离和之间的关系进行推导。

记，

>由根到所有内结点的距离之和称为内部路径长度，记为I；

>由根到所有外部结点的距离之和称为外部路径长度，记为E。

则有，E=l+2n....................................................................①

记，

>U(n)是平均情况下不成功检索的计算时间，则

U(n)=日(n+1)...............................................②

>S(n)是平均情况下成功检索的计算时间，则

S(n)=l/n+1.................................................③

n个内部结点在成功检索时所需的比较次

数均为根到该结点的路径长度+1

y

由①②③得：

S(n)=(1+1/n)U(n)-1

当rif8,s(n)8u(n),而U(n)=0(logn)

所以S(n)二0(logn)

成功检索不成功检索

最好平均最坏最好平均最坏

0(1)0(logn)0(logn)0(logn)0(logn)0(logn)

4.以比较为基础检索的时间下界

问题：设n个元素的有序表A(1:n),A(1)<A(2)<..<A(n)o检索一

给定元素x是否在A中出现。

问：是否预计还存在有以元素比较为基础的另外的检索算法，它

在最坏情况下比二分检索算法在计算时间上有更低的数量级?

以比较为基础的算法：假定算法中只允许进行元素间的比较，而不

允许对它们实施其它运算。

分析：任何以比较为基础的检索算法，其执行过程都可以用

二元比较树来描述。

图2.2两个检索算法的比较树

(a)模拟线性检索(b)模拟二分检索

内结点：表示一次元素的比较，并代表成功检索情况。每棵比较树中恰

好含有n个内结点，分别与n个不同i值相对应；

外结点：代表不成功检索情况。每棵比较树中恰好有n+1个外结点分别

与n+1中不成功检索情况相对应。

以比较为基础的有序检索问题最坏情况的时间下界有以下结论：

定理2.3设A(1:n)含有n(n>l)个不同的元素，且有

A(1)<A(2)<..<A(n)

又设，用以比较为基础的算法去判断给定的x是否有xeA(l:n)

贝最坏情况下，任何这样的算法所需的最小比较次数FIND(n)

有：FIND(n)2「log(n+l)]

证明：

①从模拟求解检索问题算法的比较树可知，FIND(n)不大于树中由根到

一个叶子(外部结点)的最长路经的距离。

②在所有的二元比较树中必定有n个内结点分别与x在A中的n中可能的

出现相对应。

③如果一棵二元树的所有内结点所在的级数小于或等于k,则该树中最

多有2匕1个内结点。

故，nW2T即

FIND(n)=k>log(n+1)~|

■结论

1)任何一种以比较为基础的有序检索算法，在最坏情况下

的计算时间都不低于O(logn)。因此，不可能存在最坏

情况比二分检索数量级还低的算法。

2)二分检索是解决检索问题的最优的最坏情况算法

2.3找最大和最小元素

查找问题：

1）在元素表中确定某给定的元素的位置或判定

其不出现：二分检索，顺序查找

2）在元素表单独或同时找出其中的最大和

（或）最小

3）在元素表找出其中第一小（大）和第二小

（大）元素

4）找元素表中的第k小元素：排序或选择

等等

本节问题：在元素表同时找出最大元素和最小元素

问题描述：给定含有n个元素的集合（以数组A表

示），找出其中的最大和最小元素。

二种算法的比较:

迭代算法

递归算法

1.直接找最大和最小元素

算法2.5直接找最大和最小元素

procedureSTRAITMAXMIN(A,n,max,min)

〃将A中的最大值置于max,最小值置于min//

Integeri,n

max—min-A⑴

fori<—2tondo算法的性能：

ifA(i)>maxthen

max—A(i)•只考虑算法中的比较

endif运算，以此代表算法

ifA(i)<minthen的执行特征；

min—A(i)

endif•该算法最好、最坏、

repeat平均情况下均需要做

endSTRAITMAXMIN2(n-1)次元素比较

STRAITMAXMIN算法的一种简单改进形式：

procedureSTRAITMAXMIN1(A,n,max,min)

integeri,n

max—min—A⑴

fcri—2tondo

ifA(i)>maxthenmax<—A(i)endif

elseifA(i)<minthenmin—A(i)endif

repeat

endSTRAITMAXMIN1

这使得，

>最好情况：按递增次序排列，元素比较次数为n-1次

>最坏情况：按递减次序排列，元素比较次数为2(n")次

>平均情况：元素比较次数为3(n")/2次

2.分治求解策略

记问题的一个实例为：

l=(n,A(1),...,A(n))

采用二(等)分法将I分成两个子集合处理

b=(|_n/2_,A(1),…，A([n/2_|))，和

l2=(n-[n/2」,A([n/2」+1),…，A(n))

则有,

MAX(I)=max(MAX(l1),MAX(l2))

MIN(I)=min(MIN(l1),MIN(l2))

MAX(I)和MIN(I)分别代表I中元素的最大者和最小者

采用递归的设计策略，得到以下算法：

3.找最大最小元素的递归求解算法

算法2.6递归求取最大和最小元素

procedureMAXMIN(i,j,fmax,fmin)

〃A(1:n)是含有n个元素的全局数组，参数i,j是整数，1Wi,jWn,代表当前的查找区间//

〃该过程把A(i:j)中的最大和最小元素分别赋给fmax和fmin//

integeri,j;globaln,A(l:n)

case

:i=j:fmax-fmin-A(i)〃只有一个元素

:i=j-l:ifA(i)<A(j)thenfmax-A(j);fmin-A(i)

elsefmax-A(i);fmin-A(j)〃两个元素的情况

endif

:else:mid-1(i+j)/2」〃取中，并在两个子区间上作递归调用

callMAXMIN(i,mid,gmax,gmin)

callMAXMIN(mid+1,j,hmax,hmin)

fmax-max(gmax,hmax);fmin-min(gmin,hmin)

endcase

endMAXMIN

MAXMIN过程的初始调用:

MAXMIN(1,n,fmax,fmin)

数组A是全局数组

fmax,fmin带出A(1:n)中的最大和最小元素

例：在A(1:9)=(22,13,-5,-8,15,60,17,31,47)上执行算法2.6

递

归

调

递

用

归

的

调

返

用

回

分

解

过

程

图2.3表示MAXMIN递归调用的树

区间划分将一直进行到只含有1个或2个元素时为止，然后求子解，并返回

MAXMIN过程的性能分析一仅考虑算法中的比较运算

r0n=1

T(n)=<1n=2

、T([n/2j+T(「n/2])+2n>2

当n是2的哥时(n=2k),化简上式有，

T(n)=2T(n/2)+2

=2(2T(n/4)+2)+2

二25(2)+汇21

l<i<k-l

=2k-1+2k-2

=3n/2-2

性能比较

1)与STRAITMAXMIN算法相比，比较次数减少了25%

(3n/2-2:2n-2)o

已经达到了以元素比较为基础的找最大最小元素的算法

计算时间的下界：「3〃/2]-2

2)存在的问题——递归调用造成：

>空间占用量大

有[log〃」+l级的递归，入栈参数：

i,j,fmax,fmin和返回地址五个值。

>时间可能不比预计的理想

如果元素A⑴和A(j)的比较与和j的比较在时间上相差不

大时，算法MAXMIN不可取。

假设元素的比较与i利的比较时间相同(整型数)。又设对case语句调

整，使得仅需一次i和j的比较就能够确定是哪种情况。

case

:i>=j-l:ifA(i)<A(j)thenfmax-A(j);fniin-A(i)

elsefmax-A(i)A(j)〃两个元素的情况

endif

:else:,

记此时MAXMIN的频率计数为C(n),n=2k(k为正整数)。则有，

r2nv=2(一次是i和卜1的比较，一次是A(i)和A(j)的比较)

C(n)=.

2C(n/2)+3n>2

化简得，

C(n)=2C(n/2)+3

=5n/2-3

按照同样的假设，重新估算STRAITMAXMIN算法的比较次数

为：3(n-1)o

>STRAITMAXMIN与MAXMIN在计算时间上的差异越来越小

1/4(25%)=>1/6(16.7%)

»考虑MAXMIN算法递归调用的开销，此时MAXMIN算法

的效率可能还不如STRAITMAXMIN算法。

结论：如果A中的元素间的比较代价远比整型数

（下标）的比较昂贵，则分治方法将产生

一个效率较高的算法；

反之，可能仅得到一个低效的算法。

故，分治策略只能看成一个较好的但并不总是成功

的算法设计指导。

2.4归并分类

1.分类问题——排序

给定一n个元素的集合A,按照某种方法将A中的元素按非

降或非增次序排列。

分类：内排序，外排序

常见内排序方法：冒泡排序

插入排序

归并排序

快速排序

堆排序

冒泡排序

■voidBubbleSort(inta[],intn)

{〃对表a做冒泡排序。

intij,t;

for(i=0；i<n；i++){

for(j=0;j++){

if(a[j]>a0+1]){

temp=a[j];

a[j]=aO+1]；

a[j+1]=temp;

}

}

}

}

2.插入分类

算法2.7插入分类

procedureINSERTIONSORT(A,n)

〃将A(1：n)中的元素按非降次序分类，n>1//

A(0)--8〃设置初始边界值

forj—2tondo〃A(1:j-1)已分类//i指示的是j之前的

item—A(j);i—j-1-------一位，即当前已

排序子表的最末

whileitem<A(i)do//0<i<j//一个元素的下标

A(i+1)—A(i);i-i-1

repeat

A(i+1)<—item;

repeat

endINSERTIONSORT

性能分析：

最坏情况：输入数据按非增次序排列，每次内层

while循环执行j次n)o则有，

Zj=(n(n+1))/2-1

2<j<n

=0(n2)

最好情况：输入数据已按非降序排列，不进入

while循环，则最好情况下计算时间为Q(n)

3.分治策略求解

基本设计思想：将原始数组A中的元素分成两个

子集合：&（1:]n/2」）和A41n/2」+1:n）。分别对这

两个子集合单独分类，然后将已分类的两个子序列

归并成一个含有n个元素的分类好的序列。

这样的一个分类过程称为归并分类。

算法2.8归并分类

procedureMERGESORT(low,high)

〃A(low:high)是一个全程数组，low和high分别指示当前待分类区间的最

小下标和最大下标，含有high・low+120个待分类的元素〃

integerlow,high

iflow<highthen〃当含有2个及2个以上的元素时，作划分与递归处理〃

mid—1(low+high)/2j〃计算中分点〃

callMERGESORT(low,mid)〃在第一个子集合上分类(递归)〃

callMERGESORT(mid+1,high)〃在第二个子集合上分类(递归)〃

callMERGE(low,mid,high)〃归并已分类的两子集合〃

endif

endMERGESORT

算法2.8归并分类(C语言版本)

voidMERGESORT(intlowjnthigh)

〃A(low:high)是一个全程数组，low和high分别指示当前待分类区间的最

小下标和最大下标，含有high・low+120个待分类的元素〃

(

intmid;

if(low<high){〃当含有2个及2个以上的元素时，

作划分与递归处理〃

mid=(low+high)/2;〃计算中分点，利用c语言的整数除法〃

MERGESORT(low,mid)〃在第一个子集合上分类(递归)〃

MERGESORT(mid+1,high)〃在第二个子集合上分类(递归)〃

MERGE(low,mid,high)〃归并已分类的两子集合〃

}

}//endMERGESORT

算法2.9使用辅助数组归并两个已分类的集合

procedureMERGE(low,mid,high)

//A(low,high)是一个全程数组，它含有两个放在A(low,mid)和A(mid+1,high)中的已分

类的子集合.目标是将这两个已分类的集合归并成一个集合，并存放到A(low,high)中〃

integerh,IJ,k,low,mid.highy/low^micKhigh//

globalA(low,high);localB(low,high)

h—low;i—low;j—mid+1;

whileh<midandj<highdo〃当两个集合都没有取尽时，将较小的元素先存放到B中〃

ifA(h)<AQ)thenB(i)<-A(h);h<-h+1〃如果前一个数组中的元素较小〃

elseB(i)—A(j);j-j+1//如果后一个数组中的元素较小//

endif

i-i+1

repeat

〃处理尚有剩余元素的集合〃

ifh>midthenfork—jtohighdoB(i)—A(k);i—i+1;repeat

elsefork<—htomiddoB(i)-A(k);i-i+1;repeat

endif

fork—lowtohighdoA(k)<—B(k)repeat〃将已归并的集合复制到A中〃

endMERGE

算法2.9使用辅助数组归并两个已分类的集合

(C语言)

voidMERGE(intlow,intmidjnthigh)

〃A(low,high)是一个全程数组，它含有两个放在A(low,mid)和A(mid+1,high)中的已分

类的子集合.目标是将这两个已分类的集合归并成一个集合，并存放到A(low,high)中〃

{integerhjj.k;

intB[N]；//设A数组的大小为N

h=low;i=low;j=mid+1;

while(h<=mid&&j<=high){〃当两个集合都没有取尽时，将较小的元素先存放到B中〃

if(A[h]<=A0]){B[i]=A[h];h=h+1;}〃如果前一个数组中的元素较小〃

else{B[i]=A[j];j=j+1;}〃如果后一个数组中的元素较小〃

i-i+1

}

〃处理尚有剩余元素的集合〃

if(h>mid)for(k=j;k<=high;k++){B[i]=A[k];i=i+1;}

elsefor(k=h;k<=mid;k++){B[i]=A[k];i=i+1;}

endif

for(k=low;k<=high;k++)A[k]=B[k]〃将已归并的集合复制到A中〃

}//endMERGE

性能分析

1)过程MERGE的归并时间与两数组元素的总数成正比

故可表示为：cn,n为元素数,c为某正常数

2)过程MERGESORT的分类时间用递推关系式表示如下：

1an=1,a是常数

递归调用一直进行

T(n)=到子区间仅含一个

2T(n/2)+cnn>1,c是常数元素时为止

化简：若廿2匕则有，工-----------------------)

T(n)=2(2T(n/4)+cn/2)+cn

=4T(n/4)+2cn=4T(2T(n/8)+cn/4)+2cn

=2kT(1)+kcn

=an+cnlogn//k=logn//

若2k〈nv2k+i,则有T(n)<T(2k+i)。

所以得：T(n)=O(nlogn)

归并分类示例

■设A二(310,285,179,652,351,423,861,254,450,520)

-1)划分过程

2）归并过程

首先进入左分枝的划分与归并。

第一次归并前的划分状态是:

(310|285|179|652,351|423,861,254,450,520)

第一次归并(285,310|179|652,351|423,861,254,450,520)

第二次归并(179,285,310|652,351|423,861,254,450,520)

第三次归并(179,285,310|351,6521423,861,254,450,520)

第四次归并(179,285,310,351,6521423,861,254,450,520)

进入右分枝的划分与归并过程

（略）

3）用树结构描述归并分类过程

图2.4用树表示MERGESORT。,10）的调用图2.5用树表示对MERGE的调用

4.归并分类算法的改进

1）算法2.8存在的问题

•递归层次太深

在MERGESORT的执行过程中，当集合仅含有两个元素

时，仍要进一步做递归调用，直至每个集合仅含有一个元素

时才退出递归调用。

在集合仅含有相当少的元素时，较深层次的递归调用使

得时间过多地消耗在处理递归上。

•元素在数组A和辅助数组B之间的频繁移动

每次归并，都要首先将A中的元素移到B中，再由B复制

到A的对应位置上。

■2）改进措施

•针对递归层次问题

采用能在小规模集合上有效工作的其它算法，直接对小

规模集合处理。

如INSERTIONSORT算法

•针对元素频繁移动问题

采用一个称为链接信息数组LINK（1：n）的数据结构，

记录归并过程中A中的元素相对于其排序后在分类表中位置

坐标的链接关系。

LINK（i）取值于[1,n],是指向A的元素的指针：在分类

表中它指向下一个元素在A中的位置坐标。

例：

LINK(1)(2)(3)(4)(5)(6)(7)(8)

64713080

»该表中含有两个子表，0表示表的结束。

A设置表头指针Q和R分别指向两个子表的起始处：

Q=2,R=5；

则有，

表1：Q(2,4,1,6),经过分类后有：A(2)<A(4)<A(1)<A(6)

表2：R(5,3,7,8),同样有：A(5)<A(3)<A(7)<A(8)

■链接信息表在归并过程中的应用：

将归并过程中元素在A和B之间移动的过程变成更改LINK

所指示的链接关系，从而避免移动元素的本身。

分类表可以通过LINK的表头指针和读取LINK中的链接关

系取得。

改进后的归并分类模型

算法2.10使用链接信息数组的归并分类模型

procedureMERGESORT1(low,high,p)

//利用链接信息数组LINK(1:n)将全程数组A(low:high)按非降次序分类。LINK中值表示按分类次序给出

A下标的表，并把p置于该表的开始处〃

globalA(low:high),LINK(low,high)

ifhigh-low+1<16〃当集合中的元素个数足够少(<化)时，采用更有效的小规模集合上的分类

算法直接分类〃

thencallINSERTSORT1(A,LINK,low,high,p)〃算法2.7的改进型〃

elsemid—[_(low+high)/2j

callMERGESORT1(low,mid,q)//返回q表〃

callMERGESORT1(mid+1,high,r)〃返回r表〃

callMERGE1(q,r,p)〃将表q和表i•归并成表p〃

endif

endMERGESORT1

算法2.11使用链接表归并已分类的集合

procedureMERGE1(q,r,p)

〃q和r是全程数组LINK(1:n)中两个表的指针。归并这两个表，得到一个由p所指示的新表。此表将

A中的元素按非降次序分类。LINK(O)被定义〃

globaln,A(1:n),LINK(1:n)

localintegeri,j,k

i<—q;j<—r;k<—0〃新表在LINK(O)处开始〃

whilei#0andj#0do//当两表均非空时〃

ifA(i)<AQ)//找较小的关键字〃

thenLINK(k)——LINK。)//加一个新关键字到表中〃

elseLINK(k)-j;k—j;j-LINK。)//加一个新关键字到表中〃

endif

repeat

ifi=9thenLINK(k)=j

elseLINK(k)=i

endif

endMERGE1

MERGES0RT1的调用

>在初次调用时，待分类的n个元素放于A(1:n)中。

>LINK(1:n)初始化为0；

>初次调用：callMERGESORT1(1,n,p)

>p作为按分类次序给出A中元素的指示表的指针。

3)改进归并分类算法示例

设元素表：(50,10,25,30,15,70,35,55)

采用MERGESORT1对上述元素表分类(不做小规模集合

的单独处理)

下表给出在每一次调用MERGESORT1结束后，LINK数

组的变化情况。

表2.2例2.4中LINK数组的变化过程

(0)(1)(2)(3)⑷(5)(6)(7)(8)

A—50102530-15703555

LINK000000000

qrP

122201000000(10,50)

343301400000(10,50),(25,30)

232203410000(10,25,30,50)

565503416000(10,25,30,50),(15,70)

787703416Q80(10,25,30,50),(15,70),(35,55)

575503417-086(10,25,30,50)(15,35,55,70)

252285473016(10,15,25,30,35,50,55,70)

在上表的最后一行，p=2返回，得到链表(2,5,3,4,7,1,8,6)

即：A(2)^A(5)<A(3)<A(4)<A(7)<A(1)<A(8)<A(6)

5.以比较为基础分类的时间下界

1.分类的“实质”

给定n个记录RiR，《淇相应的关键字是…,七。

分类就是确定12…,n的一种排列P「P如..Pn，使得记录的

关键字满足以下非递减（或非递增）排列关系

kp〔Wkp2W•••Wkpn

从而使n个记录成为一个按关键字有序的序列:

{Rpi,Rp2,…，Rpn}

2.以关键字比较为基础的分类算法的时间下界

最坏情况下的时间下界为：Q(nlogn)

利用二元比较树证明。

假设参加分类的n个关键字A(1),A(2),…,A(n)互异。任意

两个关键字的比较必导致A(i)〈A(j)或A(i)>A(j)的结果。

以二元比较树描述元素间的比较过程：

>若A(i)<A(j),进入下一级的左分支

>若A(i)>A(j),进入下一级的右分支

算法在外部结点终止。

从根到某外结点的路径代表某个特定输入情况下一种唯一的分类排序序列。路

径长度表示生成该序列代表的分类表所需要的比较次数。而最长的路径代表算法在

最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。

故，以比较为基础的分类算法的最坏情况下界等于该算法对应的比较树的最小

司度。

①由于n个关键字有n!种可能的排列，所以分类二元比较树中将有

n!个外部结点：每个外部结点代表一种特定的排列，该排列对应于某种

特定输入情况下的分类序列。

②设一棵二元比较树的所有内结点的级数均小于或等于k,则该树

中最多有2k个外结点。

记算法在最坏情况下所作的比较次数为T(n),则有T(n)二k：生成外

结点所代表的分类序列所需的比较次数等于该外结点所在的级数T;

根据①和②的分析，有：

n!W2T(n)

化简：

当n〉l时，有n!Nn(nT)(n-2)…(|"n/2"|)2(n/2)石

当n三4时，有T(n)2(n/2)log(n/2)N(n/4)logn

故，任何以比较为基础的分类算法的最坏情况的时间下界为：

Q(nlogn)

2.5快速分类

1.划分与快速分类

＞快速分类是一种基于划分的分类方法；

＞划分：选取待分类集合A中的某个元素t,按照与t的大小关系重

新整理A中元素，使得整理后t被置于序列的某位置上，

而序列中所有在t以前出现的元素均小于等于t,而所有出

现在t以后的元素均大于等于t。这一元素的整理过程称为

划分(Partitioning)。

元素t称为划分元素。

＞快速分类：对待排序集合通过反复划分达到分类目的的分

类算法。

划分过程(PARTITION)的算法描述

算法2.2用A(m)划分集合A(m:pA(p)被定义，但为一限界值，

不包含在实际的分类区间内。

procedurePARTITION(m,p)

V.?

integerglobalA(m:p-1)/

v—A(m);i—m〃A(m)是划分元素〃

loop

loopi<—i+1untilA(i)>vrepeat〃i由左向右移〃

loopp<—p-1untilA(p)<vrepeat〃p由右向左移〃

ifi<pthen

callINTERCHANGE(A(i),A(P))

elseexit

endif

repeat

A(m)—A(p)；A(p)—v〃划分元素在位置p〃

endPARTITION

注：

>算法对集合A(m:p-1)进行划分。并使用待划分区间的第一

个元素A(m)作为划分元素

>A(p)不在划分区间内，但被定义，且A(p)三A(m),用于

限界

例2.5划分实例

⑴(2)⑶⑷⑸(6)⑺(8)(9)(10)iP

A:6570758085605550454-oo29

1..■,11

A:6545758085605550704-oo38

A:654550808560557570+oo47

II

■•I

A:654550558560807570+oo56

I….I

交■-I

换A:654550556085807570+oo65

划►II

分I

一A:604550556585807570+oo

t

划分元素定位于此

经过一次“划分”后，实现了对集合元素的调整：

以划分元素为界，左边子集合的所有元素均小于等于右

边子集合的所有元素。

按同样的策略对两个子集合进行分类处理。当子集合分类

完毕后，整个集合的分类也完成了。这一过程避免了子集合

的归并操作。这一分类方法称为快速分类。

2.快速分类算法

——一种通过反复使用划分过程PARTITION实现对集合

元素分类的算法。

算法2.13快速分类

procedureQUICKSORT(p,q)

〃将数组A(1:n)中的元素A(p),…A(q)按递增的方式分类。

A(n+1)有定义，且假定A(n+1)—+8〃

integerp,q;globaln,A(1:n)

ifp<qthen

j-q+1〃进入时，A(j)定义了划分区间［p,q］的上界，首次调用时j=n+1

callPARTITION(pJ)〃出口时，j带出此次划分后划分元素所在的卜标位置〃

callQUICKSORT(p,j-1)〃对前一子集合递归调用

callQUICKSORT］+1,q)〃对后一子集合递归调用

endif

endQUICKSORT

3.快速分类分析

■统计的对象：元素的比较次数——Partition过程，记为：C(n)

■两点假设

①参加分类的n个元素各不相同

②PARTITION中的划分元素v是随机选取的(针对平均情况的分

析)

>随机选取划分元素：

在划分区间随机生成某一坐标：i-RANDOM(m.p-l)；

调换A(m)与A⑴：v<—A(i);A(i)<—A(m);i<—m

作用：将随机指定的划分元素的值调换到A(m)位置。算法主体

不变。之后，仍从A(m)开始执行划分操作。

递归层次n个元素参加划分和分类

设在任一级递归调用上，调用PARTITION处理的所有元素总数为r,则，初始

时r二n,以后的每级递归上，由于删去了上一级的划分元素，故r比上一级至少1：

理想情况，第一级少1,第二级少2,第三级少4,...；

最坏情况，每次仅减少1（每次选取的划分元素刚好是当前集合中最小或最大者）

■最坏情况分析

>记最坏情况下的元素比较次数是Cw(n)；

>PARTITION一次调用中的元素比较数是p-m+1,若一级

递归调用上处理的元素总数为r,则PARTITION的比较总数

为0(r)。

最坏情况下(第i次调用Partition所得的划分元素恰好是

第i小元素)，每级递归调用的元素总数仅比上一级少1,故

Cw(n)是r由n到2的累加和。

2

即：Cw(n)==0(n)

■平均情况分析

平均情况是指集合中的元素以任意顺序排列，且任选元素

作为划分元素进行划分和分类，在这些所有可能的情况下，算

法执行性能的平均值。

设调用PARTITION(m,p)时，所选取划分元素v恰好是

A(m:p-1)中的第i小元素的概率相等。则经过一

次划分，所留下的待分类的两个子文件恰好是A(m:j-1)和

A(j+1:p-1)的概率是：1/(p-m),记平均情猊卞的元素

比较次数是CA(FI)；则有，

q⑺=〃+1+!z(g(i)+g(1))

X<k<n

其中，

n+1是PARTITION第一次调用时所需的元素比较次数。

>CA(0)=CA(1)=0

化简上式可得：

CA(n)/(n+1)=CA(n-l)/n+2/(n+1)

=CA(n-2)/(n-l)+2/n+2/(n+1)

=CA(n-3)/(n-2)+2/(nT)+2/n+2/(n+1)

=CA(1)/2+2

?)<k<n+\

由于

3<k<n-\-\

所以得，CA(n)<2(n+l)loge(n+1)=0(nlogn)

■空间分析

最坏情况下，递归的最大深度为n-1.

需要栈空间：0(n)

使用一个迭代模型可以将栈空间总量减至O(logn)

4,快速分类算法的迭代模型

处理策略：每次在Partition将文件A(p:q)分成两个文件

A(p:j-1)和A(j+1,q)后，先对其中较小的子文件

进行分类。当小的子文件分类完成后，再对较

大的子文件进行分类。

栈：需要一个栈空间保存目前暂不分类的较大子文件。并

在较小子文件分类完成后，从栈中退出最新的较大子

文件进行下一步分类。

栈空间需要量：O(logn)

算法的终止：当栈空时，整个分类过程结束。

cr

d

O

算法2.14QuickSort2(p,q)

integerSTACK(1:max),top//max=2[)ogn]

globalA(1:n);localintegerj

top—0

loop

whilep<qdo

j-q+1

callPARTITION(pJ);

ifj-p<q-j〃先对较小的子文件分类，并将规模较大的子文件入栈

thenSTACK(top+1)<-j+1；STACK(top+2)fq-j・1

elseSTACK(top+1Kp;STACK(top+2)<-j-1；P—j+1

endif

top-top+2//调整栈顶指针

repeat

iftop=0thenreturnendif〃如果栈为空，算法结束

q<-STACK(top);p<-STACK(top-1);top-top-2〃从栈中退出先前保存的

较大的子文件

repeat

endQUICKS0RT2

•快速分类算法迭代模型的空间分析

算法2.14的最大空间是O(logn)

推导：

设算法所需的最大栈空间是S(n),则有

2+S(L(n-l)/2j)n>l

S(〃)=

0n<l

2.6选择问题

1.问题描述

在n个元素的表A(