递归与分治策略.ppt

第2章 递归与分治策略,本章主要内容,2.1 递归的概念 2.2 分治法的基本思想 2.3 二分搜索技术 2.4 大整数的乘法 2.5 Strassen矩阵乘法 2.7 合并排序 2.8 快速排序 2.11 循环赛日程表,2.1 递归的概念,2.1.1 递归的概念 直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 在计算机算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。 使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（如C语言、Pascal语言等）使用递归算法要耗用更多的栈空间，应避免采用。 一般的的递归算法都可以改写成与之等价的非递归算法。,2.1 递归的概念,2.1.2 递归的几个实例 例1 阶乘函数（理解） 可以递归地定义为： 其中： n=0时，n!=1 为边界条件 n0时，n!=n(n-1)! 为递归方程 边界条件与递归方程是递归函数的二个要素，只有具备这两个要素，才能在有限次计算后得出结果。,2.1 递归的概念,若乘法执行次数记作M(n)，则有如下结论： M(n)没有定义为n的函数，而是定义它本身在另一点上值的函数，这种等式称为递推关系，或递推式。 用反向替换法求解递推关系式：,M(n) = M(n-1)+1 替换 M(n-1)=M(n-2)+1 = M(n-2)+1 + 1 = M(n-2)+2 替换 M(n-2)=M(n-3)+1 = M(n-3)+1 + 1 = M(n-3)+3 = M( n-i ) + i = M(n-n)+n=n,2.1 递归的概念,例2 斐波那契数列（理解） Fibonacci Sequence 黄金分割数列,兔子繁殖问题 1202年，意大利数学家斐波那契(Fibonacci)在他的算盘书中提出这样一个问题：有人想知道一年内一对兔子可繁殖成多少对，便筑了一道围墙把一对兔子关在里面。已知一对兔子每一个月可以生一对小兔子，而一对兔子出生后第二个月就开始生小兔子。假如一年内没有发生死亡，则一对兔子一年内能繁殖成多少对？,2.1 递归的概念,表示一对成熟的兔子； 表示未成熟的兔子。 每一对成熟的兔子经过一个月变成本身的及新生的未成熟； 未成熟的一对经过一个月变成成熟的，没有出生新兔； 画出左图。,2.1 递归的概念,在数学上，斐波那契数列是以递归的方法来定义： 第n个Fibonacci数可递归地计算如下：,2.1 递归的概念,斐波那契数列一般表达式的初等代数解法 已知 a1 = 1，a2 = 1，an = an 1 + an 2 首先构建等比数列 令 0， 0, 设an + an 1 = (an 1 + an 2) 化简得 an = ( )an 1 + an 2 比较系数可得 解得,2.1 递归的概念,预知后事如何变换. 参见维基百科斐波那契数列 /zh-cn/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97,2.1 递归的概念,斐波那契数列的通项公式为（又叫“比内公式”，是用无理数表示有理数的一个范例） 可它的每一项却都是整数。开普勒发现两个斐波那契数的后两项比会趋近黄金分割： 这个数列有广泛的应用，如树的年分枝数目就遵循斐波那契数列的规律；而且计算机科学的发展，为斐波那契数列提供了新的应用场所。,2.1 递归的概念,斐波那契的另一种表示法,2.1 递归的概念,2.1 递归的概念,前面定义的递归算法效率并不高，为什么？,F(5),F(4),F(3),F(3),F(2),F(2),F(1),F(1),F(0),F(2),F(1),F(1),F(0),F(1),F(0),数列的递归调用树,Fib(n) /输入：非负整数n /输出：第n个斐波那契数 Create F0n F0=1;F1=1 for i=2 to n do Fi=Fi-1+Fi-2 return F(n),2.1 递归的概念,例3 Ackerman函数（了解） 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 前两例都能找到函数的非递归定义，但Ackerman函数却无法找到(?但是有非递归的算法)。 Ackerman函数A(n,m)定义如下：,2.1 递归的概念,A(n,m)的自变量m的每个值都定义了一个单变量函数 M=0时：A(n,0)=n+2 M=1时： A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2 A(1,1)=2 故A(n,1)=2*n (n=1) M=2时： A(n,2)=A(A(n-1,2),1)=2A(n-1,2) A(1,2)=A(A(0,2),1)=A(1,1)=2 故A(n,2)= 2n 。 M=3时，类似的可以推出 ，2的层数为n M=4时，A(n,4)的增长速度非常快，没有适当的数学式子来表示这一函数。,2.1 递归的概念,定义单变量的Ackerman函数A(n)为，A(n)=A(n,n)。 定义其拟逆函数(n)为 (n)=minkA(k)n 即(n)是使nA(k)成立的最小的k值。 A(0)=1, A(1)=2, A(2)=4, A(3)=16, A(4)=溢出 推知(1)=0, (2)=1, (3)= (4)= 2, (5)= =(16)=3. (n)在复杂度分析中常遇到。 对于通常所见到的正整数n，有(n)4。 但在理论上(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。,2.1 递归的概念,例4 排列问题（理解） 全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排列数为n!个。 设计一个递归算法生成n个元素r1,r2,rn的全排列（所有元素按不同顺序所有的组合）。 以1, 2, 3, 4, 5为例说明全排列的递归算法。 先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头和5的全排列和以5开头和4的全排列。 再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、4 3 5、4 5 3、5 3 4、5 4 3 六组数。即以3开头和45的全排列的、以4开头和35的全排列和以5开头和34的全排列。,2.1 递归的概念,根据以上分析，可有如下递归定义 设R=r1,r2,rn是待排列的n个元素，Ri=R-ri。 集合X中元素的全排列记为Perm(X)。 (ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀得到的排列。 R的全排列可归纳定义如下： 当n=1时，Perm(R)=(r)，其中r是集合R中唯一的元素； 当n1时，Perm(R)由(r1)Perm(R1)，(r2)Perm(R2)，(rn)Perm(Rn)构成。,2.1 递归的概念,2.1 递归的概念,2.1 递归的概念,例5 整数划分问题（了解） 将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。 正整数n的这种表示称为正整数n的划分。 求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 6 5+1 4+2，4+1+1 3+3，3+2+1，3+1+1+1 2+2+2，2+2+1+1，2+1+1+1+1 1+1+1+1+1+1,2.1 递归的概念,前面问题本身都有明显递归关系，容易求解。 本例中，若设p(n)为正整数n的划分数，难以找到递归关系； 增加一个变量：将最大加数n不大于m的划分个数记作q(n,m)。q(n,m)有如下递归关系： q(n,1)=1，n1 当最大数n1时，任何正整数n只有一种划分形式：n=1+1+.+1（共n个）。 q(n,m)=q(n,n)，mn 最大加数n 实际上不能大于n。 q(1,m)=1。,2.1 递归的概念,q(n,n)=1+q(n,n-1) 正整数n的划分由 n=n的划分和nn-1的划分组成。 q(n,m)=q(n,m-1)+q(n-m,m),nm1 正整数n的最大加数n不大于m的划分由 n=m的划分和nm-1 的划分组成。 计算q(n,m)的递归式如下，可以发现 p(n)=q(n,n),2.1 递归的概念,相传.,印度北部贝拿勒斯圣庙里 一块黄铜板上插着三根宝石针，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片： 一次只移动一片 不管在哪根针上 小片必须在大片上面 僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。,假如这个传说是真的！,2012年？ 假设有n片，移动次数是f(n)。 显然f(1)=1，f(2)=3，f(3)=7，且f(k+1)=2*f(k)+1。 即f(n)=2n-1。 n=64时 f(64)= 264-1=18446744073709551615 假如每秒钟一次，平均每年31556952秒，则18446744073709551615/31556952 =584554049253.855年 =5845亿年以上,2.1 递归的概念,例6 Hanoi塔问题（理解） 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。 各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。 在移动圆盘时应遵守以下移动规则： 每次只能移动1个圆盘； 任何时刻都不允许将较大的圆盘压在较小的圆盘上； 在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。,2.1 递归的概念,解法 为了把n1个盘子从木桩1移到木桩3，需要把n-1个盘子递归的移到木桩2（借助3）； 然后把最大的盘子（第n个）移到木桩3； 再把n-1个盘子由木桩2移动到木桩3（借助1）。,2.1 递归的概念,移动次数为M(n)，n为盘子数量，则有如下递推式 M(1)=1 M(n)=M(n-1)+1+M(n-1)， n1 建立如下递推关系： M(1)=1 M(n)=2M(n-1)+1， n1 使用反向替换法求解： M(n)=2M(n-1)+1 =22M(n-2)+1+1=22M(n-2)+2+1 =222M(n-3)+1+2+1=23M(n-3)+22+2+1 =2iM(n-i)+2i-1+2i-2+2+1= 2iM(n-i)+2i-1,2.1 递归的概念,由于初始条件是n=1，所以i=n-1，求解递推式： M(n)=2n-1M(n-(n-1)+2n-1-1 =2n-1M(1)+2n-1-1=2n-1 这是一个指数级的算法，但是，对于此问题来说，这是最高效的算法。,2.1 递归的概念,递归算法 /hanoi(n, a, b, c)表示将塔座a上自下而上、由大到小叠放的n个圆盘依规则移动到b上，移动过程中以c为辅助塔座。 /move(a,b)表示将a上编号为n的圆盘移动到b上 public static void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); ,2.1 递归的概念,递归小结 优点 结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点 递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 解决方法 在递归算法中消除递归调用，使其转化为非递归算法。,2.1 递归的概念,采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。 用递推来实现递归函数。,总之， 递归式一种优雅的算法。 但我们应该谨慎使用递归算法，因为它们的简洁可能会掩盖它们的低效率。,2.2 分治法（Divide-Conquer）,分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。 对k个子问题分别求解。若子问题的规模仍然不够小，再划分为k个子问题，如此递归进行，直到问题规模足够小，容易求解为止。 分治法对于并行计算是非常理想的。,凡治众如治寡，分数是也。 孙子兵法,2.2 分治法的基本思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。,2.2 分治法的基本思想例,伪币问题 给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。 提供一台可用来比较两组硬币重量的仪器，可比较硬币的重量是否相同。,2.2 分治法的基本思想例,笨办法 比较硬币1与2的重量。假如硬币1比2轻，则1是伪造的；假如2比1轻，则硬币2是伪造的；假如两硬币重量相等，则比较硬币 3和硬币4按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。 分治 把1 6个硬币的问题分成两个8硬币的问题来解决。一次比较即可判断是否存在伪币。 两个（三个？）硬币的情况作为不可再分的小问题。需要几步可找出伪币？,2.2 分治法的基本思想例,金块问题 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。 如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。 假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。,2.2 分治法的基本思想例,通常 假设袋中有n 个金块。可以用函数Max通过n-1次比较找到最重的金块 ，从余下的 n-1个金块中用类似的方法通过 n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。,需要2n-2次比较,2.2 分治法的基本思想例,分而治之 用二叉树来表示。叶子表示8个金块（a, b, h)，每个阴影节点表示一个包含其子树中所有叶子的问题。因此，根节点A表示寻找8个金块中最轻、最重金块的问题 1 把大问题划分成许多个小问题，小问题的大小为1或2。 2 比较每个大小为2的问题中的金块，确定哪一个较重和哪一个较轻。 3 对较轻的金块进行比较以确定哪一个金块最轻，对较重的金块进行比较以确定哪一个金块最重。,2.2 分治法的基本思想例,金块比较问题复杂度 设c(n)为使用分而治之方法所需要的比较次数。为了简便，假设 n是2的幂。 当n= 2时，c(n) = 1。对于较大的 n，递归关系 c(n) = 2c(n/2) + 2 求解得c(n) = 3n/2 2 在本例中，使用分而治之方法比逐个比较的方法少用了25的比较次数。,2.2 分治法的基本思想,分治法的适用条件 分治法所能解决的问题一般具有以下几个特征： 问题规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 利用分解出的子问题的解可合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,2.2 分治法的基本思想,分治法的基本步骤（伪码描述） divide-and-conquer(P) if ( | P | = n0) adhoc(P); / n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。adhoc(P)为基本子算法。 divide P into smaller sub-instances P1,P2,.,Pk;/分解 for (i=1;i=k;i+) yi=divide-and-conquer(Pi); /递归求解子问题 return merge(y1,.,yk); /合并子问题解为原问题解 ,2.2 分治法的基本思想,子问题平衡 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。 这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,2.2 分治法的基本思想,分治法的复杂性分析 一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值n0=1，且adhoc(P)解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。 用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有如下递推式：,2.2 分治法的基本思想,通过迭代法求得方程解： 注意 递归方程及其解只给出n等于m的方幂时T(n)的值 通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。,2.3 二分搜索技术,给定已按升序排好序的n个元素a0:n-1，要在这n个元素中找出一特定元素x。 适用分治法求解问题的基本特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。 很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的适用条件。,2.3 二分搜索技术,二分搜索（折半查找） 二分查找例(70?) 二分查找明显基于递归思想，但可以非递归实现。,2.3 二分搜索技术,二分查找非递归伪代码,BinarySearch(A0n-1,K) /非递归折半查找 /输入：升序数组A和查找键K /输出：数组下标，该元素等于K；若没有，返回-1 l=0;r=n-1 while l=r do m= (l+r)/2 if K=Am return m else if KAm r=m-1 else l=m+1 return -1,2.3 二分搜索技术,二分搜索C+代码： public static int BinarySearch(int a, int x, int n) / 在 a0 amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x ,2.3 二分搜索技术,T(1) = 1 T(2) = T(1)+1 = 2 T(4) = T(2)+1 = 3 T(8) = T(4)+1 = 4 T(n) = T(2m) = T(2m-1)+1 = m+1 = log2n+1 =O(logn),算法复杂度分析 每执行一次算法的while循环， 待搜索数组的大小减少一半。 最坏情况下，while循环被执行了O(logn) 次。 循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。,令n=2m m=0 m=1 m=2 m=3,2.4 大整数的乘法,密码技术常要对超过100位的十进制数进行乘法运算，需作特别处理。 计算两数乘法，例如23*14 23=2*101+3*100 , 14=1*101+4*100 23*14=(2*101+3*100)*(1*101+4*100) =2*1*102+(3*1+2*4)101 +(3*4)100 对于任何两位数a=a1a0和b=b1b0，乘积c为 c=a*b=c2102+c1*101+c0 其中： c2=a1*b1 , c0=a0*b0 c1=(a1+a0)*(b1+b0)-(c2+c0),2.4 大整数的乘法,设计一个有效的算法，可以进行两个n位大整数的乘法运算 分治法: X=A2n/2+B Y=C2n/2+D XY =AC2n+(AD+BC)2n/2+BD =c2*2n+c1*2n/2+c0 其中，c2、c1、c0采用相同的方法计算。 如果n是2的乘方，就是一个计算两个n位数乘积的递归算法。,2.4 大整数的乘法,复杂性分析 n位数的乘法运算需要对n/2位做三次乘法运算，乘法次数M(n)的递推式为： M(n)=3M(n-1),n1 M(1)=1 当b=2k时，用反向替换法求解： M(2k) =3M(2k-1)=32M(2k-2) =3iM(2k-i)=3kM(2k-k)=3k 因为k=log2n，所以 M(n)=3log2n=nlog23n1.585,alogbc=clogba,2.4 大整数的乘法,更快的方法 传统方法：O(n2)效率太低 分治法: O(n1.585)较大的改进 更快的方法？ 如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。 最终这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。 是否能找到线性时间的算法？目前还没有结果。,2.5 Strassen矩阵乘法,矩阵乘法 V.Strassen在1969年发表的矩阵乘法算法。 nn矩阵A和B的乘积矩阵C中的元素Ci,j定义为 则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。 算出矩阵C的 个元素所需的计算时间为O(n3)。,2.5 Strassen矩阵乘法,首先假定n是2的幂。将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为： 由此可得： 复杂度分析 T(n)=O(n3) ，对于2阶方阵，须计算8次乘法，4次加法，没有改进。,2.5 Strassen矩阵乘法,为了降低时间复杂度，必须减少乘法的次数。而其关键在于计算2个2阶方阵的乘积时所用乘法次数能否少于8次。 为此，Strassen提出了一种只用7次乘法运算计算2阶方阵乘积的方法（但增加了加/减法次数）： M1=A11(B12-B22) M2=(A11+A12)B22 M3=(A21+A22)B11 M4=A22(B21-B11) M5=(A11+A22)(B11+B22) M6=(A12-A22)(B21+B22) M7=(A11-A21)(B11+B12) 做了这7次乘法后，在做若干次加/减法就可以得到： C11=M5+M4-M2+M6 C12=M1+M2 C21=M3+M4 C22=M5+M1-M3-M7,2.5 Strassen矩阵乘法,复杂度分析 设M(n)为计算两个n阶方阵相乘执行的乘法的次数（其中n是2的乘方），有如下递推关系 M(1)=1 M(n)=7M(n/2) 因为n=2k M(2k) =7M(2k-1)=72M(2k-2)= =7iM(2k-i)=7kM(2k-k)=7k 因为k=log2n， 所以M(n)=7log2n=nlog27n2.807 O(n2.807) O(n3)，较大的改进。,2.5 Strassen矩阵乘法,更快的算法 Hopcroft和Kerr已经证明(1971)，计算2个22矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究33或55矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。 目前最好的计算时间上界是 O(n2.376) 是否能找到O(n2)的算法？目前为止还没有结果。,2.7 合并排序,基本思想 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 递归算法描述,Mergesort(A0n-1) /递归调用Mergesort对数组A0n-1排序 /输入：可排序数组A0n-1 /输出：非降序排列的数组A0n-1 if n1 copy A0 n/2 -1 to B0 n/2 -1 copy A n/2 n-1 to C n/2 n-1 Mergesort( B0 n/2 -1 ) Mergesort( C n/2 n-1 ) Merge(B,C,A),2.7 合并排序,基本思想 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 递归算法描述,Merge (B0p-1,C0q-1,A0p+q-1) /将两个有序数组合并为一个有序数组 /输入：两个有序数组B0p-1,C0q-1 /输出：合并B、C形成的有序数组A0p+q-1 i=0;j=0;k=0 while ip and jq do if BiCj Ak=Bi; i=i+1 else Ak=Cj; j=j+1 k=k+1 if i=p copy Cj q-1 to Ak p+q-1 else copy B ip-1 to A kp+q-1,2.7 合并排序,合并排序的例子,2.7 合并排序,复杂度分析 键值比较此数C(n)的递推关系式为 Cmerge(n)为合并元素键值比较此数。最坏情况下（如最小元素轮流来自不同数组）Cmerge(n)=n-1 Cworst(n)=2Cworst(n/2)+n-1 Cworst(1)=0 若n=2k，最差递推式的精确解为Cworst=nlog2n-n+1 所以合并排序是O(nlogn) 渐进意义下的最优算法。,2.8 快速(划分)排序,2.8 快速排序,基于分治策略的另一个排序算法，基本思想是： 分解 以aq为基准元素将ap:r划分成3段ap:q-1、aq和aq+1:r，使得ap:q-1中任何元素小于aq ，aq+1:r中任何元素大于aq ； 下标q在划分过程中确定。 递归求解 递归调用快速排序算法对ap:q-1和aq+1:r进行排序； 合并 对ap:q-1和aq+1:r的排序是就地进行的，ap:q-1和aq+1:r排好序后不需要执行任何计算，ap:r就已排好序。,2.8 快速排序,快速算法描述： template void QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); /对左半段排序 QuickSort (a,q+1,r); /对右半段排序 ,2.8 快速排序,分解/划分算法描述： template/以确定基准元素ap对子数组ap:r划分 int Partition (Type a, int p, int r) int i = p, j = r + 1; Type x=ap; / 将 x的元素交换到右边 while (true) while (a+i x); if (i = j) break; Swap(ai, aj); ap = aj; aj = x; return j; ,以x=ap作为划分基准，分别从左右两端开始扩展两个区域ap:i和aj:r，使ap:i中元素小于等于x，aj:r中