算法设计与分析 第2章

1、 学习要点学习要点:理解递归的概念。理解递归的概念。掌握设计有效算法的分治策略。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；）二分搜索技术； （2）大整数乘法；）大整数乘法；（3）棋盘覆盖；）棋盘覆盖；（4）合并排序和快速排序；）合并排序和快速排序；（5）循环赛日程表。）循环赛日程表。n将要求解的较大规模的问题分割成k个更小规模的子问题。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= n对这对这k k个子问题分别求解。如果子问题的规模仍然不够个子问题分别求解。如果子问题的规模仍然不够小，则再划分为小，则再

2、划分为k k个子问题，如此递归的进行下去，直个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。到问题规模足够小，很容易求出其解为止。n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) n将求出的小规模的问题的解合并为一个更大规模的问将求出的小规模的问题的解合并为一个

3、更大规模的问题的解，自底向上逐步求出原来问题的解。题的解，自底向上逐步求出原来问题的解。n将求出的小规模的问题的解合并为一个更大规模的问将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n

4、/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的设计思想是，将一个难以直接解决的大分治法的设计思想是，将一个难以直接解决的大问题，问题，分割成一些规模较小的相同问题分割成一些规模较小的相同问题，以便各个击，以便各个击破，破，分而治之分而治之。 分而治之方法法与软件设计的模块化方法非常相分而治之方法法与软件设计的模块化方法非常相似。为解决一个大问题，可以（似。为解决一个大问题，可以（1 1）把它分解成两个或）把它分解成两个或多个更小的问题；（多个更小的问题；（2 2）分别解决每个小问题；（）分别解决每个小问题；（3 3）

5、把各小问题的解答组合起来，即可得到原问题的解。把各小问题的解答组合起来，即可得到原问题的解。 小问题通常与原问题相似或同质小问题通常与原问题相似或同质 ，因而可以递归，因而可以递归地使用分而治之策略解决。地使用分而治之策略解决。 2.1 n直接或间接地调用自身的算法称为直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为用函数自身给出定义的函数称为递归函数递归函数。n由分治法产生的子问题往往是原问题的较小模由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与情况下

6、，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。致递归过程的产生。n分治与递归像一对孪生兄弟分治与递归像一对孪生兄弟，经常同时应用在，经常同时应用在算法设计之中，并由此产生许多高效算法。算法设计之中，并由此产生许多高效算法。下面来看几个实例。2.1 例例1 1 阶乘函数阶乘函数 阶乘函数可递归地定义为阶乘函数可递归地定义为：10!(1)!0nnn nn=- 边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素，递归

7、函边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出数只有具备了这两个要素，才能在有限次计算后得出结果结果。2.1 例例2 Fibonacci2 Fibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程10( )11(1)(2)1nF nnF nF nn=-+- 第n个Fibonacci数可递归地计算如下：int fibonacci(int n) if (n =2) return (n+2);return akm(akm(n-1,m),m-1);2

8、.1 例例4 4 排列问题排列问题设计一个递归算法生成设计一个递归算法生成n n个元素个元素rr1 1,r,r2 2,r,rn n 的全排列。的全排列。设设R=rR=r1 1,r,r2 2,r,rn n 是要进行排列的是要进行排列的n n个元素，个元素，R Ri i=R-r=R-ri i 。集合集合X X中元素的全排列记为中元素的全排列记为perm(X)perm(X)。(r(ri i)perm(X)perm(X)表示在全排列表示在全排列perm(X)perm(X)的每一个排列前加上前的每一个排列前加上前缀得到的排列。缀得到的排列。R R的全排列可归纳定义如下：的全排列可归纳定义如下： 当当n=

9、1n=1时，时，perm(R)=(r)perm(R)=(r)，其中，其中r r是集合是集合R R中唯一的元素；中唯一的元素；当当n1n1时，时，perm(R)perm(R)由由(r(r1 1)perm(R)perm(R1 1) )，(r(r2 2)perm(R)perm(R2 2) )，(r(rn n)perm(R)perm(Rn n) )构成。构成。 程序清单程序清单2.1 例例5 5 整数划分问题整数划分问题将正整数将正整数n n表示成一系列正整数之和：表示成一系列正整数之和：n=nn=n1 1+n+n2 2+n+nk k，其中其中n n1 1nn2 2nnk k11，k1k1。正整数正整

10、数n n的这种表示称为正整数的这种表示称为正整数n n的划分。求正整数的划分。求正整数n n的不的不同划分个数。同划分个数。 例如正整数例如正整数6 6有如下有如下1111种不同的划分：种不同的划分： 6 6； 5+15+1； 4+24+2，4+1+14+1+1； 3+33+3，3+2+13+2+1，3+1+1+13+1+1+1； 2+2+22+2+2，2+2+1+12+2+1+1，2+1+1+1+12+1+1+1+1； 1+1+1+1+1+11+1+1+1+1+1。例例5 整数划分问题整数划分问题n下面介绍一种通过递归方法得到一个正整数的划分数。n 递归函数的声明为 int split(in

11、t n, int m);其中n为要划分的正整数，m是划分中的最大加数(当m n时，最大加数为n)，n 1、当n = 1或m = 1时，split的值为1，可根据上例看出，只有一个划分1 或 1 + 1 + 1 + 1 + 1 + 1n 可用程序表示为: if(n = 1 | m = 1) return 1;例例5 整数划分问题整数划分问题n2、下面看一看m 和 n的关系。它们有三种关系n (1) m nn 在整数划分中实际上最大加数不能大于n，因此在这种情况可以等价为split(n, n);n 可用程序表示为: if(m n) return split(n, n); n (2) m = nn

12、这种情况可用递归表示为split(n, m - 1) + 1，从以上例子中可以看出，就是最大加数为6和小于6的划分之和n 用程序表示为: if(m = n) return (split(n, m - 1) + 1);例例5 整数划分问题整数划分问题n(3) m m) return (split(n, m - 1) + split(n - m), m);(2) q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。(1) q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即111nn =+ (4) q(n,m)=q(n,m-1)+q

13、(n-m,m), nm1;(4) q(n,m)=q(n,m-1)+q(n-m,m), nm1;正整数正整数n n的最大加数的最大加数n n1 1不大于不大于m m的划分由的划分由n n1 1=m=m的划分和的划分和n n1 1m-1 m-1 的划分组成。的划分组成。例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。而容易用递归函数直接求解。在本例中，如果设在本例中，如果设p(n)p(n)为正整数为正整数n n的划分数，则难以找到递归关的划分数，则难以找到递归关系，因此考虑增加

14、一个自变量：将最大加数系，因此考虑增加一个自变量：将最大加数n n1 1不大于不大于m m的划分个的划分个数记作数记作q(n,m)q(n,m)。可以建立。可以建立q(n,m)q(n,m)的如下递归关系。的如下递归关系。(3) q(n,n)=1+q(n,n-1);(3) q(n,n)=1+q(n,n-1);正整数正整数n n的划分由的划分由n n1 1=n=n的划分和的划分和n n1 1n-1n-1的划分组成的划分组成。11,1( , )( ,)1( ,1)( ,1)(,)1nmq n nnmq n mq n nnmq n mq nm mnm=例例5 5 整数划分问题整数划分问题前面的几个例子中

15、，问题本身都具有比较明显的递归关系，因前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。而容易用递归函数直接求解。在本例中，如果设在本例中，如果设p(n)p(n)为正整数为正整数n n的划分数，则难以找到递归关的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数系，因此考虑增加一个自变量：将最大加数n n1 1不大于不大于m m的划分个的划分个数记作数记作q(n,m)q(n,m)。可以建立。可以建立q(n,m)q(n,m)的如下递归关系。的如下递归关系。正整数正整数n n的划分数的划分数p(n)=q(n,n)p(n)=q(n,n)。 例例5 整数划分问

16、题整数划分问题n int split(int n, int m)n n if(n 1 | m 1) return 0;n if(n = 1 | m = 1) return 1;n if(n m) return (split(n, m - 1) + split(n - m), m);n n在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面

17、。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 2.1 2.1 例例6 Hanoi6 Hanoi塔问题塔问题设设a,b,ca,b,c是是3 3个塔座。开始时，在塔座个塔座。开始时，在塔座a a上有一叠共上有一叠共n n个圆盘，这个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为为1,2,n,1,2,n,现要求将塔座现要求将塔座a a上的这一叠圆盘移到塔座上的这一叠圆盘移到塔座b b上，并仍上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：

18、按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则规则1 1：每次只能移动：每次只能移动1 1个圆盘；个圆盘；规则规则2 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则规则3 3：在满足移动规则：在满足移动规则1 1和和2 2的前提下，可将圆盘移至的前提下，可将圆盘移至a,b,ca,b,c中中任一塔座上。任一塔座上。在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较

19、小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。2.1 例例6 Hanoi6 Hanoi塔问题塔问题 void hanoi(int n, char a, char b, char c) if (n 0) hanoi(n-1, a, c, b);/把a上n-1个盘子借助b移到c上 move(a,b); hanoi(n-1, c, b, a); n汉诺塔问题汉诺塔

20、问题nvoid Move(char x, char y)n /将第将第n个圆盘从塔座个圆盘从塔座x移到塔座移到塔座y的顶部的顶部ncout The disk is moved from n x y endl; n2.1 程序n思考：n移动次数和n的关系？2.1 优点：优点：结构清晰，可读性强，而且容易用结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。为设计算法、调试程序带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比耗费的计算时间还是

21、占用的存储空间都比非递归算法要多。非递归算法要多。解决方法：解决方法：在递归算法中消除递归调用，使其在递归算法中消除递归调用，使其转化为非递归算法。转化为非递归算法。1 1、采用一个用户定义的栈来模拟系统的递归调、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，归，只不过人工做了本来由编译器做的事情，优化效果不明显。优化效果不明显。2 2、用递推来实现递归函数。、用递推来实现递归函数。3 3、通过变换能将一些递归转化为非递归，从而、通过变换能将一些递归转化为非递归，从而迭代求出结果。迭

22、代求出结果。 后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均有较大改善，但其适用范围有限。但其适用范围有限。n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；n该问题可以分解为若干个规模较小的相同问题，即该该问题可以分解为若干个规模较小的相同问题，即该问题具有问题具有最优子结构性质最优子结构性质n利用该问题分解出的子问题的解可以合并为该问题的利用该问题分解出的子问题的解可以合并为该问题的解；解；n该问题所分解出的各个子问题是相互独立的，即子问该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。题之间不包含公共的子

23、问题。 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P in

24、to smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i 注意注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。 分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是

25、在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。 分析：很显然此问题分解出的子问题相互独立，即在很显然此问题分解出的子问题相互独立，即在ai的前的前面或后面查找面或后面查找x是独立的子问题，因此满足分治法的第四个适是独立的子问题，因此满足分治法的第四个适用条件。用条件。给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以

26、分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。 给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。据此容易设计出据此容易设计出二分搜索算法二分搜索算法：template int BinarySearch(Type a , const Type& x, int n) int left=0; int right=n-1;/在在a0=a1=

27、an-1中搜索中搜索x /找到找到x时返回其在数组中的位置，否则返回时返回其在数组中的位置，否则返回-1 while (left amiddle) left= middle+1; else right = middle-1; return -1;/未找到未找到x 算法复杂度分析：算法复杂度分析：每执行一次算法的每执行一次算法的while循环，循环， 待搜待搜索数组的大小减少一半。因此，在最索数组的大小减少一半。因此，在最坏情况下，坏情况下，while循环被执行了循环被执行了O(logn) 次。因此整个算法在最坏情次。因此整个算法在最坏情况下的计算时间复杂性为况下的计算时间复杂性为O(logn)

28、 。算法举例leftrightmid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92找找210 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92leftrightmid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92leftrightmid例例 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92leftrightmid找找70 0 1 2 3 4 5 6 7

29、8 9 10 5 13 19 21 37 56 64 75 80 88 92leftrightmid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92left rightmid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92leftrightmid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92leftright在一个在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格个方格组成的棋盘中，恰有一个方格与其它

30、方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的棋盘覆盖问题中，要用图示的4种不同形态的种不同形态的L型骨牌覆盖给定型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何的特殊棋盘上除特殊方格以外的所有方格，且任何2个个L型骨牌型骨牌不得重叠覆盖。不得重叠覆盖。当当k0k0时，将时，将2 2k k2 2k k棋盘分割为棋盘分割为4 4个个2 2k-1k-12 2k-1k-1 子棋盘子棋盘(a)(a)所示。所示。特殊方格必位于特殊方格必位于4 4个较小子棋盘之一中，其余个较小子棋盘之一中，其余3 3个子

31、棋盘中无特个子棋盘中无特殊方格。为了将这殊方格。为了将这3 3个无特殊方格的子棋盘转化为特殊棋盘，可个无特殊方格的子棋盘转化为特殊棋盘，可以用一个以用一个L L型骨牌覆盖这型骨牌覆盖这3 3个较小棋盘的会合处，如个较小棋盘的会合处，如 (b) (b)所示，所示，从而将原问题转化为从而将原问题转化为4 4个较小规模的棋盘覆盖问题。递归地使用个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘这种分割，直至棋盘简化为棋盘1 11 1。 n 棋盘覆盖【解题思路】：将2k x 2k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个

32、方格设为特殊方格。如果是：n 左上的子棋盘（若不存在特殊方格）-则将该子棋盘右下角的那个方格假设为特殊方格n 右上的子棋盘（若不存在特殊方格）-则将该子棋盘左下角的那个方格假设为特殊方格n 左下的子棋盘（若不存在特殊方格）-则将该子棋盘右上角的那个方格假设为特殊方格n 右下的子棋盘（若不存在特殊方格）-则将该子棋盘左上角的那个方格假设为特殊方格n 当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。 将棋盘保存在一个二维数组中。骨牌号从1开始，特殊方格为0，如果是一个

33、4 * 4的棋盘，特殊方格为(2,2)，那么程序的输出为 2 2 3 3 2 1 1 3 4 1 0 5 4 4 5 5 相同数字的为同一骨牌。void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr tr + s & dc tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 / 用

34、t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角 boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr = tr + s

35、 & dc = tr + s & dc = tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 号L型骨牌覆盖左上角 boardtr + stc + s = t; / 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 复杂度分析复杂度分析解此递归方程,可得时间复杂度为:T(n)=O(4k)(1)0( )4 (1)(1)0OkT kT kOk=-+ 程序n分治法求解分治法求解 将待排序的元素序列一分为二分，得到两个将待排序的元素序列一分为二分，得到两个长度基本

36、相等的子序列，如同对半搜索的做法；长度基本相等的子序列，如同对半搜索的做法；然后对两个子序列分别排序，如果子序列较长，然后对两个子序列分别排序，如果子序列较长，还可继续细分，直到子序列的长度不超过还可继续细分，直到子序列的长度不超过1 1为止；为止；当分解所得的子序列已排列有序，可以将两个有当分解所得的子序列已排列有序，可以将两个有序子序列，合并成一个有序子序列的方法，实现序子序列，合并成一个有序子序列的方法，实现将子问题的解组合成原问题解，这是分治法不可将子问题的解组合成原问题解，这是分治法不可缺少的一步。缺少的一步。void MergeSort(Type a, int left, int

37、right) if (leftright) /至少有2个元素 int i=(left+right)/2; /取中点 mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); /合并到数组b copy(a, b, left, right); /复制回数组a nvoid Merge(Type c,Type d,int left,int m,int right )nn int i=left,j=m+1,k=left;n while(i=m)&(j=right)/从小到大的复制到d中n if(ci

38、m&jright&i1, 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) &最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)n 快速排序采用一种特殊的分划操作对排序问

39、快速排序采用一种特殊的分划操作对排序问题进行分解，其分解方法是：在待排序的序列题进行分解，其分解方法是：在待排序的序列(K0,K1,Kn-1)中选择一个元素作为分中选择一个元素作为分划元素划元素，也，也称为称为主元主元（pivot）。不妨假定选择）。不妨假定选择K 为主元。经为主元。经过一趟特殊的分划处理将原序列中的元素过一趟特殊的分划处理将原序列中的元素重新排重新排列列，使得以主元为轴心，将序列分成左右两个子，使得以主元为轴心，将序列分成左右两个子序列。序列。主元左侧子序列中所有元素都不大于主元，主元左侧子序列中所有元素都不大于主元，主元右侧子序列中所有元素都不小于主元。主元右侧子序列中所有

40、元素都不小于主元。在快速排序中，记录的比较和交换是从两端向中间在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次记录每次移动的距离较大，因而总的比较和移动次数较少。数较少。templatevoid QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r);/分划操作分划操作 QuickSort (a,p,q-1);

41、 /对左半段排序对左半段排序 QuickSort (a,q+1,r); /对右半段排序对右半段排序 n分划操作(以最左边的元素72为主元)templateint Partition (Type a, int p, int r) int i = p, j = r + 1; Type x=ap; / 将将 x的元素交换到右边区域的元素交换到右边区域 while (true) while (a+i x&ix); /从右边开始寻找不大于从右边开始寻找不大于x的数的数aj if (i = j) break; Swap(ai, aj); ap = aj; /移动主元的位置移动主元的位置 aj =

42、x; return j;n快速排序示例templateint RandomizedPartition (Type a, int p, int r) int i = Random(p,r);/产生产生p和和r之间的一个随机整数之间的一个随机整数i Swap(ai, ap); return Partition (a, p, r); 快速排序算法的性能取决于划分的对称性。通过修改快速排序算法的性能取决于划分的对称性。通过修改算法算法partition，可以设计出采用随机选择策略的快速排，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在划分时，可以在ap:r中随机选出一个元素作为划分基中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。望划分是较对称的。&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间