ch4分治法.ppt

LingJie/GDUT 第4章 分治法 主要内容： 4.1 合并排序 4.2 快速排序 4.3 折半排序 4.4 二叉树遍历及其相关特性 4.5 大整数乘法和矩阵相乘 4.6 解最近对问题与凸包问题 分治法的基本思想 将规模为N的问题分解为k个规模较小的子问题,使这些子问题相互独立可分别求解,再将k个子问题的解合并成原问题的解.如子问题的规模仍很大,则反复分解直到问题小到可直接求解为止。 在分治法中,子问题的解法通常与原问题相同,自然导致递归过程。 4.1 合并排序 合并排序的递归算法 算法 MergeSort(A[0..n-1] ) // 输入：未排序序列A[0..n-1] // 输出：已排序序列A[0..n-1] if n 1 copy A[0..?n/2?-1] to B[0..?n/2?-1] copy A[?n/2?..n-1] to C[0..?n/2?-1] MergeSort( B ) MergeSort( C ) Merge( B,C,A ) 其中，Merge(B,C,A)是将有序数组B、C合并为有序数组A的算法。 算法 Merge(B[0..p-1],C[0..q-1],A[0..p+q-1]) i=0,j=0,k=0; while ip and jq do if B[i]≤C[j] A[k]=B[i], i=i+1 else A[k]=C[j], j=j+1 k=k+1 if i=p copy C[i..q-1] to A[k..p+q-1] else copy B[0..p-1] to A[0..p+q-1] 合并排序举例 注：合并 [2,3,8,9] 与[1,4,5,7] 的过程： 从两个序列的头部开始合并：2与1比较，1被移到结果序列；2与4比较，2被移入结果序列；4与3比较，3被放入结果序列；4和8比较，4被放入结果序列, 8和5比较...， ? 合并排序的后半部分是”归并排序“。 归并排序举例： 初始序列 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] 合并排序的效率分析 设n=2k, 则关键字比较次数的递推关系式为： C(n)=2C(n/2)+Cmerge(n) C(1)=0 在最坏情况下，归并排序的效率Cmerge(n)=n-1, 于是，在最坏情况下 C (n)=2C(n/2)+n-1 解得 C(n)=nlog2n-n+1∈Θ(nlog2n) 4.2 快速排序 算法思路: 对于输入A[0.. n-1]，按以下三个步骤进行排序： (1)分区:取A中的一个元素为支点(pivot) 将A[0..n-1]划分成3段: A[0..s-1], A[s ], A[s+1..n-1], 使得 A[0..s-1]中任一元素?A[s], A[s+1..n-1]中任一元素 ?A[s]; 下标s 在划分过程中确定。 (2)递归求解:递归调用快速排序法分别对A[0..s-1]和A[s+1..n-1]排序。 (3)合并:合并A[0..s-1], A[s], A[s+1..n-1]为A[0..n-1] 快速排序算法 Qui