1、2022-12-20第四章第四章 分治法分治法 “分分”而治之而治之4.1 一般方法一般方法n 对大规模问题的求解对大规模问题的求解 n 利用分治法求解大规模问题利用分治法求解大规模问题 1.基本思想基本思想 分而治之方法法与软件设计的模块化方法非常相似。分而治之方法法与软件设计的模块化方法非常相似。为解决一个大问题，可以为解决一个大问题，可以（1）把它）把它分解分解成两个或多个成两个或多个更小的问题；（更小的问题；（2）分别解决分别解决每个小问题；（每个小问题；（3）把各）把各小问题的解答小问题的解答组合组合起来，即可得到原问题的解。起来，即可得到原问题的解。小问题通常与原问题相似或同质小问
2、题通常与原问题相似或同质，因而可以，因而可以递归递归地地使用分而治之策略解决。使用分而治之策略解决。2022-12-20通常，子问题与原始问题通常，子问题与原始问题“同质同质”2022-12-20例例找伪币找伪币 假设假设16 16 枚金币中有一枚是伪造的，真枚金币中有一枚是伪造的，真假金币的区别仅是重量不同假金币的区别仅是重量不同(伪币轻一些），利用一伪币轻一些），利用一个没有砝码的天平作工具，找出这枚伪造的金币。个没有砝码的天平作工具，找出这枚伪造的金币。方法方法1：比较硬币：比较硬币1和和2的重量，有一个轻则找到；的重量，有一个轻则找到；否则比较硬币否则比较硬币3和和4，依次比较下去，直
3、到找到。最，依次比较下去，直到找到。最多多8次比较。次比较。方法方法2：利用分治法。：利用分治法。16个硬币分为两组，每组个硬币分为两组，每组8个，个，比较重量，伪币在轻的一组。将轻的一组再分为两比较重量，伪币在轻的一组。将轻的一组再分为两组，每组组，每组4个个继续划分下去，依次每组继续划分下去，依次每组2个，每个，每组组1个，此时找到。个，此时找到。2022-12-20算法算法4.1 分治策略的抽象化控制分治策略的抽象化控制procedure DANDC(p,q)global n,A(1:n);integer m,p,q;/1pqnpqn/if SMALL(p,q)then return(G
4、(p,q)else mDIVIDE(p,q)/pmmq q/return(COMBINE(DANDC(p,m),DANDC(m+1,q)endifend DANDC 注：注：k=2:二分二分是最常用的分解策略；是最常用的分解策略；SMALL(p,q)：布尔函数，判断布尔函数，判断输入规模输入规模q-p+1是否足够小而无是否足够小而无需再进一步分就可求解；需再进一步分就可求解；G(p,q)：对输入规模为对输入规模为q-p+1的的子问题求解（子问题求解（SMALL(p,q)为真为真时）；时）；DIVIDE(p.q)：对输入规模为对输入规模为q-p+1的子问题进一步分解，返回的子问题进一步分解，返回
5、值为值为p,q区间进一步的分割点区间进一步的分割点（SMALL(p,q)不为真时为真时）；COMBINE(x,y)：子结果的合并子结果的合并函数，将区间函数，将区间p,m和和m+1,q上上的子问题的解合并成上级区间的子问题的解合并成上级区间p,q上的上的“较完整较完整”的解。当的解。当p=1,q=n时，就得到整个问题的时，就得到整个问题的解。解。2.2.分治策略的抽象化控制分治策略的抽象化控制2022-12-20n DANDC的计算时间的计算时间 若所分成的两个子问题的输入规模大致相等，则若所分成的两个子问题的输入规模大致相等，则DANDC总的计算时间可用递归关系式表示，如下：总的计算时间可用
6、递归关系式表示，如下：g(n)n足够小足够小 T(n)=2T(n/2)+f(n)否则否则 注：注：T(n)：表示输入规模为表示输入规模为n的的DANDC计算时间计算时间 g(n)：表示对足够小的输入规模直接求解的计算时间表示对足够小的输入规模直接求解的计算时间 f(n)：表示表示COMBINE对两个子区间的子结果进行合并对两个子区间的子结果进行合并 的时间的时间 （该公式针对具体问题有各种不同的变形）（该公式针对具体问题有各种不同的变形）2022-12-204.2 二分检索（折半查找）二分检索（折半查找）1.1.问题的描述问题的描述 已知一个按已知一个按非降次序非降次序排列的元素表排列的元素表
7、a1,a2,an,判定某给定的元素判定某给定的元素x是否在该表中出是否在该表中出现。现。若是，则找出若是，则找出x在表中的位置并返回其所在下在表中的位置并返回其所在下标标 若非，则返回若非，则返回0值。值。2022-12-20分治求解策略分析分治求解策略分析：n 定义问题的定义问题的形式描述形式描述：I=(n,a1,a2,an,x)n 问题分解：选取下标问题分解：选取下标k，由此将，由此将I分解为分解为3个子问题：个子问题：I1=(k-1,a1,a2,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,ak+2,an,x)对于对于I2，若，若ak=x，则有解，则有解k，对，对I1、I
8、3不用再求解；否则，不用再求解；否则，若若xak，则只在，则只在I3中求解，对中求解，对I1不用求解；不用求解；I1、I3上的求解可再次采用分治方法划分后求上的求解可再次采用分治方法划分后求解（解（递归过程递归过程）2022-12-202.2.二分检索算法二分检索算法算法算法4.3 二分检索二分检索procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low1;highn;while lowhigh do mid case :xA(mid):low mid+1 :else:jmid;return endcase repeat j0end BINS
9、RCHhigh)/2(low注注：给定一个按非降次序排给定一个按非降次序排列的元素数组列的元素数组A(1:n)，n1,1,判断判断x x是否出现。是否出现。若是，置若是，置j j，使得，使得x=A(j)x=A(j)若非，若非，j=0j=02022-12-20例例2.1：设：设A(1:9)=(-15，-6，0，7，9，23，54，82，101)在在A中检索中检索x=101，-14，82。执行轨迹见下表。执行轨迹见下表1表表1 1 运行轨迹示例运行轨迹示例x=101x=101x=-14x=-14x=82x=82lowlowhighhighmidmidlowlowhighhighmidmidlowl
10、owhighhighmidmid1 19 95 51 19 95 51 19 95 56 69 97 71 14 42 26 69 97 78 89 98 81 11 11 18 89 98 89 99 99 92 21 1找不到找不到找到找到找到找到成功成功的检索的检索不成功不成功的检索的检索成功成功的检索的检索2022-12-203.3.算法的正确性证明算法的正确性证明定理定理4.1 过程过程BINSRCH(A,n,x,j)能正确运行能正确运行证明：证明：1）在具体指定）在具体指定A中的数据元素及中的数据元素及x的数据类型后，算法中的所有运算都的数据类型后，算法中的所有运算都 能按要求正确
11、运行能按要求正确运行即首先满足确定性和能行性即首先满足确定性和能行性2）终止性）终止性 算法初始部分置算法初始部分置low1,highn 若若n=0，不进入循环，不进入循环，j置置0，算法终止，算法终止 否则，进入循环，计算否则，进入循环，计算mid,或或 x=A(mid)，j置为置为mid，算法终止；，算法终止；或或xA(mid)，置，置lowmid+1，进入下次循环；搜索范围实际缩小，进入下次循环；搜索范围实际缩小 为为mid+1,high，对，对low,mid-1区间不做进一步搜索；区间不做进一步搜索；因因low,high,mid都是整型变量，故按照上述规则，在都是整型变量，故按照上述规
12、则，在有限步内有限步内，或，或找到某个找到某个mid，有，有A(mid)=x；或变得；或变得lowhigh，在，在A中没有找到任何中没有找到任何元素等于元素等于x，算法终止。，算法终止。2022-12-204.4.性能分析性能分析1）空间特性）空间特性 n+5个空间位置个空间位置(n)(n)2)2)时间特性时间特性 区分以下情况，并进行相应的分析区分以下情况，并进行相应的分析成功检索成功检索：所检索的：所检索的x x出现在出现在A A中。中。成功检索情况共有成功检索情况共有n n种种：x x恰好是恰好是A A中的某个元素，中的某个元素，A A中共有中共有n n个元素，故有个元素，故有n n种可
13、能的情况种可能的情况不成功检索不成功检索：所检索的：所检索的x x不出现在不出现在A A中。中。不成功检索情况共有不成功检索情况共有n+1n+1种种：xA(1),xA(1),或或A(i)xA(i+1),1in-1A(i)xA(i+1),1iA(n)xA(n)成功成功/不成功检索的最好情况不成功检索的最好情况：执行步数最少，计算时间最短：执行步数最少，计算时间最短成功成功/不成功检索的最坏情况不成功检索的最坏情况：执行步数最多，计算时间最长：执行步数最多，计算时间最长成功成功/不成功检索的平均情况不成功检索的平均情况：一般情况下的计算时间：一般情况下的计算时间2022-12-20实例分析（例实例
14、分析（例4.1）n 频率计数特征频率计数特征1.while循环体外语句的频率计数为循环体外语句的频率计数为12.集中考虑集中考虑while循环中的循环中的x与与A中元素的比较（其中元素的比较（其它运算的频率计数与之有相同的数量级）它运算的频率计数与之有相同的数量级）假定只需一次比较就可确定假定只需一次比较就可确定case语句控制是三语句控制是三种情况的哪一种。查找每个元素所需的元素比较次种情况的哪一种。查找每个元素所需的元素比较次数统计如下：数统计如下：A 元素元素 -15 -6 0 7 9 23 54 82 101-15 -6 0 7 9 23 54 82 101成功检索成功检索比较次数比较
15、次数 3 2 3 4 1 3 2 3 43 2 3 4 1 3 2 3 4 不成功检索不成功检索比较次数比较次数 3 3 3 4 4 3 3 3 4 43 3 3 4 4 3 3 3 4 42022-12-20n成功检索成功检索 最好最好：1 1次次 最坏最坏：4 4次次 平均平均：（：（3+2+3+4+1+3+2+3+43+2+3+4+1+3+2+3+4）/9/92.772.77次次n不成功检索不成功检索 最好最好：3次次 最坏最坏：4次次 平均平均：(3+3+3+4+4+3+3+3+4+4)/10=3.4次次2022-12-20二元比较树二元比较树n算法执行过程的算法执行过程的主体主体是是
16、x与一与一系列中间元素系列中间元素A(mid)比较。比较。可用一棵二元树描述这一过程，可用一棵二元树描述这一过程，并称之为并称之为二元比较树二元比较树。n构造构造：比较树由称为：比较树由称为内结点内结点和和外结点外结点的两种结点组成：的两种结点组成：内结点内结点：表示一次元素比较，：表示一次元素比较，用圆形结点表示，存放一个用圆形结点表示，存放一个mid值；代表一次成功检索；值；代表一次成功检索；外结点外结点：在二分检索算法中表：在二分检索算法中表示一种不成功检索的情况，用示一种不成功检索的情况，用方形结点表示。方形结点表示。路路 径径：表示一个元素的比较：表示一个元素的比较序列。序列。例例4
17、.1的二元比较树的二元比较树2022-12-20基于二元比较树的分析基于二元比较树的分析p 若若x在在A中出现，则算法的中出现，则算法的执行过程在一个圆形的执行过程在一个圆形的内结内结点点处结束。处结束。p 若若x不在不在A中出现，则算法中出现，则算法的执行过程在一个方形的的执行过程在一个方形的外外结点结点处结束处结束 外结点不代表元素的外结点不代表元素的比较，因为比较过程在该外比较，因为比较过程在该外结点的上一级的内结点处结结点的上一级的内结点处结束。束。例例4.1的二元比较树的二元比较树2022-12-20定理定理4.2 若若n在区域在区域2k-1,2k)中，则对于中，则对于一次成一次成功
18、的检索功的检索，BINSRCH至多做至多做k次比较；对于次比较；对于一一次不成功的检索次不成功的检索，或者做，或者做k-1次比较，或者做次比较，或者做k次比较。次比较。证明：证明：要点：要点：成功检索都在内结点处结束，不成功检索都在外结点处结束成功检索都在内结点处结束，不成功检索都在外结点处结束 当当2k-1nn2k时，所有内结点在时，所有内结点在1至至k级，所有外结点在第级，所有外结点在第k级级 或第或第k+1级，级，故：成功检索在故：成功检索在i级终止所需要的元素比较次数是级终止所需要的元素比较次数是i 不成功检索在不成功检索在i级外部结点终止的元素比较次数是级外部结点终止的元素比较次数是
19、i-12022-12-20BINSRCH计算复杂度的理论分析计算复杂度的理论分析1）不成功检索的最好、最坏和平均情况的计算时）不成功检索的最好、最坏和平均情况的计算时间均为间均为 外结点处在最末的两级上；外结点处在最末的两级上；2）最好情况下的成功检索的计算时间为）最好情况下的成功检索的计算时间为 最坏情况下的成功检索的计算时间为最坏情况下的成功检索的计算时间为(logn)(1)(logn)2022-12-203）平均情况下的成功检索的计算时间分析）平均情况下的成功检索的计算时间分析 利用利用外部结点和内部结点到根距离和之间的关系外部结点和内部结点到根距离和之间的关系进行推导：进行推导：记，记
20、，由根到所有内结点的距离之和称为由根到所有内结点的距离之和称为内部路径长度内部路径长度，记为，记为I；由根到所有外部结点的距离之和称为由根到所有外部结点的距离之和称为外部路径长度外部路径长度，记为，记为E。则有，则有，E=I+2n 记，记，U(n)是平均情况下不成功检索的计算时间，则是平均情况下不成功检索的计算时间，则U(n)=E/(n+1)S(n)是平均情况下成功检索的计算时间，则是平均情况下成功检索的计算时间，则S(n)=I/n+1 利用上述公式，可有利用上述公式，可有:S(n)=(1+1/n)U(n)-1 当当n,S(n)U(n)，而，而U(n)=所以所以 S(n)=S(n)=(logn
21、)(logn)2022-12-204.4.以比较为基础检索的时间下界以比较为基础检索的时间下界问题问题：设：设n个元素的数组个元素的数组A(1:n)有有A(1)A(2)A(n)。检索一给定元素。检索一给定元素x是否在是否在A中出现。中出现。定理定理4.2给出了二分检索算法的时间下界，是否给出了二分检索算法的时间下界，是否预计还存在有以元素比较为基础的另外的检索算法，预计还存在有以元素比较为基础的另外的检索算法，它在最坏情况下比二分检索算法在计算时间上有它在最坏情况下比二分检索算法在计算时间上有更低更低的数量级的数量级?以比较为基础的算法以比较为基础的算法：假定算法中只允许：假定算法中只允许进行
22、元素间的进行元素间的比较比较，而不允许对它们实施其它，而不允许对它们实施其它运算。运算。2022-12-20注：每个注：每个内结点内结点表示一次元素的比较。每棵比较树中恰好含有表示一次元素的比较。每棵比较树中恰好含有n个内结个内结点，分别与点，分别与n个不同个不同i值相对应；每个值相对应；每个外结点外结点对应一次不成功的检索，并对应一次不成功的检索，并恰好又恰好又n+1个外结点对应于个外结点对应于n+1中不成功检索的情况。中不成功检索的情况。n任何以比较为基础的检索算法，其执行过程都可任何以比较为基础的检索算法，其执行过程都可以用二元比较树来描述。以用二元比较树来描述。2022-12-20 以
23、比较为基础的有序检索问题最坏情况的时间下界以比较为基础的有序检索问题最坏情况的时间下界n定理定理4.3 设设A(1:n)含有含有 n(n1)1)个不同的元素，排序为个不同的元素，排序为A(1)A(2)max then maxA(i)endif if A(i)max then maxA(i)endif else if A(i)min then minA(i)endif repeatend STRAITMAXMIN1这使得，这使得，最好情况：最好情况：按按递增次序递增次序排列，元素比较次数为排列，元素比较次数为n-1次次最坏情况：最坏情况：按按递减次序递减次序排列，元素比较次数排列，元素比较次数为
24、为2(n-1)次次平均情况：平均情况：元素比较次数元素比较次数为为3(n-1)/2次次2022-12-202.分治求解策略分治求解策略 记问题的一个实例为：记问题的一个实例为：I=(n,A(1),A(n)采用二分法将采用二分法将I分成两个子集合处理分成两个子集合处理 I1=(,A(1),，A()，和，和 I2=(n-,A(+1),，A(n)则有，则有，MAX(I)=max(MAX(I1),MAX(I2)MIN(I)=min(MIN(I1),MIN(I2)采用递归的设计策略，得到以下算法：采用递归的设计策略，得到以下算法：n/2n/2n/2n/22022-12-203.一种递归求解策略一种递归求
25、解策略算法算法4.6 递归求取最大和最小元素递归求取最大和最小元素procedure MAXMIN(i,j,fmax,fmin)/A(1:n)是含有是含有n个元素的数组，参数个元素的数组，参数I,j是整数，是整数，1i,jn i,jn/该过程把该过程把A(i:j)A(i:j)中的最大和最小元素分别赋给中的最大和最小元素分别赋给fmaxfmax和和fminfmin /integer i,j;global n,A(1:n)integer i,j;global n,A(1:n)case case :i=j:fmaxfminA(i :i=j:fmaxfminA(i)/)/只有一个元素只有一个元素 :i
26、=j-1:if A(i)A(j)then fmaxA(j);fminA(i:i=j-1:if A(i)2当当n是是2的幂时的幂时(n=2k),化简上式有，化简上式有，T(n)=2T(n/2)+2 =2(2T(n/4)+2)+2 =2k-1T(2)+=2k-1+2k-2 =3n/2-22)n/2T()n/2T(1ki1i22022-12-20性能分析性能分析1）与）与STRAITMAXMIN算法相比，比较次数减少了算法相比，比较次数减少了25%（3n/2-2:2n-2)。已经达到了以已经达到了以元素比较为基础元素比较为基础的找最大最小元素的算法的找最大最小元素的算法 计算时间的计算时间的下界下界
27、：2）存在的问题：）存在的问题：空间占用量大空间占用量大 有有 级的递归，入栈参数：级的递归，入栈参数：i,j,fmax,fmin和返回地址五个值。和返回地址五个值。时间可能不比预计的理想时间可能不比预计的理想 如果元素如果元素A(i)和和A(j)的比较与的比较与i和和j的比较的比较相差不大相差不大时，算时，算法法MAXMIN不可取不可取。22/3n1logn2022-12-20 假设元素的比较与假设元素的比较与i和和j的比较时间相同（整型数）。又设的比较时间相同（整型数）。又设case语句中仅需一次语句中仅需一次i和和j的比较就能够确定是哪种情况。记此的比较就能够确定是哪种情况。记此时时MA
28、XMIN的频率计数为的频率计数为C(n)，n=2k(k为正整数）。则有，为正整数）。则有，2 n=2 C(n)=2C(n/2)+3 n2 化简得，化简得，C(n)=2C(n/2)+3 =5n/2-3 按照同样的假设，重新估算按照同样的假设，重新估算STRAITMAXMIN算法的比较算法的比较次数为：次数为：3(n-1)。考虑考虑MAXMIN算法算法递归调用的开销递归调用的开销，此时，此时MAXMIN算法算法 的效率可能还不如的效率可能还不如STRAITMAXMI算法。算法。2022-12-20结论：如果结论：如果A中的元素间的比较代价远比整型数中的元素间的比较代价远比整型数 （下标）的比较（下
29、标）的比较昂贵昂贵，则分治方法将产生，则分治方法将产生 一个一个效率较高效率较高的算法；的算法；反之，可能仅得到一个反之，可能仅得到一个低效低效的算法。的算法。故，分治策略只能看成一个故，分治策略只能看成一个较好的较好的但但并不总是成功并不总是成功 的算法设计指导。的算法设计指导。2022-12-20思考题：最大子段和问题思考题：最大子段和问题n求数列的最大子段和。求数列的最大子段和。n给定给定n个元素的整数列个元素的整数列(可能为负整数可能为负整数)a1，a2，an，求形如求形如ai，ai+1，aj，i，j=1，2，n，i=j的子段，的子段，使其和为最大。使其和为最大。n例如，当例如，当(a
30、1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)max_sum=20，best_i=2，best_j=42022-12-20n若用一般的二分法解决该实例？若用一般的二分法解决该实例？n分解为两组分解为两组(-2,11,-4)和和(13,-5,-2)11111313不独立，子问题中不独立，子问题中间有公共子问题间有公共子问题2022-12-20对重叠子问题对重叠子问题专门处理专门处理n“三三”分治分治情形情形1情形情形2情形情形3将将a1.n分为长度相等的分为长度相等的2段段a1.(n/2)和和a(n/2)+1.n,分别求这分别求这2段段最大子段和最大子段和,则则a1.
31、n最大子段和有最大子段和有3种情形种情形:1)a1.n的最大子段和与的最大子段和与a1.(n/2)的最大子段和相同；的最大子段和相同；2)a1.n的最大子段和与的最大子段和与a(n/2)+1.n的最大字段和相同的最大字段和相同;3)a1.n的最大字段和为的最大字段和为ai.j,且且1i(n/2),(n/2)+1jn。情况情况1)和情况和情况2)可分别递归求得。可分别递归求得。对于情况对于情况3）,a(n/2)与与a(n/2)+1一定在最大子段中。一定在最大子段中。因此因此,可以计算出可以计算出ai.(n/2)最大值最大值s1和和a(n/2)+1.j最大值最大值s2。则。则s1+s2即为情况即为
32、情况3)时最优值。时最优值。2022-12-20n“三三”分治分治情形情形1情形情形2情形情形3n对分解得到的左右子段，求对分解得到的左右子段，求左右子段内部的最大子段和；左右子段内部的最大子段和；左子段中满足以下条件的最大的子段和左子段中满足以下条件的最大的子段和s1：以任何位：以任何位置置i开始，结尾处开始，结尾处n/2结束；结束；右子段中满足以下条件的最大的子段和右子段中满足以下条件的最大的子段和s2：以起始位：以起始位置置n/2+1开始，任何位置开始，任何位置j结束；结束；n原问题最大子段和是左右子段内最大和与原问题最大子段和是左右子段内最大和与两个子段最大值求和两个子段最大值求和s1
33、+s2中的大者。中的大者。2022-12-204.4 4.4 归并分类归并分类1.分类问题分类问题排序排序 给定一给定一n个元素的集合个元素的集合A，按照某种方法将，按照某种方法将A中的元素按非中的元素按非降或非增次序排列。降或非增次序排列。分类：内排序，外排序分类：内排序，外排序 常见内排序方法：冒泡排序常见内排序方法：冒泡排序 插入排序插入排序 归并排序归并排序 快速排序快速排序 堆排序堆排序 例 输入：（8，5，4，9）输出：（4，5，8，9）或 （9，8，5，4）2022-12-202.插入分类插入分类 算法算法4.7 插入分类插入分类 procedure INSERTIONSORT(
34、A,n)/将将A(1：n)中的元素按非降次序分类，中的元素按非降次序分类，n1/A(0)-/设置初始边界值设置初始边界值 for j2 to n do/A(1:j-1)已分类已分类/itemA(j);ij-1 while itemA(i)do /0ij/A(i+1)A(i);ii-1 repeat A(i+1)item;repeat end INSERTIONSORT n(8,5,4,9)n(8,5,4,9)n(5,8,4,9)n(5,8,4,9)n(4,5,8,9)n(4,5,8,9)2022-12-20 性能分析：性能分析：最坏最坏情况：输入数据按非增次序排列情况：输入数据按非增次序排列,
35、每次每次内层内层while循环循环执行执行j次（次（j=2,3,n)。则有，。则有，最好最好情况：输入数据已按非降序排列，不进入情况：输入数据已按非降序排列，不进入while循环，则最好情况下计算时间为循环，则最好情况下计算时间为(n)(n21 1)/2(n(njnj22022-12-203.3.分治策略求解分治策略求解 基本设计思想：将原始数组基本设计思想：将原始数组A中的元素分成两个中的元素分成两个子集合：子集合：A1(1:)和和A2(+1 :n)。分别对。分别对这两个子集合单独分类，然后将已分类的两个子序这两个子集合单独分类，然后将已分类的两个子序列归并成一个含有列归并成一个含有n个元素
36、的分类好的序列。个元素的分类好的序列。这样的一个分类过程称为这样的一个分类过程称为归并分类归并分类。n/2n/22022-12-20算法算法4.8 归并分类归并分类 procedure MERGESORT(low,high)/A(low:high)是一个全程数组，它含有是一个全程数组，它含有high-low+100个待分类的元素个待分类的元素/integer low,high if lowmid then for kj to high do B(i)A(k);ii+1;repeat else for kh to mid do B(i)A(k);ii+1;repeat endif for k l
37、ow to high do A(k)B(k)repeat /将已归并的集合复制到将已归并的集合复制到A中中/end MERGE2022-12-20性能分析性能分析1)过程过程MERGE的归并时间与两数组元素的总数成正比的归并时间与两数组元素的总数成正比 (可表示为可表示为:cn,n为元素数为元素数,c为某正常数为某正常数)2)过程过程MERGESORT的分类时间用递推关系式表示如下的分类时间用递推关系式表示如下:a n=1,a是常数是常数 T(n)=2T(n/2)+cn n1,c是常数是常数化简化简:若若n=2k,则有则有,T(n)=2(2T(n/4)+cn/2)+cn =4T(n/4)+2c
38、n=4T(2T(n/8)+cn/4)+2cn =2kT(1)+kcn =an+cnlogn /k=logn/若若2kn2k+1,则有则有T(n)T(2k+1)。所以得：所以得：T(n)=(nlogn)2022-12-20归并分类示例归并分类示例n设设A=（310，285，179，652，351，423，861，254，450，520）n1）划分过程）划分过程310，285，179，652，351，423，861，254，450，520310，285，179，652，351423，861，254，450，520310，285，179652，351310，285179310285652351423
39、，861，254450，520423，8612544238614505202022-12-202）归并过程）归并过程首先进入左分枝的划分与归并。首先形成的划分状态是：首先进入左分枝的划分与归并。首先形成的划分状态是：（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，652|423，861，2
40、54，450，520）第四次归并第四次归并：（：（179，285，310，351，652|423，861，254，450，520）进入右分枝的划分与归并过程进入右分枝的划分与归并过程（略）（略）2022-12-203）用树结构描述归并分类过程）用树结构描述归并分类过程2022-12-204.4.归并分类算法的改进归并分类算法的改进1）算法）算法4.8存在的问题存在的问题l 递归层次太深递归层次太深 在在MERGESORT的执行过程中，当集合仅含有两个元的执行过程中，当集合仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退
41、出递归调用。素时才退出递归调用。在集合含有仅相当少的元素时，较深层次的递归调用使在集合含有仅相当少的元素时，较深层次的递归调用使得时间得时间过多地消耗过多地消耗在处理递归上。在处理递归上。l 元素在数组元素在数组A和辅助数组和辅助数组B之间的频繁移动之间的频繁移动 每次归并，都要首先将每次归并，都要首先将A中的元素移到中的元素移到B中，在由中，在由B复制复制到到A的对应位置上。的对应位置上。2022-12-20n2）改进措施）改进措施l 针对递归层次问题针对递归层次问题 采用能采用能在小规模集合在小规模集合上有效工作的其它算法，直接对小上有效工作的其它算法，直接对小规模集合处理。规模集合处理。
42、如如INSERTIONSORT算法算法l 针对元素频繁移动问题针对元素频繁移动问题 采用一个称为采用一个称为链接信息数组链接信息数组LINK（1：n）的数据结构，的数据结构，记录归并过程中记录归并过程中A中的元素相对于其排序后在分类表中中的元素相对于其排序后在分类表中位置位置坐标的链接关系。坐标的链接关系。LINK(i)取值于取值于1，n，是指向，是指向A的元素的指针：在分类的元素的指针：在分类表中它指向下一个元素在表中它指向下一个元素在A中的位置坐标。中的位置坐标。2022-12-20例：例：LINK (1)(2)(3)(4)(5)(6)(7)(8)6 4 7 1 3 0 8 0该表中含有该
43、表中含有两个子表两个子表，0表示表的结束。表示表的结束。设置设置表头指针表头指针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)n 链接信息表在归并过程中的应用链接信息表在归并过程中的应用：将归并过程中元素在将归并过程中元素在A和和B之间移动的过程变成更改之间移动的过程变成更改LINK所指示的链接关系，从而避免移动元素的本身。所指示的链接关系，从而避免移动元素的本身。分类表可以通过分类表可
44、以通过LINK的表头指针和读取的表头指针和读取LINK中的链接关中的链接关系取得。系取得。2022-12-20改进后的归并分类模型改进后的归并分类模型算法算法4.10 使用链接信息数组的归并分类模型使用链接信息数组的归并分类模型procedure MERGESORT1(low,high,p)/利用链接信息数组利用链接信息数组LINK(1:n)将全程数组将全程数组A(low:high)按非降次序分类。按非降次序分类。LINK中值表示按分类次序给中值表示按分类次序给出出A下标的表，并把下标的表，并把p置于该表的开始处置于该表的开始处/global A(low:high),LINK(low,high
45、)if high-low+116 /当集合中的元素个数足够少当集合中的元素个数足够少(16)时，采用更有效的小规模集合上的分时，采用更有效的小规模集合上的分类类 算法直接分类算法直接分类/then call INSERTSORT1(A,LINK,low,high,p)/算法算法2.7的改型的改型/else mid call MERGESORT1(low,mid,q)/返回返回q表表/call MERGESORT1(mid+1,high,r)/返回返回r表表/call MERGE1(q,r,p)/将表将表q和表和表r归并成表归并成表p/endifend MERGESORT1high)/2(low
46、2022-12-20算法算法4.11 使用链接表归并已分类的集合使用链接表归并已分类的集合 procedure MERGE1(q,r,p)/q和和r是全程数组是全程数组LINK(1:n)中两个表的指针。归并这两个表，得到一个由中两个表的指针。归并这两个表，得到一个由p所指示的新表。此表将所指示的新表。此表将 A中的元素按非降次序分类。中的元素按非降次序分类。LINK(0)被定义被定义/global n,A(1:n),LINK(1:n)local integer i,j,k iq;jr;k0 /新表在新表在LINK(0)处开始处开始/while i0 and j0 do/当两表均非空时当两表均非
47、空时/if A(i)A(j)/找较小的关键字找较小的关键字/then LINK(k)i;ki;iLINK(i)/加一个新关键字到表加一个新关键字到表中中/else LINK(k)j;kj;jLINK(j)/加一个新关键字到表中加一个新关键字到表中/endif repeat if i=0 then LINK(k)=j else LINK(k)=i endif p=LINK(0)end MERGE12022-12-20MERGESORT1 的调用的调用 在初次调用时，待分类的在初次调用时，待分类的n个元素放于个元素放于A(1:n)中。中。LINK(1:n)初始化为初始化为0；初次调用：初次调用：c
48、all MERGESORT1(1,n,p)p作为按分类次序给出作为按分类次序给出A中元素的指示表的指针。中元素的指示表的指针。3）改进归并分类算法示例）改进归并分类算法示例 设元素表：（设元素表：（50，10，25，30，15，70，35，55）采用采用MERGESORT1对上述元素表分类（不做小规模集对上述元素表分类（不做小规模集合的单独处理）合的单独处理）下表给出在每一次调用下表给出在每一次调用MERGESORT1结束后，结束后，LINK数数组的变化情况。组的变化情况。2022-12-20在上表的最后一行，在上表的最后一行，p=2返回，得到链表（返回，得到链表（2，5，3，4，7，1，8，
49、6）即：即：A(2)A(5)A(3)A(4)A(7)A(1)A(8)A(6)2022-12-205.5.以比较为基础分类的时间下界以比较为基础分类的时间下界 任何以关键字比较为基础的分类算法，其最坏情况下的任何以关键字比较为基础的分类算法，其最坏情况下的时间下界都为：时间下界都为：(nlogn(nlogn)利用利用二元比较树二元比较树证明。证明。假设参加分类的假设参加分类的n n个关键字个关键字A(1),A(2),A(n)A(1),A(2),A(n)互异。任互异。任意两个关键字的比较必导致意两个关键字的比较必导致A(i)A(j)A(i)A(j)A(i)A(j)的结果。的结果。以二元比较树描述元
50、素间的比较过程：以二元比较树描述元素间的比较过程：若若A(i)A(j)A(i)A(j)A(i)A(j)，进入下一级的，进入下一级的右分支右分支2022-12-20 算法在算法在外部结点外部结点终止。终止。从根到某外结点的从根到某外结点的路径路径代表某个特定输入情况下一种唯一的代表某个特定输入情况下一种唯一的分类排序序列分类排序序列。路径长度路径长度表示生成该序列代表的分类表所需要的表示生成该序列代表的分类表所需要的比较次数。比较次数。而而最长的路径最长的路径代表算代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况
