算法设计与分析第-章递归分治策略

1、算法设计与分析授课教师：刘伟电 话： 邮 件： 办 公 室：长安校区 2 号实验楼 303 室 （软件工程系办公室）西安邮电大学计算机学院第2章 递归与分治策略2.7 合并排序排序是计算机内经常进行的一种操作，其目的是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。如图像检索中的检索结果排序是依据某种算法计算得到的“检索图像相似性”关键字，然后进行排序；在谷歌上搜索网页，也是按照一定的算法计算网页的“重要性”进行排序。有很多排序算法，如冒泡排序、插入排序、选择排序等。西安邮电大学计算机学院第2章 递归与分治策略自然图像检索结果排序医学图像检索结果排序西安邮电大学计算机

2、学院第2章 递归与分治策略网页检索结果排序西安邮电大学计算机学院第2章 递归与分治策略合并排序算法是用分治策略实现对 n 个元素进行排序的算法。其基本思想是（1）将待排序元素分成大小大致相同的两个子集合，（2）分别对两个子集合进行排序，最终（3）将排好序的子集合合并成为所要求的排好序的集合。合并排序算法可递归地描述如下：templatevoid MergeSort( Type a, int left, int right ) if ( left right ) / 至少有2个元素 int i = ( left + right ) / 2; /取中点 MergeSort( a, left, i

3、); MergeSort( a, i + 1, right ); Merge( a, b, left, i, right ); /合并到数组b Copy( a, b, left, right ); /复制回数组a 西安邮电大学计算机学院第2章 递归与分治策略合并排序算法示例西安邮电大学计算机学院第2章 递归与分治策略算法说明（1）Merge 函数：合并两个排好序的数组段到一个新的数组 b 中；（2）Copy 函数：将合并后的数组段再复制回数组 a 中。Merge 函数 和 Copy 函数可以在 O( n ) 时间内完成，计算时间 T( n ) 满足：西安邮电大学计算机学院第2章 递归与分治策略

4、算法的进一步改进很容易看出，上述算法中的 MergeSort 函数的递归过程只是将待排序集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并两个排好序的数组段。因此可以首先将数组 a 中相邻元素两两配对，用合并算法将它们排序，构成 n / 2 组长度为 2 的排好序的子数组段，然后再将它们排序成长度为 4 的排好序的子数组段，如此直至整个数组排好序。用这种思想可以消去递归，“消去递归后的合并排序算法”描述如下：西安邮电大学计算机学院第2章 递归与分治策略templatevoid MergeSort( Type a, int n ) Type * b = new Type n ; / 定

5、义辅助空间 b int s = 1; while( s n ) MergePass( a, b, s, n ); / 合并到数组 b s += s; MergePass( b, a, s, n ); / 合并到数组 a s += s; 西安邮电大学计算机学院第2章 递归与分治策略上述算法中的函数 MergePass 用于合并排好序的相邻数组段。具体的合并算法由 Merge 来实现。templatevoid MergePass( Type x, Type y, int s, int n ) / 合并大小为 s 的相邻子数组 int i = 0; while( i = n - 2 * s ) /

6、合并大小为 s 的相邻 2 段子数组 Merge( x, y, i, i + s - 1, i + 2 * s - 1 ); i = i + 2 * s; / 剩下的元素个数少于 2s if ( i + s n ) Merge( x, y, i, i + s - 1, n - 1 ); else for( int j = i; j = n - 1; j+ ) y j = x j ; 西安邮电大学计算机学院第2章 递归与分治策略templatevoid Merge( Type c, Type d, int l, int m, int r ) / 合并 cl:m 和 cm + 1:r 到 dl:r

7、 int i = 1, j = m + 1,k = 1; while( ( i = m ) & ( j = r ) ) if ( c i m ) for( int q = j; q = r;q+ ) d k+ = c q ; else for( int q = i; q = m;q+ ) d k+ = c q ; 类型为 Type 的元素的比较运算“=”：如果 Type 是自定义的，则必须重载运算“=”。比如 2 幅图像之间的大小比较。西安邮电大学计算机学院第2章 递归与分治策略辅助数组smallestsmallestAGLORHIMST A西安邮电大学计算机学院第2章 递归与分治策略合并过程

8、（1）在每一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重复直至结束。smallestsmallestAGLORHIMSTA G西安邮电大学计算机学院第2章 递归与分治策略辅助数组合并过程（1）在每一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重复直至结束。smallestsmallestAGLORHIMSTAG H西安邮电大学计算机学院第2章 递归与分治策略辅助数组合并过程（1）在每一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重复直至结束。smallestsmallestAGLORHIMSTAGH I西安邮电大学

9、计算机学院第2章 递归与分治策略辅助数组合并过程（1）在每一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重复直至结束。smallestsmallestAGLORHIMSTAGHI L西安邮电大学计算机学院第2章 递归与分治策略辅助数组合并过程（1）在每一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重复直至结束。smallestsmallestAGLORHIMSTAGHIL M西安邮电大学计算机学院第2章 递归与分治策略辅助数组合并过程（1）在每一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重复直至结束。smalles

10、tsmallestAGLORHIMSTAGHILM O西安邮电大学计算机学院第2章 递归与分治策略辅助数组合并过程（1）在每一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重复直至结束。smallestsmallestAGLORHIMSTAGHILMO R西安邮电大学计算机学院第2章 递归与分治策略辅助数组合并过程（1）在每一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重复直至结束。first halfexhaustedsmallestAGLORHIMSTAGHILMOR S西安邮电大学计算机学院第2章 递归与分治策略辅助数组合并过程（1）在每

11、一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重复直至结束。first halfexhaustedsmallestAGLORHIMSTAGHILMORS T西安邮电大学计算机学院第2章 递归与分治策略辅助数组合并过程（1）在每一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重复直至结束。first halfexhaustedsecond halfexhaustedAGLORHIMSTAGHILMORST西安邮电大学计算机学院第2章 递归与分治策略辅助数组合并过程（1）在每一半排序数组中指向最小元素；（2）将二者中的较小的值插入辅助数组；（3）重

12、复直至结束。西安邮电大学计算机学院第2章 递归与分治策略2.8 快速排序快速排序算法是基于分治策略的另一个排序算法。基本思想如下：排序子数组 a p : r ，步骤如下：（1）分解：以 a p 为基准元素将 a p : r 分成 3 段： a p : q - 1 、 a q 、 a q + 1 : r 。满足条件： a p : q - 1 中任何一个元素 = a q 。下标 q 在划分过程中确定。（2）递归求解：通过递归调用快速排序算法分别对 a p : q - 1 和 a q + 1 : r 进行排序。（3）合并：对 a p : q - 1 和 a q + 1 : r 的排序在各自的范围内进

13、行，因此排好序后不需任何运算整个数组 a p : r 即完成排序。西安邮电大学计算机学院第2章 递归与分治策略快速排序算法可递归地描述如下：templatevoid QuickSort( Type a, int p, int r ) if ( p r ) int q = Partition( a, p, r ); QuickSort( a, p, q - 1 ); / 对左半段排序 QuickSort( a, q + 1, r ); / 对右半段排序 西安邮电大学计算机学院第2章 递归与分治策略上述算法的关键是函数 Partition ，其功能是以一个确定的基准元素 a p 对子数组 a p

14、: r 进行划分，它是整个排序算法的关键：template int Partition( Type a, int p, int r ) int i = p, j = r + 1; Type x = a p ; while( true ) / 将 x 的元素交换到右边区域 while( a +i x & i x ); if ( i = j ) break; Swap( a i , a j ); a p = a j ; aj := x; return j; / 返回划分位置 西安邮电大学计算机学院第2章 递归与分治策略函数 Partition 的一些说明：（1）函数主要功能是将小于 x 的元素放在

15、原数组的左半部分，而将大于 x 的元素放在原数组的右半部分；（2）取 a p 作为基准可保证算法正常结束，若选择 a r 作为划分基准，且 a r 又是 a p : r 中的最大元素，则函数返回的值为 q = r，这样会使 QuickSort 陷入死循环；（3）函数的计算时间复杂性为 O( r p 1 )。西安邮电大学计算机学院第2章 递归与分治策略快速排序算法的时间复杂性在快速排序中，记录的比较和交换是从两端向中间进行的。关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少（相对于其他比较类算法速度快）。算法的运行

16、时间与划分是否对称有关：（1）最坏情况：划分过程产生的两个区域分别包含 n 1 和 1 个元素时，由于函数 Partition 的计算时间为 O( n )，如果算法 Partition 的每一步均出现这种不对称划分，则时间复杂性为：注：由于上述划分的极端情况，QuickSort 中的递归仅执行了一次，所以上面 T( n 1 ) 的系数为 1。西安邮电大学计算机学院第2章 递归与分治策略西安邮电大学计算机学院第2章 递归与分治策略（2）最好情况：每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为 n / 2 的区域，则时间复杂性为：西安邮电大学计算机学院第2章 递归与分治策略快速排序算法

17、的性能取决于划分的对称性。通过修改算法 Partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在 a p : r 中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。算法如下：templateint RandomizedPartition( Type a, int p, int r ) int i = Random( p, r ); / 产生 p 和 r 之间的一个随机整数 Swap( a i , a p ); / 将随机选择的元素作为划分基准元素 return Partition (a, p, r);西安邮电大学计算机学院第2章 递归与分治策略随机选择策略的快速排序算法通过调用 RandomizedPartition 来产生随机的划分：template int RandomizedQuickSort( Type a, int p, int r ) if ( p r ) int q = Randomize