第5章 减治法.ppt

算法设计与分析算法设计与分析计算机与信息学院计算机与信息学院 2 ★★使用教材使用教材作者:(美) Anany Levitin 译者:潘彦出版社:清华大学丛书名:国外经典教材·计算机科学与技术第第5 5章章减治法减治法★★算法策略算法策略★★插入排序插入排序★★深度优先搜索深度优先搜索 DFS DFS 与与广度优先搜索广度优先搜索 BFS BFS ★★拓扑排序拓扑排序★★减常因子法减常因子法★★减可变规模法减可变规模法 4 ★★算法策略算法策略减治法减治法:利用给定规模给定规模与较小规模较小规模问题解之间的关系,从顶至下(递归) 或从底至上(非递归)求解问题的一种方法。减治法通常分为 3种: w减常量法: 常量通常为 1即减 1法,也有减 2的(如奇偶数分别处理) w减常因子法: 常因子通常为 2(减半技术)。 w减可变规模法。原问题(规模 n n) )子问题(规模 n-1 n-1 ) )子问题解原问题解子问题(规模 n/2 n/2 ) )子问题解原问题解原问题(规模 n n) )× 5 插入排序插入排序插入排序★★插入排序插入排序(非降序) (非降序) w设计策略:用减治技术对一个 n元素数组 A[0,...,n-1] A[0,...,n-1] 排序。考虑减一技术,假设对较小数组 A[0,...,n-2] A[0,...,n-2] 排序问题已解决,得到 n-1 个元素有序数组 A[0] ≤ A[1] ≤ A[n-2] 。现在问题:如何把这个较小规模的解与原问题第 A[n-1] 元素合并考虑,得到原问题的解。显然,要做的是把把 A[n-1] A[n-1] 这个元素这个元素插入插入到减一后的有序数组到减一后的有序数组 A[0,...,n-2] A[0,...,n-2] 的恰当位置的恰当位置。这样,就利用了减一技术。递归的对较小的数组继续减一,即可得到一个递归算法。递归减一,直到子数组仅有一个元素为止。 w插入算法:有 3种方法实现一个元素插入,左右扫描称为直接插入法直接插入法左扫描左扫描:从左向右扫描有序子数组,当遇到第一个大于等于 A[n-1] 元素为止,在该元素前面插入 A[n-1] 。若未找到(Max) ,插在最后。右扫描右扫描:从右向左扫描有序子数组,当遇到第一个小于等于 A[n-1] 元素为止,在该元素后面插入 A[n-1] 。若未找到(Min) ,插在最前。左右扫描比较:实践中,常采用右扫描法。【理由? 】理由:若子数组中有多个等值元素,右扫描法在插入前需移动的元素个数较少。(前面等值元素都无需作位置的移动) 6 折半插入法折半插入法:因为子数组是有序的,因此可使用折半查找,为插入元素 A[n-1] 在子数组中找到一个恰当的位置: A[k] ≤ A[n-1] ≤ A[k+1] 。这是组合利用了减一技术和减半技术的一个算例。 w算法实现(伪码) ——至顶向下的递归思考方法,非递归的实现至顶向下的递归思考方法,非递归的实现虽然本算法明显基于递归思想,但由底向上来实现插入排序(非递归) 效率更高。// // [ ] ( [ ]) { ( 1) { 1; ( 0 [ ] ) { [ 1] [ 0... 1 1 ];1 [ ]; [ 1] ; ; } } /} / // 0 for to do while and d InsertionSort A i n j i j A j V A n V A i A j A j A ijVj ojj ??? ?? ???? ?? ????右扫描法:插入V元素保存后移判断起限位作用,防止越界 89 68 90 29 34 17 45 89 90 29 34 17 45 68 89 29 34 17 45 68 89 90 34 17 29 45 68 8 456 9 90 17 29 34 45 68 89 90 17 29 34 45 6 89029341 8 89 90 7 jjjjj VVVVVVj ????????????7 v v插入排序效率分析插入排序效率分析 w输入规模:待排序数组的元素个数 n; w基本操作:键值比较操作 A[j ]>V ; w效率类别:显然有最佳、最差、平均效率。若输入数组本身为升序,每次插入只需比较 1次。 w最佳效率:有 n-1 个元素要插入,显然共比较 n-1 次。线性效率。也可根据伪码计算: w最差效率: 对于每个如第 i 个元素插入,从 j= i-1 比较到 j=0 ,共 i 次键值比较, 即插入元素 A[i ]与包括 A[i-1] 的前面全部元素都比