算法分析第四章

1、1第四章第四章分治法分治法24.1 一般方法一般方法4.2 二分检索二分检索4.3 找最大和最小元素找最大和最小元素4.4 归并分类归并分类4.5 快速分类快速分类4.6 选择问题选择问题4.7 斯特拉森矩阵乘法斯特拉森矩阵乘法主要内容主要内容3输入规模相当大时，直接求解很困难。输入规模相当大时，直接求解很困难。分析问题的特征，选择适当的设计策略。分析问题的特征，选择适当的设计策略。将一个难以直接解决的大问题，分割成一些规模将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。较小的相同问题，以便各个击破，分而治之。4.1 一般方法一般方法4分治法的思想分治法的思想

2、: 将一个输入规模为将一个输入规模为n的问题分解为的问题分解为k个规模较小的子问题，这些子问题互相独立且与个规模较小的子问题，这些子问题互相独立且与原问题性质相同，求出这些子问题解后，可以用原问题性质相同，求出这些子问题解后，可以用适当的方法将各子问题的解合并成原问题的解。适当的方法将各子问题的解合并成原问题的解。问题问题(n个输入个输入)子问题子问题1子问题子问题2子问题子问题k子问题子问题1子问题子问题2子问题子问题k相同类型相同类型合并解合并解5步骤：步骤：分（分（divide）二分为主二分为主多分比二分更好吗？多分比二分更好吗？ 治（治（conquer）递归调用，当规模足够小时直接处理

3、递归调用，当规模足够小时直接处理 合（合（combine）4.1 一般方法一般方法6分治策略分治策略DANDC的抽象化控制的抽象化控制procedure DANDC(p,q)global n, A(1:n); integer m, p, q; /1 p q n/if SMALL(p,q) then return(G(p,q) else mDIVIDE(p,q) return(COMBINE (DANDC(p,m), DANDC(m+1,q)endifend DANDC判断输入规模判断输入规模q p+1是否足够小是否足够小,可直接求解可直接求解G是直接求解该规模问题的函数是直接求解该规模问题的函

4、数分割函数分割函数, p m q, 原问题被分为原问题被分为A(p:m)和和A(m+1:q)两个子问题两个子问题合并函数合并函数,将两个子问题的解合并为原问题的解将两个子问题的解合并为原问题的解原问题为原问题为A(1:n) , 最初调用函数应该是最初调用函数应该是DANDC(1, n); DANDC(p, q)是计算是计算A(p: q)子问题的解子问题的解.4.1 一般方法一般方法7二分策略二分策略DANDC的计算时间的计算时间倘若所分成的两个子问题的输入规模大致相等倘若所分成的两个子问题的输入规模大致相等,则分治策略则分治策略DANDC的计算时间可表示为：的计算时间可表示为： 说明：说明：T

5、(n)：输入规模为：输入规模为n时，分治策略的计算时间时，分治策略的计算时间g(n)：对足够小的输入规模能直接计算出答案的时间：对足够小的输入规模能直接计算出答案的时间f(n)：COMBINE函数合成原问题解的计算时间函数合成原问题解的计算时间g(n)n足够小足够小2T(n/2)+f(n)否则否则T(n)=4.1 一般方法一般方法8一个分治法将规模为一个分治法将规模为n的问题分成的问题分成k个规模为个规模为n/m的子问题去解。的子问题去解。设分解阈值设分解阈值n0=1，且解规模为，且解规模为1的问题需耗费常数时间。再设将的问题需耗费常数时间。再设将原问题分解为原问题分解为k个子问题以及将个子问

6、题以及将k个子问题的解合并为原问题的个子问题的解合并为原问题的解需用解需用f(n) 时间。用时间。用T(n)表示该分治法解规模为表示该分治法解规模为|P|=n的问题所的问题所需的计算时间，则有：需的计算时间，则有：11)()/() 1 ()(nnnfmnkTOnT通过迭代法求得方程的解：通过迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT注意注意：递归方程及其解只给出递归方程及其解只给出n等于等于m的方幂时的方幂时T(n)的值，但的值，但是如果认为是如果认为T(n)足够平滑，那么由足够平滑，那么由n等于等于m的方幂时的方幂时T(n)的值的值可以估计可以估计T(n)的增

7、长速度。通常假定的增长速度。通常假定T(n)是单调上升的，从是单调上升的，从而当而当minmi+1时，时，T(mi)T(n)T(mi+1). 9问题描述问题描述: 已知一个按已知一个按非降序排列非降序排列的元素表的元素表a1, a2, , an , 判定某个给定元素判定某个给定元素x是否在该表中出现，若是是否在该表中出现，若是, 则找则找出该元素在表中的位置出该元素在表中的位置,并将下标值赋给并将下标值赋给j, 否则置否则置j为为0.二分检索原理二分检索原理将将二分检索二分检索问题表示为：问题表示为：I=(n, a1, , an, x)选取一个下标选取一个下标k，可得到三个子问题：，可得到三个

8、子问题：vI1=(k 1, a1, , ak-1, x)vI2=(1, ak , x)vI3=(n k, ak+1, , an, x)4.2 二分检索二分检索对所求解的问题（或子问题）所选的下标都是对所求解的问题（或子问题）所选的下标都是中间元素的下标：中间元素的下标：k= (n+1) /2 10procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low1; highn while low high do mid (low+high)/2 /*取中间值取中间值*/ case :xA(mid): lowmid+1 /*在后一半寻

9、找在后一半寻找*/ : else: jmid; return; /*检索成功检索成功, 结束结束*/ endcase repeat j0 /*检索失败检索失败*/end BINSRCH二分检索算法二分检索算法11检索检索x=9, 9=A(5), 一次比较就成功一次比较就成功, 最好情况最好情况 15 6079235482101A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9)检索检索x= 15, 15A(5), 15A(5), 101A(7), 101A(8), 101= A(9), 4次比较次比较, 成功成功检索检索x=8, 8A(2), 8A(3),

10、8A(4), 4次比较次比较, 不成功检索不成功检索二分检索实例二分检索实例:设在设在A(1:9)中顺序放了以下中顺序放了以下9个元素：个元素：12用五个特性判断是否是一个算法用五个特性判断是否是一个算法证明算法正确性证明算法正确性n假定：比较运算能恰当地执行，过程中所有的语假定：比较运算能恰当地执行，过程中所有的语句按要求工作句按要求工作n初始状态：初始状态：low=1, high=n, n 0, A(1) A(n).nn=0nn0二分检索算法正确性证明：二分检索算法正确性证明：13二分检索算法所需的空间和时间二分检索算法所需的空间和时间v所需空间所需空间: 用用n个位置存放数组个位置存放数

11、组A，还有，还有low, high, mid, x, j五个五个 变量需要存储，变量需要存储，共需空间共需空间 n+5v所需计算时间所需计算时间: 对于计算时间，需要分别考虑以下几种情况：对于计算时间，需要分别考虑以下几种情况： 成功检索成功检索的最好情况、平均情况、最坏情况的最好情况、平均情况、最坏情况 不成功检索不成功检索的最好情况、平均情况、最坏情况的最好情况、平均情况、最坏情况4.2 二分检索二分检索14-15-6079235482101A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9)3234132343334433344成功检索有成功检索有n种

12、情况，不成功检索有种情况，不成功检索有n+1种情况种情况成功：成功：不成功：不成功：不论检索是否成功，算法的执行过程都是不论检索是否成功，算法的执行过程都是x与一系列与一系列中间元素中间元素A(mid)的比较过程，可以用一棵二元比较的比较过程，可以用一棵二元比较树来描述算法的执行过程。树来描述算法的执行过程。15二元比较树二元比较树内结点内结点表示一表示一次元素的比较次元素的比较,存放一个存放一个mid值值外结点外结点表示不成功表示不成功检索的一种情况检索的一种情况592-61-1530754476238829101一条路径表一条路径表示一个元素示一个元素的比较序列的比较序列4.2 二分检索二

13、分检索16二分检索的时间复杂度二分检索的时间复杂度定理定理4.2: 若若n在区域在区域2k- -1, 2k)中，则对于一次成功的检中，则对于一次成功的检索，二分检索算法至多作索，二分检索算法至多作k次比较，而对于一次不成次比较，而对于一次不成功的检索，或者作功的检索，或者作k 1次比较或者作次比较或者作k次比较。次比较。4.2 二分检索二分检索证明：考察二分检索算法执行过程的二元比较树：证明：考察二分检索算法执行过程的二元比较树：成功检索内结点，不成功检索外结点成功检索内结点，不成功检索外结点由于由于2k 1 n 2k,内结点级数内结点级数 k，外结点级数，外结点级数 k+1 成功检索所需要的

14、元素比较次数成功检索所需要的元素比较次数=级数级数，不成功检索所需要的元素比较次数不成功检索所需要的元素比较次数=级数级数 1.17二分检索的时间复杂度二分检索的时间复杂度对前面二分检索实例对前面二分检索实例n=9, n 23, 24), 已分析过成功检已分析过成功检索和不成功检索的各种情况下的比较次数索和不成功检索的各种情况下的比较次数 4, 易知易知: (logn)(logn)(logn)(logn)(logn)(1)不成功的检索不成功的检索成功的检索成功的检索最坏情况最坏情况平均情况平均情况最好情况最好情况计算时间计算时间4.2 二分检索二分检索内部路径长度内部路径长度I：由根到所有内部

15、结点的距离之和：由根到所有内部结点的距离之和外部路径长度外部路径长度E：由根到所有外部结点的距离之和：由根到所有外部结点的距离之和18关于确切比较次数的讨论：关于确切比较次数的讨论：BINSRCH的的case语句：元素比较次数的假定不合语句：元素比较次数的假定不合理，但对时间的近似表示无影响。理，但对时间的近似表示无影响。实际上可以用实际上可以用if语句替代语句替代BINSRCH相应相应case语句语句If xA(mid) then low mid+1 else j mid; return endifendif 每次循环固定一次比较的每次循环固定一次比较的BINSRCH1算法算法Case:xA

16、(mid): lowmid+1 : else: jmid; return; endcase19procedure BINSRCH1(A, n, x, j) integer low, high, mid, j, n; low1; highn+1 / high总比可能的取值大总比可能的取值大1 / while lowhigh 1 do mid (low+high)/2 if xA(mid) then highmid else lowmid / x A(mid) / endif repeat if x=A(low) then jlow / 检索成功检索成功 / else j0 / 检索失败检索失败

17、/ endifend BINSRCH二分检索算法二分检索算法20检索检索x=9, low=1, high=10, mid=5, x=9 A(5)=9; low=5, high=10, mid=7, x=9 A(7)=54; low=5, high=7, mid=6, x=9 A(6)=23; low=5, high=6, low=high-1,退出退出while循环循环; x=A(5), j=low=5, 程序结束程序结束. 15 6079235482101A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9)二分检索实例二分检索实例:设在设在A(1:9)中顺

18、序放了以下中顺序放了以下9个元素：个元素：21以比较为基础检索的时间下界以比较为基础检索的时间下界思考思考: 对于已排序的对于已排序的n个元素个元素, 检索某元素检索某元素x是否出现是否出现, 是否存在以比较为基础的检索算法是否存在以比较为基础的检索算法, 在在最坏情况最坏情况下该下该算法比二分检索算法在计算时间上有算法比二分检索算法在计算时间上有更低的数量级更低的数量级?对于以比较为基础的检索算法的分析，采取构建二对于以比较为基础的检索算法的分析，采取构建二元比较树的方式。元比较树的方式。22二元比较树二元比较树-顺序检索顺序检索n个元素存在如下关系的个元素存在如下关系的:A(1)A(2)A

19、(n),检检索一给定元素索一给定元素x是否在是否在A中出现中出现x:A(1)x:A(2)x:A(n)不成功不成功不成功不成功不成功不成功不成功不成功线性检索线性检索23二元比较树二元比较树-二分检索二分检索X:A( (n+1)/2 )X:A( 3(n+1)/4 )X:A( (n+1)/4 )X:A(n)X:A( (n+1)/2 +1)X:A( (n+1)/2 -1)X:A(1)不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功24以比较为基础检索的时间下界以比较为基础检索的时间下界v定理定理4.3: 设设A(1:n)含有含有n(n 1)个不同的元素

20、，排序个不同的元素，排序为为A(1)A(2)max then max Ai; if Aimax then max=Ai;else if Aimin then min=Ai;v直接算法的时间复杂度在最好、最坏、平均情况下均为直接算法的时间复杂度在最好、最坏、平均情况下均为2(n- -1)改进后的计算时间改进后的计算时间:(元素升序元素升序)最好情况为最好情况为(n-1)(元素降序元素降序)最坏情况为最坏情况为2(n-1)平均情况为平均情况为3/2(n-1)改进改进26采用分治策略求最大最小元素采用分治策略求最大最小元素I=(n,A(1),A(n)划分为划分为I1=( n/2 ,A(1),A( n

21、/2 ) )I2=( n- n/2 ,A( n/2 +1 ),A(n) )结果的合并结果的合并27分治法求最大和最小元素分治法求最大和最小元素procedure MAXMIN( i, j, fmax, fmin)int i, j; global n, A(1:n);case i= j: fmax fmin Ai i= j- -1: if Ai212210nnjj4.3 找最大和最小元素找最大和最小元素30可以证明可以证明: 任何一种以比较为基础的找最大和最小元任何一种以比较为基础的找最大和最小元素的算法，其元素比较次数的下界为素的算法，其元素比较次数的下界为 3n/2 - -2但是不代表该算法

22、最优，理由如下：但是不代表该算法最优，理由如下：MAXMIN算法分析算法分析vMAXMIN所需的存储空间比直接算法多所需的存储空间比直接算法多4.3 找最大和最小元素找最大和最小元素给出给出n个元素，则个元素，则MAXMIN算法有算法有 logn +1级的递归，级的递归，每次递归都需要保存每次递归都需要保存i, j, fmax, fmin和返回地址和返回地址5个值个值直接算法需要空间为直接算法需要空间为: n+3, 用用n个位置存放数组个位置存放数组A，还有还有i, max, min三个变量需要存储三个变量需要存储31v元素元素A(i)和和A(j)的比较与的比较与i和和j的比较时间相差不大时，

23、的比较时间相差不大时，过程过程MAXMIN不可取。不可取。 设设MAXMIN的频率计数为的频率计数为C(n)，n=2k , k为整数为整数, 当当n2时时, 有有: C(n)=5n/2-3 4.3 找最大和最小元素找最大和最小元素C(n)= 2C(n/2)+3 = 2(2C(n/4)+3)+3 = 4C(n/4)+6+3 = 2k-1C(2)+3*( 2k-2 +2k-3+22+21+20 ) =2k+3*(2k-1-1) =2k+3*2k-1-3 =5n/2-32 n=2C(n)=2C( n/2 )+ 3 n212210nnjj32v直接算法的比较次数为直接算法的比较次数为2(n-1), 加

24、上实现加上实现for循环循环 需要的比较次数需要的比较次数, 则为则为3(n-1), 虽然虽然3(n-1)略大于略大于 5n/2-3, 但但MAXMIN算法还有递归所带来的时间算法还有递归所带来的时间 开销开销, 这种情况下直接算法要快一些这种情况下直接算法要快一些结论结论: 如果数组如果数组A的元素之间的比较远比整型的元素之间的比较远比整型变量的比较代价昂贵，则分治法产生效率较高变量的比较代价昂贵，则分治法产生效率较高的算法；反之则得到一个效率较低的程序。的算法；反之则得到一个效率较低的程序。4.3 找最大和最小元素找最大和最小元素33 直接方法直接方法(插入法插入法)for j2 to n

25、 do将将A(j)放入已分类集合放入已分类集合A(1:j 1)repeat4.4 归并分类归并分类问题描述问题描述: 给定一个含有给定一个含有n个元素的集合，个元素的集合， 把它们按一定的次序分类把它们按一定的次序分类(如非降次序如非降次序)34procedure INSERTIONSORT(A, n)A(0) for j 2 to n do item A(j); i j 1; while ( itemA(i) do A(i+1) A(i); ii 1; repeat A(i+1) item;repeat end INSERTIONSORT插入分类算法描述插入分类算法描述数组元素的比较和移动数

26、组元素的比较和移动将本次考虑的元素将本次考虑的元素插入相应位置插入相应位置可能执行可能执行0j次次(j=2,3n)最好情况最好情况 (n)最坏情况的计算时间：最坏情况的计算时间：2+n=(n(n+1)/2) 1= (n2)用用item保存保存当前元素值当前元素值4.4 归并分类归并分类35分：平均分为分：平均分为2个子集合个子集合治：递归调用分类算法，将治：递归调用分类算法，将2个子集合分类个子集合分类合：将合：将2个分类的子集合并为一个分类集合个分类的子集合并为一个分类集合4.4 归并分类归并分类分治策略设计归并分类算法分治策略设计归并分类算法36递归调用，分别对分解递归调用，分别对分解出来

27、的两个子问题排序出来的两个子问题排序合并两个已排好的序合并两个已排好的序列，得到原问题的解列，得到原问题的解归并排序算法描述归并排序算法描述Procedure MERGESORT(low,high)int low, high, mid;if (lowmid) then for kj to high do B(i)A(k);i i+1 else for kh to mid do B(i)A(k);ii+1 for k low to high do A(k) B(k);end MERGE处理两个已处理两个已分类的序列分类的序列剩余元素剩余元素处理过程处理过程将已分类的集合复制到将已分类的集合复制到

28、A数组数组4.4 归并分类归并分类38MERGESORT执行过程执行过程1,54,51,35,54,43,31,21,12,2表示一次调用时的表示一次调用时的low和和high的值的值只含单个元只含单个元素的子集合素的子集合1, 1, 24, 4, 51, 2, 31, 3, 5表示表示MERGE调用时调用时low, mid, high 的值的值4.4 归并分类归并分类39A(1)A(2)A(3)A(4)A(5)310285179652351low=1; mid=1; high=2; h=1; i=1; j=2; while (h mid and j high) do if A(h) A(j)

29、 then else B(i)A(j); jj+1=3 ; ii+1=2; B(1)B(2)B(3)B(4)B(5)285310285310if (hmid) then else for k=1 to 1 do B(i)A(h); ii+1=3; for k=1 to 2 do A(k)B(k); 4.4 归并分类归并分类40low=1; mid=2; high=3; h=1; i=1; j=3; while (h mid and j high) do if A(h) A(j) then else B(i)A(j); jj+1=4 ii+1=2; if (hmid) then else for

30、 k=h to mid do B(2)A(k);ii+1=3 B(3)A(k); ii+1=4 for k=1 to 3 do A(k)B(k);A(1)A(2)A(3)A(4)A(5)285310179652351B(1)B(2)B(3)B(4)B(5)1792853101792853104.4 归并分类归并分类41low=4; mid=4; high=5; h=4; i=4; j=5; while (h mid and j high) do if A(h) A(j) then else B(i)A(j); jj+1=6 ii+1=5; for k=4 to 5 do A(k)B(k); i

31、f (hmid) then else for k=4 to 4 do B(5)A(4); ii+1=6; A(1)A(2)A(3)A(4)A(5)179285310652351B(1)B(2)B(3)B(4)B(5)3516523516524.4 归并分类归并分类42low=1; mid=3; high=5; h=1; i=1; j=4; while (h mid and j high) do if A(h) A(j) then B(i)A(h); hh+1=2 ; ii+1=2; if (hmid) then for k=4 to 5 do B(4)A(4); ii+1=5 for k=1

32、to 5 do A(k)B(k); B(5)A(5); ii+1=6 if A(h) A(j) then B(i)A(h); hh+1=4 ; ii+1=4; if A(h) A(j) then B(i)A(h); hh+1=3 ; ii+1=3; A(1)A(2)A(3)A(4)A(5)179285310351652B(1)B(2)B(3)B(4)B(5)1792853103516521792853103516524.4 归并分类归并分类43归并分类的计算时间归并分类的计算时间T(n)=a n=1 , a是常数是常数2T(n/2)+cn n1 , c是常数是常数当当 n=2k时，可得时，可得

33、T(n)=2(2T(n/4)+cn/2)+cn = 22T(n/4)+2cn = 22(2T(n/8)+cn/4)+2cn = 23T(n/8)+3cn = 2kT(1)+kcn = an+cnlogn如果如果2kn2k+1，有有T(n) T(2k+1)则有则有T(n)=O(nlogn)归并归并2个子数组所需的元素个子数组所需的元素比较次数在比较次数在n/2到到n-1之间之间4.4 归并分类归并分类44归并分类算法的缺点归并分类算法的缺点缺点缺点1: 当子集合的元素很少时，算法的很多时间消耗当子集合的元素很少时，算法的很多时间消耗 在递归的处理上。在递归的处理上。改进改进: 当子集合的元素个数

34、适当少时，采用在小规模当子集合的元素个数适当少时，采用在小规模 集合上能有效工作的集合上能有效工作的插入分类算法进行排序，插入分类算法进行排序，而不是继续划分，以此而不是继续划分，以此克服上述缺点带来的时克服上述缺点带来的时间消耗。间消耗。缺点缺点2: 辅助数组辅助数组B的使用增加了算法的空间，且每次的使用增加了算法的空间，且每次 调用调用MERGE时，都需要将时，都需要将B中的结果复制回中的结果复制回A 中，消耗了一部分时间。中，消耗了一部分时间。改进改进: 用一个用一个链接数组链接数组LINK(1:n)代替代替B，LINK中的中的 元素为元素为A中元素的下标，它指示下一个元素所在中元素的下

35、标，它指示下一个元素所在 的下标位置。的下标位置。4.4 归并分类归并分类45关于关于LINK数组数组LINK(1:n)为一链接数组，取值范围为为一链接数组，取值范围为1, 2, , n。可看成是可看成是A元素的指针，在分类表中它指向下一个元素的指针，在分类表中它指向下一个元素所在的下标位置，用元素所在的下标位置，用0表示结束。表示结束。实例实例: 下面是一个下面是一个LINK集合，包含了两个已分类的集合，包含了两个已分类的 子集合。子集合。q和和r表示两个子集合的起始处表示两个子集合的起始处:q=2,r=5(1) (2) (3) (4)(5)(6)(7)(8)34018706q=2的表为的表

36、为(2, 4, 1, 3) A(2) A(4) A(1) A(3)r=5的表为的表为(5, 8 , 6, 7) A(5) A(8) A(6) A(7)(1) (2) (3) (4)(5)(6)(7)(8)4332693523588946数组数组A:数组数组LINK:4.4 归并分类归并分类46procedure MERGESORT1(low, high, p)global A(low:high), LINK(low:high)if (high low+116 ) then call INSERTIONSORT(A, LINK, low, high, p);else mid (low+high)

37、/2 ; call MERGESORT1(low, mid, q); call MERGESORT1(mid+1, high, r); call MERGE1(q, r, p);endif end MEGESORT1改进的归并分类算法改进的归并分类算法当集合元素小于当集合元素小于16时时, 调用修改调用修改的插入分类算法的插入分类算法归并分类归并分类递归调用递归调用合并两个子问题的解合并两个子问题的解4.4 归并分类归并分类47使用使用LINK数组的归并函数数组的归并函数procedure MERGE1(q, r, p)global n, A(1:n), LINK(0:n); int i, j

38、, k;i q; j r; k 0;while (i 0 and j 0) do if (A(i) A(j) then LINK(k)i;ki;iLINK(i); else LINK(k)j;kj;jLINK(j);if (i=0) then LINK(k)j; else LINK(k)i;pLINK(0);end MERGE1当当q和和r非空时进行以下非空时进行以下操作操作: 加入一个关键字加入一个关键字的下标到的下标到LINK数组中数组中处理剩下的关键字处理剩下的关键字4.4 归并分类归并分类48(1) (2) (3) (4)(5)(6)(7) (8)5010253015703555数组数

39、组A:MSORT1(1, 8, p)if (8-1+15 ) then ISTSORT(A,LINK,1,8,p);else mid= (1+8)/2=4 ; MSORT1(1, 4, q); MSORT1(5, 8, r); MERGE1(q, r, p);end MSORT1 MSORT1(1, 4, q)if (4-1+15 ) then ISTSORT(A,LINK,1,4,p);end MSORT1 返回返回q=2MSORT1(5, 8, r)if (8-5+15 ) then ISTSORT(A,LINK,5,8,p);end MSORT1 返回返回r=5MERGE1(2,5,p)

40、;(0) (1) (2) (3) (4)(5)(6)(7) (8)000000000数组数组LINK:034170864.4 归并分类归并分类2 549(0)(1)(2)(3)(4)(5)(6)(7)(8)003417086数组数组LINK:MERGE1(2, 5, p)i=2; j=5; k=0;while (i 0 and j 0) do if (A(2) A(5) then LINK(0)=2; k=2; i=LINK(2)=3; 2534718(1) (2) (3) (4)(5)(6)(7) (8)5010253015703555if (A(3) A(5) else LINK(2)=5

41、; k=5; j=7; if (A(3) A(7) then LINK(5)=3; k=3; i=4; if (A(4) A(7) then LINK(3)=4; k=4; i=1; if (A(1) A(7) else LINK(4)=7; k=7; j=8; if (A(1) A(8) then LINK(7)=1; k=1; i=0; if (i=0) then LINK(1)=8;p=LINK(0)=2;4.4 归并分类归并分类504.4 归并分类归并分类讨论：讨论：1. 可以消去递归，取消栈的使用，例如：可以消去递归，取消栈的使用，例如： 采用由底向上的方法，将元素两两配对；采用由底

42、向上的方法，将元素两两配对； 自然合并排序法；自然合并排序法；2. 空间代价空间代价3. 适合于并行计算，采用并行或专用集成电路实现数据排序适合于并行计算，采用并行或专用集成电路实现数据排序操作时，派生出许多算法，例如奇偶合并排序，双调合并操作时，派生出许多算法，例如奇偶合并排序，双调合并排序等。排序等。(1) (2) (3) (4)(5)(6)(7)(8)501025301570355551(1) (2) (3) (4)(5)(6)(7) (8)5010253015703555(1)50(2)(3)(4)102530(5)(6)1570(7)(8)3555(1) (2) (3)(4)1025

43、3050(5)(6)(7) (8)15355570(1) (2) (3) (4)(5)(6)(7) (8)1015253035505570首先首先 对数组对数组A进行进行一遍扫描一遍扫描, 找出所有找出所有已排序的子数组段已排序的子数组段然后将相邻的子数然后将相邻的子数组段两两合并组段两两合并, 重复重复这种合并过程这种合并过程, 直到直到整个数组排好序整个数组排好序4.4 归并分类归并分类52 任何以关键字比较为基础的分类算法，最坏情况任何以关键字比较为基础的分类算法，最坏情况下的时间下界都是下的时间下界都是 (nlogn)，因此从数量级的角度上因此从数量级的角度上看看, 归并分类是归并分类

44、是最坏情况下的最优算法最坏情况下的最优算法。采用二元比较树证明采用二元比较树证明以比较为基础分类的时间下界以比较为基础分类的时间下界4.4 归并分类归并分类53对对3个关键字分类的二元比较树个关键字分类的二元比较树1:21:31:32:32:31,2,31,3,23,1,22,1,32,3,13,2,1A(1)A(2)A(2)A(3)A(1)A(3)A(2)A(3)A(1)A(3)表示一表示一次比较次比较一种可能的一种可能的分类序列分类序列54 2T(n) 叶结点实际数叶结点实际数 n!满二叉树满二叉树 n关键词全排列关键词全排列n1时，时，n! (n/2) n/2n 4有，有，T(n) (n

45、/2)log (n/2) (n/4)log nT(n) = (n log n)最坏情况下比较次数最坏情况下比较次数=比较树的最长路径比较树的最长路径=根到最远叶结点距离根到最远叶结点距离=树高树高T(n)4.4 归并分类归并分类554.5 快速分类快速分类快速分类的基本思想：快速分类的基本思想：选取数组选取数组A中的某个元素中的某个元素 t=As，然后将其他元素，然后将其他元素 重新排列，使重新排列，使A中所有在中所有在t以前出现的元素都小于以前出现的元素都小于或等于或等于t，而在，而在t之后出现的元素都大于或等于之后出现的元素都大于或等于t。这这个重新整理的过程称为划分，个重新整理的过程称为

46、划分，t称为划分元素。称为划分元素。A1A2As-1AsAs+1An划分元素划分元素t经过一次经过一次划分后划分后A1A2AjtAkAn每个元素都小于或等于每个元素都小于或等于t每个元素都大于或等于每个元素都大于或等于t564.5 快速分类快速分类快速分类实例快速分类实例A1A2A3A4A5A6A75392718 第第1次划分，选次划分，选t=A1，即，即t=5，划分后得到如下结果：，划分后得到如下结果： A1A2A3A4A5A6A72315798 第第2次划分，选次划分，选t=A1，即，即t=2，划分后结果：，划分后结果： A1A2A3A4A5A6A71235798 第第3次划分，选次划分，

47、选t=A5，即，即t=7，划分后没有变化，划分后没有变化 第第4次划分，选次划分，选t=A6，即，即t=9，划分后结果：，划分后结果： A1A2A3A4A5A6A71235798A1A2A3A4A5A6A71235789574.5 快速分类快速分类procedure QUICKSORT(low,high)int low,high; global n, A(1:n)if lowhigh then jhigh+1 call PARTITION(low, j) call QUICKSORT(low, j-1) call QUICKSORT(j+1, high) endifend QUICKSORT快

48、速分类算法快速分类算法划分划分A(low,high), 函数执函数执行完后行完后, j返回划分元素返回划分元素的下标的下标递归调用划递归调用划分之后得到分之后得到的两个集合的两个集合584.5 快速分类快速分类PARTITION划分过程的实现划分过程的实现procedure PARTITION(m, p)int m,p,i; global A(m:p-1)vAm; im;loop loop ii+1 until Aiv ; loop pp- -1 until Apv ; if (ip) then call INTERCHANGE(Ai, Ap) else exitrepeatAmAp; Apv

49、;end PARTITION交换交换Ai和和Ap结束过程时结束过程时, 参数参数p中的值为划分元中的值为划分元素所在位置的下标素所在位置的下标, 该值将带回该值将带回, 用用于后面的于后面的QUICKSORT过程过程i从左向右移，直到从左向右移，直到Ai t p从右向左移，直到从右向左移，直到Apt59首先调用首先调用QUICKSORT(1,7) /low=1,high=7if 17 then j=8; call PARTITION(1, 8); call QUICKSORT(low, j-1) call QUICKSORT(j+1, high) end QUICKSORT4.5 快速分类快速

50、分类快速分类实例分析过程快速分类实例分析过程等等PARTITION(1, 8)调调用结束后用结束后,返回参数返回参数j的的值值,才能执行递归调用才能执行递归调用PARTITION(m, p) /m=1, p=8t=Am=5; i=m=1;loop(第第1次次) loop i+ until Ait ; i=3 loop p- until Apt ; p=6 if (ip) then Ai Ap; A1 A2 A3 A4A5A6A75392718A1 A2 A3 A4A5A6A75312798604.5 快速分类快速分类Am=Ap; 即即A1=A4=2Ap=t; 即即A4=5end / p=4的值

51、带回的值带回loop(第第2次次,i=3,p=6) loop i+ until Ait ; i=5 loop p- until Apt ; p=4 if (i p) 执行执行else exit loop1 A1 A2 A3 A4A5A6A75312798A1A2A3A4A5A6A72315798递归调用递归调用QUICKSORT(low, j-1) 即即QUICKSORT(1, 3)递归调用递归调用QUICKSORT(j+1,high) 即即QUICKSORT(5, 7)61快速分类算法的分析快速分类算法的分析 I ：时间复杂性时间复杂性假设前提假设前提互不相同；随机选取划分元素互不相同；随机

52、选取划分元素划分单元随机选取的改进划分单元随机选取的改进快速分类的性能取决于划分的对称性！快速分类的性能取决于划分的对称性！随机选取更合理，因为最好能找到中间元素随机选取更合理，因为最好能找到中间元素最坏情况下：最坏情况下：划分算法比较次数为元素数划分算法比较次数为元素数:p-m+1:p-m+1第第i i级的比较次数：级的比较次数：n-i+1 (n-i+1 (实际上是固定的实际上是固定的) )最坏情况下级数为最坏情况下级数为n-1(n-1(每次取最小或最大值）每次取最小或最大值） 总和：总和：n+(n-1)+= O(nn+(n-1)+= O(n2 2) )平均情况下：平均情况下：划分元素最终位置机会均等，划分元素最终位置机会均等，运用概率公式得：运用概率公式得：62 快速分类算法的分析快速分类算法的分析 II ：栈空间使用：栈空间使用递归算法：最坏情况下递归算法：最坏情况下 O(n) O(n) 改进的迭代算法：改进的迭代算法：每次选择小的文件继续处理每次选择小的文件继续处理（较小的文件在处理过程中相对迭代次数少，可能（较小的文件在处理过程中相对迭代次数少，