1、2022-5-20第二章 分治法 “分”而治之2.1 一般方法n 对大规模问题的求解 n 利用分治法求解大规模问题 1.基本思想 分而治之方法与软件设计的模块化方法非常相似。为解决一个大问题，可以（1）把它分解分解成两个或多个更小的问题；（2）分别解决分别解决每个小问题；（3）把各小问题的解答组合组合起来，即可得到原问题的解。 小问题通常与原问题相似或同质 ，因而可以递归地使用分而治之策略解决。 2022-5-20通常，子问题与原始问题“同质”2022-5-20例例找伪币找伪币 假设16 枚金币中有一枚是伪造的，真假金币的区别仅是重量不同(伪币轻一些），利用一个没有砝码的天平作工具，找出这枚伪
2、造的金币。 方法1：比较硬币1和2的重量，有一个轻则找到； 否则比较硬币3和4，依次比较下去，直到找到。最多8次比较。方法2：利用分治法。16个硬币分为两组，每组8个，比较重量，伪币在轻的一组。将轻的一组再分为两组，每组4个继续划分下去，依次每组2个，每组1个，此时找到。2022-5-20算法2.1 分治策略的抽象化控制procedure DANDC(p,q) global n.A(1:n); integer m,p,q; /1pqn/ if SMALL(p,q) then return(G(p,q) else mDIVIDE(p,q) /pmq/ return(COMBINE(DANDC(p
3、,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的子问题进一步分解，返回值为p,q区间进一步的分割点（SMALL(p,q)不不为真时）；COMBINE(x,y)：子结果的合并函数，将区间p,m和m+1,q上的子问题的解合并成上级区间p,q上的“较完整”的解。当p=1,q=n时，就得到整个问题的解。2. 分治策略的抽象化控制20
4、22-5-20n DANDC的计算时间 若所分成的两个子问题的输入规模大致相等，则DANDC总的计算时间可用递归关系式表示，如下： g(n) n足够小 T(n) = 2T(n/2) + f(n) 否则 注： T(n)：表示输入规模为n的DANDC计算时间 g(n)：表示对足够小的输入规模直接求解的计算时间 f(n)：表示COMBINE对两个子区间的子结果进行合并 的时间 （该公式针对具体问题有各种不同的变形）2022-5-202.2 二分检索（折半查找）1. 问题的描述 已知一个按非降次序排列的元素表a1, a2, ,an,判定某给定的元素x是否在该表中出现。 若是，则找出x在表中的位置并返回
5、其所在下标 若非，则返回0值。2022-5-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, a2, ,an,x) 对于I2，若ak=x，则有解k，对I1、I3不用再求解；否则， 若xak，则只在I3中求解，对I1不用求解； I1 、I3上的求解可再次采用分治方法划分后求解（递归过程）2022-5-202. 二分检索算法算法2.3 二分检索procedure BINSRCH(A,n,x,j) in
6、teger low,high,mid,j,n; low1; highn; while lowhigh do mid case :xA(mid):low mid+1 :else:jmid;return endcase repeatend BINSRCHhigh)/2(low注： 给定一个按非降次序排列的元素数组A(1:n)，n1,判断x是否出现。若是，置j，使得x=A(j)若非，j=02022-5-20例2.1：设A(1:9)=(-15，-6，0，7，9，23，54，82，101) 在A中检索x=101，-14，82。执行轨迹见下表1表1 运行轨迹示例x=101x=-14x=82lowhighm
7、idlowhighmidlowhighmid19519519569714269789811189899921找不到找到找到成功的检索不成功的检索成功的检索2022-5-203. 算法的正确性证明定理2.1 过程BINSRCH(A,n,x,j)能正确运行证明：1）在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都 能按要求正确运行即首先满足确定性和能行性2）终止性 算法初始部分置low1, highn 若n=0，不进入循环，j置0，算法终止 否则，进入循环，计算mid, 或 x=A(mid)，j置为mid，算法终止； 或xA(mid)，置lowmid+1，进入下次循环；搜索范围实际缩小
8、 为mid+1, high，对low, mid-1区间不做进一步搜索； 因low, high, mid都是整型变量，故按照上述规则，在有限步内，或找到某个mid，有A(mid) = x；或变得lowhigh，在A中没有找到任何元素等于x，算法终止。2022-5-204. 性能分析1）空间特性 n+5个空间位置(n)2) 时间特性 区分以下情况，并进行相应的分析成功检索：所检索的x出现在A中。成功检索情况共有n种：x恰好是A中的某个元素，A中共有n个元素，故有n种可能的情况不成功检索：所检索的x不出现在A中。不成功检索情况共有n+1种：xA(1),或A(i)xA(i+1),1iA(n) 成功/不
9、成功检索的最好情况：执行步数最少，计算时间最短成功/不成功检索的最坏情况：执行步数最多，计算时间最长成功/不成功检索的平均情况：一般情况下的计算时间2022-5-20实例分析（例2.1）n 频率计数特征1. while循环体外语句的频率计数为12. 集中考虑while循环中的x与A中元素的比较（其它运算的频率计数与之有相同的数量级） 假定只需一次比较就可确定case语句控制是三种情况的哪一种。查找每个元素所需的元素比较次数统计如下： A 元素 -15 -6 0 7 9 23 54 82 101成功检索比较次数 3 2 3 4 1 3 2 3 4 不成功检索比较次数 3 3 3 4 4 3 3
10、3 4 42022-5-20n成功检索 最好：1次 最坏：4次 平均：（3+2+3+4+1+3+2+3+4）/92.77次n不成功检索 最好：3次 最坏：4次 平均：(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次2022-5-20二元比较树n算法执行过程的主体是x与一系列中间元素A(mid)比较。可用一棵二元树描述这一过程，并称之为二元比较树。n构造：比较树由称为内结点和外结点的两种结点组成：内结点：表示一次元素比较，用圆形结点表示，存放一个mid值；代表一次成功检索；外结点：在二分检索算法中表示一种不成功检索的情况，用方形结点表示。路 径：表示一个元素的比较序列。例2.1的二
11、元比较树2022-5-20基于二元比较树的分析p 若x在A中出现，则算法的执行过程在一个圆形的内结点处结束。p 若x不在A中出现，则算法的执行过程在一个方形的外结点处结束 外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处结束。 例2.1的二元比较树2022-5-20定理2.2 若n在区域2k-1,2k)中，则对于一次成功的检索，BINSRCH至多做k次比较；对于一次不成功的检索，或者做k-1次比较，或者做k次比较。证明：要点： 成功检索都在内结点处结束，不成功检索都在外结点处结束 当2k-1n2k时，所有内结点在1至k级，所有外结点在第k级 或第k+1级， 故：成功检索在i级终
12、止所需要的元素比较次数是i 不成功检索在i级外部结点终止的元素比较次数是i-12022-5-20BINSRCH计算复杂度的理论分析1）不成功检索的最好、最坏和平均情况的计算时间均为 外结点处在最末的两级上；2）最好情况下的成功检索的计算时间为 最坏情况下的成功检索的计算时间为(logn)(1)(logn)2022-5-203）平均情况下的成功检索的计算时间分析 利用外部结点和内部结点到根距离和之间的关系进行推导： 记， 由根到所有内结点的距离之和称为内部路径长度，记为I； 由根到所有外部结点的距离之和称为外部路径长度，记为E。 则有，E=I+2n 记， U(n)是平均情况下不成功检索的计算时间
13、，则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) = (logn)(logn)2022-5-204. 以比较为基础检索的时间下界问题：设n个元素的数组A(1:n)有A(1) A(2) A(n)。检索一给定元素x是否在A中出现。 定理2.2给出了二分检索算法的时间下界，是否预计还存在有以元素比较为基础的另外的检索算法，它在最坏情况下比二分检索算法在计算时间上有更低的数量级? 以比较为基础的算法：假定算法中只允许进行元素间
14、的比较，而不允许对它们实施其它运算。 2022-5-20注：每个内结点表示一次元素的比较。每棵比较树中恰好含有n个内结点，分别与n个不同i值相对应；每个外结点对应一次不成功的检索，并恰好又n+1个外结点对应于n+1中不成功检索的情况。n任何以比较为基础的检索算法，其执行过程都可以用二元比较树来描述。2022-5-20 以比较为基础的有序检索问题最坏情况的时间下界n定理2.3 设A(1:n)含有 n(n1)个不同的元素，排序为A(1) A(2) max then maxA(i) endif if A(i) max then maxA(i) endif else if A(i) min then
15、minA(i) endif repeatend STRAITMAXMIN1这使得，最好情况：按递增次序排列，元素比较次数为n-1次最坏情况：按递减次序排列，元素比较次数为2(n-1)次平均情况：元素比较次数为3(n-1)/2次2022-5-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) 采用递归的设计策
16、略，得到以下算法：n/2n/2n/2n/22022-5-203. 一种递归求解策略算法2.6 递归求取最大和最小元素procedure MAXMIN(i,j,fmax,fmin) /A(1:n)是含有n个元素的数组，参数i,j是整数，1i,jn / /该过程把A(i:j)中的最大和最小元素分别赋给fmax和fmin / integer i,j;global n,A(1:n) case :i=j: fmaxfminA(i) /只有一个元素 :i=j-1:if A(i)2当n是2的幂时(n=2k),化简上式有， T(n)=2T(n/2) +2 =2(2T(n/22) + 2) + 2 = 22T(
17、n/22 ) + 22 + 2 = 22(2T(n/23 )+2)+22+2 = 23T(n/23 )+23+22+2 = 2k-1T(n/2k-1 ) +(2k-1+22+21) = 2k-1T(2) +(2k-1+22+21) = n/2 + (2k 1 1) = n/2 + n 2 = 3n/2 22)n/2T()n/2T(2022-5-20性能分析1）与STRAITMAXMIN算法相比，比较次数减少了25% （3n/2-2 : 2n-2)。 已经达到了以元素比较为基础的找最大最小元素的算法 计算时间的下界：2）存在的问题： 空间占用量大 有 级的递归，入栈参数： i, j, fmax,
18、 fmin和返回地址五个值。 时间可能不比预计的理想 如果元素A(i)和A(j)的比较与i和j的比较相差不大时，算法MAXMIN不可取。22/3n1logn2022-5-20 假设元素的比较与i和j的比较时间相同（整型数）。又设case语句中仅需一次i和j的比较就能够确定是哪种情况。记此时MAXMIN的频率计数为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算法递归调用的开销，
19、此时MAXMIN算法 的效率可能还不如STRAITMAXMI算法。2022-5-20结论：如果A中的元素间的比较代价远比整型数 （下标）的比较昂贵，则分治方法将产生 一个效率较高的算法； 反之，可能仅得到一个低效的算法。故，分治策略只能看成一个较好的但并不总是成功 的算法设计指导。2022-5-202.4 归并分类1. 分类问题排序 给定一n个元素的集合A，按照某种方法将A中的元素按非降或非增次序排列。 分类：内排序，外排序 常见内排序方法：冒泡排序 插入排序 归并排序 快速排序 堆排序 例 输入：（8，5，4，9）输出：（4，5，8，9）或 （9，8，5，4） 2022-5-202. 插入分
20、类 算法2.7 插入分类 procedure INSERTIONSORT(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-5-20插
21、入分类算法示例n(-,8, 5, 4, 9)j=2i=1item=5item A(i) : 跳出while循环n(-,5, 8, 4, 9)j=3i=2item=4item A(i) : 执行while得 (-,5, 8, 8, 9)i=1item A(i) : 跳出while循环n(-,4, 5, 8, 9)j=4i=3item=9item A(i) : 跳出while循环2022-5-20 性能分析：以比较为基础 最坏情况：输入数据按非增次序排列,每次内层while循环比较执行j次（j=2,3, n)。则有， 最好情况：输入数据已按非降序排列，不进入while循环，则最好情况下计算时间为(
22、n)(n2nj2 1 - 1)/2(n(nj2022-5-203.分治策略求解 基本设计思想：将原始数组A中的元素分成两个子集合：A1(1: )和A2( +1 :n)。分别对这两个子集合单独分类，然后将已分类的两个子序列归并成一个含有n个元素的分类好的序列。 这样的一个分类过程称为归并分类。 n/2n/22022-5-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
23、，285，179652，351310，285179310285652351423，861，254450，520423，8612544238614505202022-5-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
24、| 423，861，254，450，520）第四次归并：（179，285，310，351，652 | 423，861，254，450，520）进入右分枝的划分与归并过程（略）2022-5-203）用树结构描述归并分类过程2022-5-20算法2.8 归并分类 procedure MERGESORT(low,high) /A(low:high)是一个全程数组，它含有high-low+10个待分类的元素/ 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(
25、i) A(k);ii+1; repeat endif for k low to high do A(k) B(k) repeat /将已归并的集合复制到A中/ end MERGE2022-5-20Merge算法示例n(4, 5, 8, 9)|(1, 2, 6, 7) (1, 2, 4, 5, 6, 7, 8, 9)参数：low = 1; high = 8; mid = 4(4, 5, 8, 9)|(1, 2, 6, 7)hjjjjhh(14256789)j2022-5-20性能分析1) 过程MERGE的归并时间与两数组元素的总数成正比 (可表示为:cn, n为元素数,c为某正常数)2) 过程M
26、ERGESORT的分类时间用递推关系式表示如下: a n=1,a是常数 T(n)= 2T(n/2)+cn n1, c是常数化简: 若n=2k,则有, T(n) =2(2T(n/22)+cn/2)+cn = 22T(n/22) + 2cn =22(2T(n/23) +cn/22) + 2cn = 23T(n/23)+3cn = =2kT(1)+kcn =an+cnlogn /k=logn/ 若2kn2k+1,则有T(n)T(2k+1)。所以得：T(n) = (nlogn) 2022-5-204. 归并分类算法的改进1）算法2.8存在的问题l 递归层次太深 在MERGESORT的执行过程中，当集合
27、仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退出递归调用。 在集合含有仅相当少的元素时，较深层次的递归调用使得时间过多地消耗在处理递归上。l 元素在数组A和辅助数组B之间的频繁移动 每次归并，都要首先将A中的元素移到B中，在由B复制到A的对应位置上。2022-5-20n2）改进措施l 针对递归层次问题 采用能在小规模集合上有效工作的其它算法，直接对小规模集合处理。 如INSERTIONSORT算法l 针对元素频繁移动问题 采用一个称为链接信息数组LINK（1：n）的数据结构，记录归并过程中A中的元素相对于其排序后在分类表中位置坐标的链接关系。 LINK(i)取值于1，
28、n，是指向A的元素的指针：在分类表中它指向下一个元素在A中的位置坐标。2022-5-20例： LINK (1) (2) (3) (4) (5) (6) (7) (8) 6 4 7 1 3 0 8 0该表中含有两个子表，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) 链接信息表在归并过程中的应用： 将归并过程中元素在A和B之间移动的过程变成更改LINK所指示的链接关系，从而避免移动元素的本身。 分类表可
29、以通过LINK的表头指针和读取LINK中的链接关系取得。2022-5-20改进后的归并分类模型算法2.10 使用链接信息数组的归并分类模型procedure MERGESORT1(low,high,p) /利用链接信息数组LINK(1:n)将全程数组A(low:high)按非降次序分类。LINK中值表示按分类次序给出A下标的表，并把p置于该表的开始处/global A(low:high),LINK(low,high)if high-low+116 /当集合中的元素个数足够少(16)时，采用更有效的小规模集合上的分类 算法直接分类/ then call INSERTSORT1(A,LINK,lo
30、w,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(low2022-5-20算法2.11 使用链接表归并已分类的集合 procedure MERGE1(q,r,p) /q和r是全程数组LINK(1:n)中两个表的指针。归并这两个表，得到一个由p所指示的新表。此表将 A中的元素按非降次序分类。LINK(0)被定义/ global n
31、,A(1:n),LINK(1:n) local integer i,j,k iq;jr;k0 /新表在LINK(0)处开始/ while i0 and j0 do /当两表均非空时/ if A(i) A(j) /找较小的关键字/ then LINK(k) i;ki;iLINK(i) /加一个新关键字到表中/ else LINK(k) j;kj;jLINK(j) /加一个新关键字到表中/ endif repeat if i=9 then LINK(k) = j else LINK(k) = i endif end MERGE12022-5-20MERGESORT1 的调用 在初次调用时，待分类的
32、n个元素放于A(1:n)中。 LINK(1:n)初始化为0； 初次调用：call MERGESORT1(1,n,p) p作为按分类次序给出A中元素的指示表的指针。3）改进归并分类算法示例 设元素表：（50，10，25，30，15，70，35，55） 采用MERGESORT1对上述元素表分类（不做小规模集合的单独处理） 下表给出在每一次调用MERGESORT1结束后，LINK数组的变化情况。2022-5-20在上表的最后一行，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)ijijkkkjk2022-5-205
33、. 以比较为基础分类的时间下界 任何以关键字比较为基础的分类算法，其最坏情况下的时间下界都为：(nlogn) 利用二元比较树证明。 假设参加分类的n个关键字A(1),A(2),A(n)互异。任意两个关键字的比较必导致A(i)A(j)的结果。 以二元比较树描述元素间的比较过程： 若A(i)A(j)，进入下一级的右分支2022-5-20 算法在外部结点终止。 从根到某外结点的路径代表某个特定输入情况下一种唯一的分类排序序列。路径长度表示生成该序列代表的分类表所需要的比较次数。而最长的路径代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。 故，以比较为基础的分类算法的最
34、坏情况下界等于该算法对应的比较树的最小高度。2022-5-20 由于n个关键字有n!种可能的排列，所以二元比较树中将有n!个外部结点：每种排列对应于某种特定输入情况下的分类情况，每个外部结点表示一种可能的分类序列。 设一棵二元比较树的所有内结点的级数均小于或等于k，则该树中最多有2k个外结点。(引理1.1) 记算法在最坏情况下所作的比较次数为T(n)，则有T(n)=k：生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数-1； 根据和的分析，有： n!2T(n) 化简： 当n1时，有n!n(n-1)(n-2)( )(n/2)n/2 当n4时，有 T(n)(n/2)log(n/2)(n
35、/4)logn 故，任何以比较为基础的分类算法的最坏情况的时间下界为： (nlogn) n/22022-5-202.5 快速分类任何一个基于比较来确定两个元素相对位置的排序算法需要(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare发明的。1. 问题描述 分类问题2.划分 快速分类是一种基于划分的分类方法； 划分：选取待分类集合A中的某个元素t，按照与t的大小关系重 新整理A中元素，使得整理后的序列中所
36、有在t以前出现 的元素均小于等于t，而所有出现在t以后的元素均大于等 于t。这一元素的整理过程称为划分（Partitioning）。元 素t称为划分元素。 快速分类：通过反复地对待排序集合进行划分达到分类目的的分 类算法。2022-5-20划分过程（PARTITION）的算法描述算法2.2 用A(m)划分集合A(m:p-1) procedure PARTITION(m,p) integer m,p,i; global A(m:p-1) vA(m);im /A(m)是划分元素/ loop loop ii+1 until A(i)v repeat / i由左向右移/ loop pp-1 until
37、 A(p)v repeat /p由右向左移/ if ip then call INTERCHANGE(A(i),A(p) else exit endif repeat A(m)A(p)； A(p)v /划分元素在位置p/end PARTITION 2022-5-20注： 算法对集合A(m:p-1)进行划分。并使用待划分区间的第一个元素A(m)作为划分元素 A(p)不在划分区间内，但被定义，且A(p）A(m)，用于限界2022-5-20例2.5 划分实例 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i p A: 65 70 75 80 85 60 55 50
38、 45 + 2 9 | A: 65 45 75 80 85 60 55 50 70 + 3 8 | A: 65 45 50 80 85 60 55 75 70 + 4 7 | A: 65 45 50 55 85 60 80 75 70 + 5 6 | A: 65 45 50 55 60 85 80 75 70 + 6 5 | A: 60 45 50 55 65 85 80 75 70 +划分元素定位于此交换划分元素2022-5-20 经过一次“划分”后，实现了对集合元素的调整：其中一个子集合的所有元素均小于等于另外一个子集合的所有元素。 按同样的策略对两个子集合进行分类处理。当子集合分类完毕后
39、，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类过程称为快速分类。2022-5-203.快速分类 通过反复使用划分过程PARTITION实现对集合元素分类的算法。算法2.13 快速分类 procedure QUICKSORT(p,q) /将数组A(1:n)中的元素A(p),A(q)按递增的方式分类。 A(n+1)有定义，且假定A(n+1)+/ integer p,q;global n,A(1:n) if pq then jq+1 /进入时，A(j)定义了划分区间p,q的上界，初次调用时j=n+1 call PARTITION(p,j) /出口时，j带出此次划分后划分元素所在的
40、坐标位置/ call QUICKSORT(p,j-1) /前一子集合上递归调用 call QUICKSORT(j+1,q) /后一子集合上递归调用 endif end QUICKSORT 2022-5-204. 快速分类分析n统计的对象：元素的比较次数，记为：C(n)n两点假设 参加分类的n个元素各不相同 PARTITION中的划分元素v是随机选取的（针对平均情况的分析）随机选取划分元素： 在划分区间m,p随机生成某一坐标：iRANDOM(m.p-1)； 调换A(m)与A(i):vA(i);A(i) A(m);im作用：将随机指定的划分元素的值依旧调换到A(m)位置。 之后，算法主体不变，仍从
41、A(m)开始执行划分操作。2022-5-20递归层次QuickSort(1,n)QuickSort(1,j1-1)QuickSort(j1+1,n)QuickSort(1,j21-1)QuickSort(j21+1, j1-1)QuickSort(j1+1,j22-1)QuickSort(j22+1,n)n个元素参加划分和分类去掉1个第一级的划分元素n-1个元素参加划分和分类去掉2个第二级的划分元素n-3个元素参加划分和分类去掉4个第三级的划分元素第一层第二层第三层 设在任一级递归调用上，调用PARTITION处理的所有元素总数为r，则，初始时r=n，以后的每级递归上，由于删去了上一级的划分元
42、素，故r比上一级至少1：理想情况，第一级少1，第二级少2，第三级少4， ；最坏情况，每次仅减少1（如集合元素已经按照递增或递减顺序排列）2022-5-20n 最坏情况分析 记最坏情况下的元素比较次数是Cw(n)； PARTITION一次调用中的元素比较数是p-m+1，故每级递归调用上，元素的比较次数等于该级所处理的待分类元素数。 最坏情况下，每级递归调用的元素总数仅比上一级少1，故Cw(n)是r由n到2的累加和。 即：Cw(n)= = (n2)nrr22022-5-20n 平均情况分析 平均情况是指集合中的元素以任一一种顺序排列，且任选所有可能的元素作为划分元素进行划分和分类，在这些所有可能的
43、情况下，算法执行性能的平均值。 设调用PARTITION(m,p)时，所选取划分元素v恰好是A(m:p-1)中的第i小元素（1ip-m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是A(m:j-1)和A(j+1:p-1)的概率是：1/(p-m), mjp。则有， 其中， n+1是PARTITION第一次调用时所需的元素比较次数。 CA(0) = CA(1) = 0 nkAAnAknCkCnnC11)() 1(1)(2022-5-20化简上式可得： CA(n)/(n+1) = CA(n-2)/(n-1)+2/n+2/(n+1) = CA(n-3)/(n-2)+2(n-1)+2/n+
44、2/(n+1) = CA(1)/2+由于所以得，CA(n)2(n+1)loge(n+1) = (nlogn)13/12nkk) 1(log/11213nkenxdxnk2022-5-205. 快速分类算法的迭代模型n消去递归（略）6. 快速分类与归并分类比较两者平均情况时间都是(nlogn），平均情况下哪种快一些？实验证明快速分类要快一些2022-5-202.6 选择问题1. 问题描述 给出含有n个元素表A(1:n)，要求确定其中的第k小元素。2. 设计思路 利用PARTITION过程。如果划分元素v测定在A(j)的位置上，则有j-1个元素小于或等于A(j)，且有n-j个元素大于或等于A(j)
45、。此时， 若k=j，则A(j)即是第k小元素；否则， 若kj，则第k小元素将出现在A(j+1:n)中。2022-5-203. 利用PARTITION实现的选择算法n算法描述 算法2.15 找第k小元素 procedure SELECT(A,n,k) /在数组A(1:n)中找第k小元素，并将之放在A(k)中。/ integer n,k,m,r,j; m1;r n+1;A(n+1) + /A(n+1)被定义，并置为一大值，用于限界/ loop /在进入循环时，1mkrn+1 / j r /将剩余元素的最大下标加1后置给j / call PARTITION(m.j) /返回j,它使得A(j)是第j小
46、的值/ case :k=j: return :kj, j+1是新的下界/ endcase repeat end SELECT2022-5-20n 算法分析 两点假设 A中的元素互异 随机选取划分元素，且选择A中任一元素作为划分元 素的概率相同 分析 每次调用PARTITION（m,j),所需的元素比较次数是 (j-m+1)。 在执行一次PARTITION后，或者找到第k小元素，或者将 在缩小的子集(A(m,k-1)或A(k+1,j)中继续查找。缩小 的子集的元素数将至少比上一次划分的元素数少1。2022-5-201) 最坏情况 SELECT的最坏情况时间是(n2) 当A中的元素已经按照递增的顺
47、序排列， 且k=n。此时，需要n次调用PARTITION过程，且每次返回的元素位置是子集中的第一个元素，子集合的元素数一次仅减少，而j值不变。 则,n次调用的时间总量是)() ) 1(21nin2022-5-202)平均情况 设 是找A(1:n)中第k小元素的平均时间。 是SELECT的平均计算时间，则有并定义则有：T(n)R(n)。nkkAnAnTnT11)()()(nTAkkAnTnR)(max)()(nTkA定理2.4 SELECT的平均计算时间TA(n)是(n)2022-5-204. 最坏情况是(n)的选择算法1）采用两次取中间值的规则精心选取划分元素 首先，将参加划分的n个元素分成
48、组，每组有r个元素(r1)。（多余的 个元素忽略不计） 然后，对这 组每组的r个元素进行分类并找出其中间元素mi,1i ，共得 个中间值。 之后，对这 个中间值分类，并找出其中间值mm。将mm作为划分元素执行划分。2）算法描述n/rn/rrnn/rn/rn/rn/r2022-5-20算法2.16 使用二次取中规则得选择算法的说明性描述 /在集合A中找第k小元素，使用两次取中规则/ 若nr，则采用插入法直接对A分类并返回第k小元素 把A分成大小为r的 个子集合，忽略多余的元素 设M=m1,m2,m 是 子集合的中间值集合 vSELECT2(M, , ) jPARTITION(A，v) /v作为划
49、分元素，划分后j等于划分元素所在位置的下标/ case :k=j: return(v) :kj: 设S是A(1:j-1)中元素的集合 return(SELECT2(S,k,j-1) :else: 设R是A(j+1:n)中元素的集合 return(SELECT2(R,k-j,n-j) endcase end SELECT2n/rn/rn/r2/n/r2022-5-20n例：设 n=35, r=7。 分为n/r = 5个元素组：B1，B2，B3，B4，B5；每组有7个元素。 B1-B5按照各组的mi的非增次序排列。 mm = mi的中间值，1i5由图所示有：mm中间值小于等于mm的元素大于等于mm
50、的元素非降次序B1 B2 B3 B4 B5按照mi的非降次序排列2022-5-20 由于r个元素的中间值是第 小元素。则， 至少有 个mi小于或等于mm； 至少有 个mi大于或等于mm。 则，至少有 个元素小于或等于（或大于或等于）mm。 当r=5，则使用两次取中间值规则来选择v=mm，可推出， 至少有 个元素小于或等于选择元素v。 至多有 个元素大于v。 至多有 0.7n+1.2个元素小于v。 故，这样的v可近似平均地划分A中的n个元素。/2n/r1/2n/rn/r2/n/r2/r /2n/rr/2n/55 . 11.20.7nn/51.5n2022-5-202) 算法分析 记T(n)是SE
