递归与分治策略讲义课件

1、学习要点学习要点: :理解递归的概念。理解递归的概念。掌握设计有效算法的分治策略。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。通过下面的范例学习分治策略设计技巧。（1 1）二分搜索技术；）二分搜索技术；（2 2）合并排序）合并排序（3 3）快速排序；）快速排序；（4 4）最接近点对问题；）最接近点对问题；n递归递归(recursion)(recursion)是数学与计算机科学中的基本概念。直是数学与计算机科学中的基本概念。直接或间接地调用自身的算法称为递归算法。用函数自身接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。给出定义的函数称为递归函数。

2、n递归程序不能无限制地自我调用，否则就会永不终止，递归程序不能无限制地自我调用，否则就会永不终止，递归程序必须有终止条件。递归程序必须有终止条件。n尽管递归程序在执行时间上往往比非递归程序要付出更尽管递归程序在执行时间上往往比非递归程序要付出更多的代价，但有很多问题的数学模型或算法设计方法本多的代价，但有很多问题的数学模型或算法设计方法本来就是递归的，用递归过程来描述它们不仅非常自然，来就是递归的，用递归过程来描述它们不仅非常自然， 而且证明该算法的正确性要比相应的非递归形式容易得而且证明该算法的正确性要比相应的非递归形式容易得多，因此递归不失为一种强有力的程序设计方法。多，因此递归不失为一种

3、强有力的程序设计方法。2.1 构成递归需具备的条件构成递归需具备的条件:1.1.不能无限制地调用本身，须有个出口，化简为非递归状不能无限制地调用本身，须有个出口，化简为非递归状况处理况处理( (边界条件边界条件););2.2.子问题与原问题为同一类型子问题与原问题为同一类型, ,且更为简单且更为简单( (递归模式递归模式).递归程序的书写方式递归程序的书写方式:Procedure(parameter list) if return(initial value); else return(parameter exchange); end例例1 1 阶乘函数阶乘函数 阶乘函数可递归地定义为：00)

4、!1(1!nnnnn边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。int factorial(int n) if (n= 0) return 1; return n*factorial( n-1); 例例2 Fibonacci(2 Fibonacci(斐波那齐斐波那齐) )数列数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程110)2() 1(11)(nnnnFnFnF第n个Fibonacci数可递归地计算如下：int

5、fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); 斐波那齐数列算法的递归结构(n=5) F(6)F(5)F(4)F(3)F(2)F(1)F(0)F(1) F(1)F(0)F(2)F(3)F(2)F(1)F(0)F(1)F(2)F(1)F(0)F(3)F(1)F(4)F(2)F(1)F(0)递归程序结构清晰，可读性强，而且容易用数学归纳法来证明递归程序结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。算法的正确性，因此它为设计算法、调试程序带来很

6、大方便。递归算法的运行效率较低，无论是耗费的计算时间还是占用递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。的存储空间都比非递归算法要多。求斐波那齐数列的求斐波那齐数列的非递归程序：非递归程序：void fibonacci (int n) int prev,now,next,j; if (n=1) return(1); else prev=1; now=1; for(j=2;j=n;j+) next=prev+now; prev=now; now=next; return(next); 使用递归子程使用递归子程序时，最好以序时，最好以较难的问题为较难的问题为主

7、，将处理栈主，将处理栈的复杂问题全的复杂问题全交给编译程序交给编译程序去处理。去处理。具有编译递归程序能力的程序设计语言有：C、Pascal 、 ALGOL、 PL/A 、 ADA、 QBASIC等，不具有编译递归程序能力的程序设计语言有：FORTRAN、 COBOL、BASIC、 低级语言。前2例中的函数都可以找到相应的非递归方式定义：nnnnF) 1(321!)(1125125151)(nnnF例例1 阶乘函数阶乘函数例例2 Fibonacci(斐波那齐斐波那齐)数列数列例例3 Hanoi3 Hanoi塔问题塔问题设设x,y,zx,y,z是是3 3个塔座。开始时，在塔座个塔座。开始时，在塔

8、座x x上有一叠共上有一叠共n n个圆盘，这个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为为1,2,n,1,2,n,现要求将塔座现要求将塔座x x上的这一叠圆盘移到塔座上的这一叠圆盘移到塔座z z上，并仍上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则规则1 1：每次只能移动：每次只能移动1 1个圆盘；个圆盘；规则规则2 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则规则3 3：在满足移动规则：在满足移

9、动规则1 1和和2 2的前提下，可将圆盘移至的前提下，可将圆盘移至x,y,zx,y,z中中任一塔座上。任一塔座上。xyzHANOI(2, Z, X, Y)HANOI(4, X,Y, Z)HANOI(3, X, Z, Y)HANOI(2, X, Y, Z)HANOI(1, X, Z, Y)MOVE(X, 1, Y)MOVE(X, 2, Z)HANOI(1, Y, X, Z)MOVE(Y, 1, Z)MOVE(X, 3, Y)HANOI(1, Z, Y, X)MOVE(Z, 1, X)MOVE(Z, 2, Y)HANOI(1, X, Z, Y)MOVE(X, 1, Y)MOVE(X, 4, Z)H

10、ANOI(3, Y, X, Z)HANOI(2, Y, Z, X)HANOI(1, Y, X, Z)MOVE(Y, 1, Z)MOVE(Y, 2, X)HANOI(1, Z, Y, X)MOVE(Z, 1, X)MOVE(Y, 3, Z)HANOI(2, X, Y, Z)HANOI(1, X, Z, Y)MOVE(X, 1, Y)MOVE(X, 2, Z)HANOI(1, Y, X, Z)MOVE(Y, 1, Z)XYZ汉诺塔的执行过程(n=4)HANOI(2, Z, X, Y)HANOI(4, X,Y, Z)HANOI(3, X, Z, Y)HANOI(2, X, Y, Z)HANOI(1,

11、 X, Z, Y)MOVE(X, 1, Y)MOVE(X, 2, Z)HANOI(1, Y, X, Z)MOVE(Y, 1, Z)MOVE(X, 3, Y)HANOI(1, Z, Y, X)MOVE(Z, 1, X)MOVE(Z, 2, Y)HANOI(1, X, Z, Y)MOVE(X, 1, Y)MOVE(X, 4, Z)HANOI(3, Y, X, Z)HANOI(2, Y, Z, X)HANOI(1, Y, X, Z)MOVE(Y, 1, Z)MOVE(Y, 2, X)HANOI(1, Z, Y, X)MOVE(Z, 1, X)MOVE(Y, 3, Z)HANOI(2, X, Y, Z

12、)HANOI(1, X, Z, Y)MOVE(X, 1, Y)MOVE(X, 2, Z)HANOI(1, Y, X, Z)MOVE(Y, 1, Z)XYZvoid hanoi (int n, int x, int y, int z)/ 将塔座将塔座 x 上按直径由小到大且至上而下编号为上按直径由小到大且至上而下编号为1至至 n/ 的的 n 个圆盘按规则搬到塔座个圆盘按规则搬到塔座 z 上，上，y 可用作辅助塔座。可用作辅助塔座。 if (n=1) move(x, 1, z); / 将编号为将编号为1的圆盘从的圆盘从 x 移到移到 z else hanoi(n-1, x, z, y);/ 将将x

13、上编号为上编号为1至至n-1的圆盘移到的圆盘移到y,z作辅助塔作辅助塔 move(x, n, z); / 将编号为将编号为 n 的圆盘从的圆盘从 x 移到移到 z hanoi(n-1, y, x, z); /将将y上编号为上编号为1至至n-1的圆盘移到的圆盘移到z,x作辅助塔作辅助塔 HanoiHanoi塔问题的递归程序塔问题的递归程序递归函数的运行轨迹递归函数的运行轨迹 在递归函数中，调用函数和被调用函数是同一个函数，在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第的主函数称为第

14、0 0层，进入函数后，首次递归调用自身称为层，进入函数后，首次递归调用自身称为第第1层调用；从第层调用；从第i层递归调用自身称为第层递归调用自身称为第i+1层。反之，退层。反之，退出第出第i+1层调用应该返回第层调用应该返回第i层。采用图示方法描述递归函数层。采用图示方法描述递归函数的运行轨迹，从中可较直观地了解到各调用层次及其执行的运行轨迹，从中可较直观地了解到各调用层次及其执行情况。情况。 汉诺塔的递归程序易于理解，也容易证明它的正确汉诺塔的递归程序易于理解，也容易证明它的正确性，但很难用手工移动的方式来模拟这个算法，尤其是性，但很难用手工移动的方式来模拟这个算法，尤其是n n较大的时候。

15、较大的时候。Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move (A,C)Move (A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move (C,B)Hanio(1,C,A,B)Move (A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move (B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move (A,C)Hanio(2,B,A,C)Move (B,A)Hanio(1,A,B,C)结束结束递归函数的内部执行过程递归函数的内部执行过程 一个递归函数的调用过程类似于多

16、个函数的嵌套调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：（1）运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；（3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。优点：优点：结构清晰，可读性强，而且容易用数学结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算归纳法来证明算法的正确性，因此它为设计算法、

17、调试程序带来很大方便。法、调试程序带来很大方便。缺点：缺点：递归算法是一种自身调用自身的算法，递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。因此算法的运行效率较低。因此无论是耗费的计算无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。时间还是占用的存储空间都比非递归算法要多。解决方法：解决方法：在递归算法中消除递归调用，使其转在递归算法中消除递归调用，使其转化为非递归算法。化为非递归算法。1 1、采用一个用户定义的栈来模

18、拟系统的递归调用、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效只不过人工做了本来由编译器做的事情，优化效果不明显。果不明显。2 2、用递推来实现递归函数。、用递推来实现递归函数。3 3、通过变换能将一些递归转化为尾递归，从而迭、通过变换能将一些递归转化为尾递归，从而迭代求出结果。代求出结果。 后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均有较大改善，但其适用范围有限。但其适用范围有限。 将一个难以直接解决的大问题，划分成一些规模较小将一个难以直接解决的大问

19、题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成求解的原问题划分成k个较小规模的子问题，对这个较小规模的子问题，对这k个子问个子问题分别求解。如果子问题的规模仍然不够小，则再将每个题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为子问题划分为k个规模更小的子问题，如此分解下去，直到个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，合并为一个更大规模的问题的解，自底向上自底向上

20、逐步求出原问逐步求出原问题的解。题的解。 分治法的基本思想分治法的基本思想: :2. 独立子问题独立子问题：各子问题之间相互独立，这涉及到分治法的：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。共的子问题。 1. 平衡平衡(balancing)子问题子问题：最好使子问题的规模大致相同。：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的也就是将一个问题划分成大小相等的k个子问题（通常个子问题（通常k2），），这种使子问题规模大致相等的做法是出自一种平衡这种使子问题规模大致相等的

21、做法是出自一种平衡（Balancing）子问题的思想，它几乎）子问题的思想，它几乎总是比子问题规模不等总是比子问题规模不等的做法要好。的做法要好。启发式规则： 子问题子问题1的规模是的规模是n/2 子问题子问题1的解的解 子问题子问题2的解的解 子问题子问题2的规模是的规模是n/2 原问题的解原问题的解 原问题原问题的规模是的规模是n分治法的典型情况分治法的典型情况分治法的求解过程分治法的求解过程 一般来说，分治法的求解过程由以下三个阶段组成：一般来说，分治法的求解过程由以下三个阶段组成： （1 1）划分划分：既然是分治，当然需要把规模为：既然是分治，当然需要把规模为n n的原问题划的原问题划

22、分为分为k k个规模较小的子问题，并尽量使这个规模较小的子问题，并尽量使这k k个子问题的规模个子问题的规模大致相同。大致相同。 （2 2）求解子问题求解子问题：各子问题的解法与原问题的解法通常：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。处理也可以用循环来实现。 （3 3）合并合并：把各个子问题的解合并起来，合并的代价因：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。于合并的实

23、现。 例：计算例：计算an，应用分治技术得到如下计算方法：，应用分治技术得到如下计算方法： 34 32 32 81 31 31 9 31 31 9 3 3 3 3分解问题分解问题求解每个子问题求解每个子问题合并子问题的解合并子问题的解分析时间性能 1122naanaannn如果如果如果如果n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；n该问题可以分解为若干个规模较小的相同问题，即该该问题可以分解为若干个规模较小的相同问题，即该问题具有问题具有最优子结构性质最优子结构性质n利用该问题分解出的子问题的解可以合并为该问题的利用该问题分解出的子问题的解可

24、以合并为该问题的解；解；n该问题所分解出的各个子问题是相互独立的，即子问该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。题之间不包含公共的子问题。 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地

25、独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般解公共的子问题，此时虽然也可用分治法，但一般用用动态规划动态规划较好。较好。divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 问问题题的的规规模模阀值阀

26、值设问题设问题P(n)P(n)分解成分解成k k个规模为个规模为n/mn/m的子问题的子问题, ,阀值阀值n0=1,n0=1,求解求解P(1)P(1)的的时间耗费为时间耗费为O(1).O(1).将将P(n)P(n)分解及合并成分解及合并成P(n)P(n)的解的时间为的解的时间为f(n),f(n),则则分治法解规模为分治法解规模为n n的问题的的问题的最坏时间最坏时间复杂性函数复杂性函数T(n)T(n)满足满足: : Divide-and-Conquer(P) if ( |P|=n0) Adhoc(P); divide P into smaller subinstances P1 ,P2,. ,

27、Pk; for (i = 1;i 1O(1) T(n) = kT(n / m) + f(n) = k(kT(n / m2) + f(n / m) + f(n) = k2T(n / m2) + kf(n / m) + f(n) = k3T(n / m3) + k2f(n / m2) +kf(n / m) + f(n) = 这里ma = n，所以a = log m n。于是：ka = k = n = np，这里p = log m k。 log m nlog m k由此可知，T(n)的首项是n的常数幂。 T(n)= T(1)=O(1) n=1T(n)=kT(n/m)+f(n) n1a1 j=0 =

28、kaT(1) + kj f(n / mj) = ka + kj f(n / mj)a1 i=0)f(n/mknT(n)1nogl0klogmmjjj解得:n问题描述问题描述 已知一个已知一个排好次序排好次序的元素表的元素表a1,a2,ana1,a2,an，判定某个，判定某个给定元素给定元素x x是否在该表中出现，若是，则是否在该表中出现，若是，则返回返回该元素该元素在表中的位置，否则，在表中的位置，否则，返回返回-1-1。n一般解决方法（从头到尾查找一遍）一般解决方法（从头到尾查找一遍）a1a2a3a4anx最坏情况下，顺序搜索算法需要最坏情况下，顺序搜索算法需要O(O(n n) )次比较。次

29、比较。分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。 分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素

30、中找个元素中找出一特定元素出一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。 二分搜索有序表的递归式算法二分搜索有序表的递归式算法nint recursive_binary_search ( int a , int left , int right , int T ) int k , mid; if (

31、 left right ) k = -1 ; /*数组中不存在T，返回-1 else mid = ( left + right ) / 2 ;/*取中点下标 if ( amid = T ) k = mid ; else if (amid T ) k = recursive_binary_search ( a , mid+1 , right , T ) ; else k = recursive_binary_search ( a , left , mid-1 ,T ) ; return ( k ) ;/*返回T在数组a中位置的下标值 二分搜索有序表的非递归式算法二分搜索有序表的非递归式算法nin

32、t binary_search ( int a , int n , int T ) int left , right , mid , k ; left = 0 ; right = n - 1 ; k = -1 ; while ( left T ) right = mid-1; else left = mid+1 ; return ( k ) ; 对于有序数组： （05,13,19,21,37,56,64,75,80,88,92）T=21的查找过程：05 13 19 21 37 56 64 75 80 88 92 leftrightmid05 13 19 21 37 56 64 75 80 88

33、 92 leftrightmid05 13 19 21 37 56 64 75 80 88 92 leftrightmidT=85的查找过程：05 13 19 21 37 56 64 75 80 88 92 leftrightmidmid T , left=mid +1 leftrightmidmid T , right=mid -1 leftright二分搜索有序表的算法分析二分搜索有序表的算法分析nn/2n/2n/4n/4n/4n/41111log n + 1n二分搜索的每次循环查找区间减半，查找区间构成一棵二叉树，最坏的情况是一直走到二叉树的叶子。因此算法的复杂度为 log n + 1。

34、二分搜索有序表的算法分析二分搜索有序表的算法分析n我们也可以根据递归算法列出如下的递归方程：T(n) =T( n/2) + 1 n 1 1 n = 1n由前面所学的求解递归方程的一般结论有：时间复杂度为O(log n)。每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。归并排序归并排序（1）划分划分：将待排序序列：将待排序序列r1, r2, , rn划分为两个长度相划分为两个长度相等的子序列等的子序列r1, , rn/2和和rn/2

35、1, , rn；（2）求解子问题求解子问题：分别对这两个子序列进行排序，得到：分别对这两个子序列进行排序，得到两个有序子序列；两个有序子序列；（3）合并合并：将这两个有序子序列合并成一个有序序列。：将这两个有序子序列合并成一个有序序列。 二路归并排序是成功应用分治法的一个完美例子，二路归并排序是成功应用分治法的一个完美例子，其分治策略是：其分治策略是：所谓排序，就是使一串记录，按照其中的某个或某所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。些关键字的大小，递增或递减的排列起来的操作。 r1 rn/2 rn/21 rn 划分划分r1 rn/2 rn/21

36、 rn 递归处理递归处理r1rn/2rn/21 r n 合并解合并解 （2-路）归并排序的分治思想路）归并排序的分治思想初始序列a 8 4 5 6 2 1 7 3 归并到b 4 8 5 6 1 2 3 7 复制到a 4 8 5 6 1 2 3 7 归并到b 4 5 6 8 1 2 3 7 复制到a 4 5 6 8 1 2 3 7 归并到b 1 2 3 4 5 6 7 8 复制到a 1 2 3 4 5 6 7 8 归并 4,5,6,8 1,2,3,7 从两个序列的头部开始归并：4与1比较，1被移到结果序列；4与2比较，2被移入结果序列4与3比较，3被放入结果序列；4和7比较，4被放入结果序列,

37、5和7比较.，例例: :归并过程归并过程MergeSortMergeSort的递归过程是将待排序集合一分为二，直至待排序集的递归过程是将待排序集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并两个排好序的数组段。合只剩下一个元素为止，然后不断合并两个排好序的数组段。 算法算法归并排序归并排序 temlplate void MergeSort(Type a, int left, int right) if (1eft right) /至少有至少有2个元素个元素 int i = (left + right ) /2; /取中点取中点 MergeSort(a, 1eft, i)； /归并排

38、序前半个子序列归并排序前半个子序列 MergeSort(a, i+1, right)； /归并排序后半个子序列归并排序后半个子序列 Merge(a, b, 1eft, i, right)；/从从a合并到数组合并到数组b copy(a, b, left, right);/复制回数组复制回数组a 合并函数合并函数MERGE的实现的实现A(1)A(2)A(3)A(n/2)A(n/2+1)A(n)数组数组A已分类序列已分类序列A已分类序列已分类序列B辅助辅助数组数组B比较大小小值小值A(1)比较大小小值小值A(n/2+1)数组数组A剩余已分类元素A(1)A(n/2+1)算法如下 templatevoi

39、d merge(T c, T d ,int l, int m , int r)/把cl:m,cm+1,r归并到dl,r int: i=l, /第段的游标 j=m+1, /第二段的游标 k=l; /结果的游标 /只要段中存在i和j,则不断进行归并while (i=m)&(j=r) if cim) for (int q=j; q=r;q+) dk+=cq； else for(int q=i ;q1 , c是常数是常数当当n=2k时，可得时，可得T(n)=2(2T(n/4)+cn/2)+cn = 22T(n/22)+2cn =4(2T(n/8)+cn/4)+2cn = 23T(n/23)+3

40、cn =2kT(n/2k)+kcn =2kT(1)+kcn =an+cnlognT(n)=O(nlogn)时间复杂度&最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)T(n)=O(nlogn) 渐进意义下的最优算法11)() 2/(2) 1 ()(nnnOnTOnT算法mergeSort的递归过程可以消去。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97消

41、去递归后的合并排序算法消去递归后的合并排序算法 temlplate void mergesort( type a,int n) type *b=new typen; int s; s = 1; while(sn) mergepass(a,b,n,s); s+ = s; mergepass(b,a,n,l); s += s; 快速排序快速排序 （1）划分划分：选定一个记录作为：选定一个记录作为轴值轴值，以轴值为基准将整个序，以轴值为基准将整个序列划分为两个子序列列划分为两个子序列r1 ri-1和和 ri+1 rn ，前一个子序列，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均中

42、记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；大于或等于轴值；（2）求解子问题求解子问题：分别对划分后的每一个子序列递归处理；：分别对划分后的每一个子序列递归处理；（3）合并合并：由于对子序列：由于对子序列r1 ri-1和和ri+1 rn的排序是就地进的排序是就地进行的，所以合并不需要执行任何操作。行的，所以合并不需要执行任何操作。 快速排序也是基于分治技术的重要排序算法，和归并排快速排序也是基于分治技术的重要排序算法，和归并排序不同的是：序不同的是：归并排序是按照记录在序列中的位置对序列进归并排序是按照记录在序列中的位置对序列进行划分的，而快速排序是按照记录的值对序列进行

43、划分的。行划分的，而快速排序是按照记录的值对序列进行划分的。快速排序的分治策略是：快速排序的分治策略是： r1 ri- -1 ri ri+1 rn 均均ri 轴值轴值 均均ri 位于最终位置位于最终位置 快速排序是快速排序是冒冒泡排序的一种改进方法泡排序的一种改进方法，是由是由C.A.R. C.A.R. HoareHoare于于19621962年提出的年提出的。在快速排序中，记录的比较和交换是在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次单元，关键

44、字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，而总的比较和移动次数较少。移动的距离较大，而总的比较和移动次数较少。快速排序的分治思想快速排序的分治思想jijjjiiiijjj一次划分示例一次划分示例 以轴值为基准将待排序序列划分为两个子序以轴值为基准将待排序序列划分为两个子序列后，对每一个子序列分别递归进行排序。列后，对每一个子序列分别递归进行排序。jiij算法算法一次划分一次划分 int Partition( (int r , int first, int end) ) i=first; j=end; /初始化初始化 while ( (ij) ) while ( (ij &am

45、p; ri= rj) ) j-； /右侧扫描右侧扫描 if ( (ij) ) rirj; /将较小记录交换到前面将较小记录交换到前面 i+; while ( (ij & ri= rj) ) i+； /左侧扫描左侧扫描 if ( (ij) ) rjri; /将较大记录交换到后面将较大记录交换到后面 j-; retutn i; / i为轴值记录的最终位置为轴值记录的最终位置 以第一个记录作为轴值，对待排序序列进行划分的过程为：以第一个记录作为轴值，对待排序序列进行划分的过程为：（1）初始化初始化：取第一个记录作为基准，设置两个参数：取第一个记录作为基准，设置两个参数i，j分分别用来指示将要

46、与基准记录进行比较的左侧记录位置和右侧别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；记录位置，也就是本次划分的区间；（2）右侧扫描过程右侧扫描过程：将基准记录与：将基准记录与j指向的记录进行比较，指向的记录进行比较，如果如果j指向记录的关键码大，则指向记录的关键码大，则j前移一个记录位置。重复右前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若侧扫描过程，直到右侧的记录小（即反序），若ij，则将，则将基准记录与基准记录与j指向的记录进行交换；指向的记录进行交换；（3）左侧扫描过程左侧扫描过程：将基准记录与：将基准记录与i指向的记录进行比较，

47、指向的记录进行比较，如果如果i指向记录的关键码小，则指向记录的关键码小，则i后移一个记录位置。重复左后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若侧扫描过程，直到左侧的记录大（即反序），若ij，则将，则将基准记录与基准记录与i指向的记录交换；指向的记录交换；（4）重复重复（2）（）（3）步，直到）步，直到i与与j指向同一位置，即基准记指向同一位置，即基准记录最终的位置。录最终的位置。算法算法快速排序快速排序 void QuickSort( (int r , int first, int end) ) if ( (firstend) ) pivot=Partition( (r

48、, first, end) ); /问题分解，问题分解，pivot是轴值在序列中的位置是轴值在序列中的位置 QuickSort( (r, first, pivot- -1) ); /递归地对左侧子序列进行快速排序递归地对左侧子序列进行快速排序 QuickSort( (r, pivot+1, end) ); /递归地对右侧子序列进行快速排序递归地对右侧子序列进行快速排序 T( (n) )2 T( (n/2) )n 2( (2T( (n/4) )n/2) )n4T( (n/4) )2n 4( (2T( (n/8) )n/4) )2n8T( (n/8) )3n nT( (1) )nlog2nO( (

49、nlog2n) ) 因此，时间复杂度为因此，时间复杂度为O( (nlog2n) )。 在在最好情况最好情况下，每次划分对一个记录定位后，该记录的左侧子下，每次划分对一个记录定位后，该记录的左侧子序列与右侧子序列的长度相同。在具有序列与右侧子序列的长度相同。在具有n个记录的序列中，一次个记录的序列中，一次划分需要对整个待划分序列扫描一遍，则所需时间为划分需要对整个待划分序列扫描一遍，则所需时间为O( (n) )。设。设T( (n) )是对是对n个记录的序列进行排序的时间，每次划分后，正好个记录的序列进行排序的时间，每次划分后，正好把待划分区间划分为长度相等的两个子序列，则有：把待划分区间划分为长

50、度相等的两个子序列，则有：因此，时间复杂度为因此，时间复杂度为O( (n2) )。 在在最坏情况最坏情况下，待排序记录序列下，待排序记录序列正序或逆序正序或逆序，每次划分只，每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序得到一个比上一次划分少一个记录的子序列（另一个子序列为空）。此时，必须经过列为空）。此时，必须经过n-1次递归调用才能把所有记录次递归调用才能把所有记录定位，而且第定位，而且第i趟划分需要经过趟划分需要经过n-i次关键码的比较才能找到次关键码的比较才能找到第第i个记录的基准位置，因此，总的比较次数为：个记录的基准位置，因此，总的比较次数为：)() 1(21211n

51、Onninni）（在在平均情况平均情况下，设基准记录的关键码第下，设基准记录的关键码第k小（小（1kn），则），则有：有： 这是快速排序的平均时间性能，可以用归纳这是快速排序的平均时间性能，可以用归纳法证明，其数量级也为法证明，其数量级也为O( (nlog2n) )。 nknknkTnnkTknTnnT11)(2)1()(1)(给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。 u为了使问题易于理解和分析，先来考虑一维的情形。此时，为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的中的n个点退化为个点退化为x轴上的轴上的n个实数个实数 x1,x

52、2,xn。最接近点。最接近点对即为这对即为这n个实数中相差最小的个实数中相差最小的2个实数。个实数。假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于平衡子问题平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设d=min|p1-p2|,|q1-q2|，S中的最接近点对或者是p1,p2，或者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。能否在线性时间内找到能否在线性时间内找到p3,q3？u如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3(m-d,m，q3(m,m+d。u由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m中至多包含S中的一个点。由图可以看出，如果如果(m-d,m中有中有S中的点，则此点就是中的点，则此点就是S1中最大点。中最大点。u因此，我们用线性时间就能找到区间(m-d,m和(m,m+d