分治算法

1分治法2分治算法1排序问题2分治算法框架3二分法4二分法变异5同题异策31例6.1排序问题例：关键字序列：49,38,65,97,76,13,27,49调整为：13,27,38,49,49,65,76,97(从小到大)如何实现？A茫然，瞬间短路；B从外存调入几个排序算法名称，思路也未必记得清楚，如“冒泡”，“快速”；C冒出某一种排序算法(当时就这种学得扎实)；DDS课的第十章内容刷刷往外冒，像在看课件。看懂理解/背过吃透设计知道无版权的原创41例6.1排序问题已学过的主要算法策略(思想)枚举贪婪动态规划枚举贪婪列出所有可行解，检验之；理论上，攻无不克，“必杀技”；通过一系列的局部选择来得到一个问题的解；将问题分阶段；贪婪策略应用于每阶段的选择；“只顾眼前，不顾将来”。49,38,65,97,76,13,27,49效率低，应用效果差。51例6.1排序问题-贪婪1分阶段贪婪选择性质最优子结构性质贪婪策略每阶段多排一个数；先随便选一种实现方式49,38,65,97,76,13,27,49第i阶段：将原序列的前i个数由小到大排列，in。将第i个数按大小顺序插入前(i-1)个数组成的序列中；从前面开始排；6初始状态4938659776132749R0R1R2R3R4R5R6R7R8i=2i=33849659776132749i=43849659776132749i=5384965769713274976i=6384965769713274913i=7384965769713274927i=83849657697132749494938659776132749383849387趟排序1趟排序2趟排序71例6.1排序问题-贪婪2分阶段贪婪选择性质最优子结构性质贪婪策略每阶段多排一个数；再随便选一种实现方式49,38,65,97,76,13,27,49第i阶段：序列的前i个数是从小到大排列的原序列中最小的i个数；in。从剩下的(n-i+1)个数中找出最小的数，将它与第i个记录交换；先把最小的挑出来；8初始：[49386597761327]jjjjjjki=11349一趟：13[386597764927]i=2二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序结束：六趟：13273849657697kki=6i=3i=4i=5比较次数n-1n-2n-69可以，但与贪婪2相似1例6.1排序问题-贪婪3分阶段贪婪选择性质最优子结构性质贪婪策略每阶段多排一个数；第i阶段：将原序列中第i大的数，放到第n-i+1位置上；a将第i个数按大小顺序插入后(i-1)个数组成的序列中；b比较第1个数与第2个数，若为逆序则交换；然后比较第2个数与第3个数；依次类推，直至第i-1个数和第i个数比较为止；把大数先向下沉；10排序过程1、比较第一个记录与第二个记录，若关键字为逆序则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。2、对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。3、重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。初始关键字4938659776132749第一趟排序493849977697971397972797974997384965761327499738496513274976第二趟排序384913274965第三趟排序3813274949第四趟排序13273849第五趟排序132738第六趟排序for(j=1;jn;j++)if(r[j+1]r[j])r[j]r[j+1];for(j=1;jn-1;j++)if(r[j+1]r[j])r[j]r[j+1];for(i=n;i1;i--)i;{}while(i1){}//whilei=n;i=k;VoidBubbleSort(SqList&L){}冒泡排序算法初始关键字4938659776132749k=j;//交换的位置k=1;111例6.1排序问题-贪婪-总结直接插入排序简单选择排序冒泡排序含“折半插入排序”按排序依据原则：1)插入排序：直接插入排序、折半插入排序、希尔排序2)交换排序：冒泡排序、快速排序3)选择排序：简单选择排序、堆排序4)归并排序：2-路归并排序5)基数排序将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。比较特殊通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。基数排序是一种基于多关键字排序的思想，将单关键字按基数分成“多关键字”进行排序的方法。121例6.1排序问题-贪婪-总结直接插入排序简单选择排序冒泡排序排序方法按工作量分类：简单的排序方法：T(n)=O(n²)插入排序，冒泡排序，直接选择排序先进的排序方法：T(n)=O(nlogn)快速排序，堆排序，归并排序基数排序：T(n)=O(d(n+rd))=O(n)含“折半插入排序”希尔(shell)排序比较特殊131例6.1排序问题-先进的排序方法快速排序堆排序(略)归并排序14一般取第一个记录基本思想：任选一个记录，以它的关键字作为“枢轴”，凡关键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录均移至枢轴之后。一趟快速排序(一次划分)lowhigh设R[s]=52为枢轴例：5252498036145861972375st附设两个指针low和high，从high所指位置起向前搜索找到第一个关键字小于枢轴的关键字的记录与枢轴记录交换，然后从low所指位置起向后搜索找到第一个关键字大于枢轴的关键字的记录与枢轴记录交换，重复这两步直至low=high为止。high23lowlow80highhighhighhigh14lowlow5215快速排序过程：快速排序首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行一趟快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴一次划分分别进行一趟快速排序有序的记录序列…分解解决合并16voidQSort(SqList&L,intlow,inthigh){//对顺序表L中的子序列L.r[low..high]进行快速排序if(lowhigh){//长度大于1}}//QSortpivotloc=Partition(L,low,high);//对L.r[low..high]进行一次划分QSort(L,low,pivotloc-1);//对低子序列递归排序，pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子序列递归排序第一次调用函数Qsort时，待排序记录序列的上、下界分别为1和L.length。voidQuickSort(SqList&L){//对顺序表进行快速排序QSort(L,1,L.length);}//QuickSort171例6.1-快速排序快速排序(复杂度O(nlogn))：平均速度最大的一种排序方法；快速排序是一种不稳定的排序；在递归调用时需要占据一定的存储空间用来保存每一层递归调用时的必要信息。优化：当快速排序的子数组小于某个长度时，不继续递归，直接进行插入排序。有人经验得到：最好的组合方式是当子数组长度小于16时，就使用插入排序。与冒泡相似，但反应激烈。例：设排序前的关键字序列为：52,49,80,36,14,58,36,23若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是稳定的。若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是不稳定的。181例6.1-归并(合并)排序-递归思路将原始序列划分为两个子序列；分别对每个子序列递归排序；最后将排好序的子序列合并为一个有序序列。分解解决合并19归并排序-非递归思路归并：将两个或两个以上的有序表组合成一个新的有序表。在内部排序中，通常采用2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录有序序列。初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]看成是n个有序的子序列(长度为1)，然后两两归并。得到n/2个长度为2或1的有序子序列。空间复杂度为：O(n)时间复杂度为：O(nlog2n)稳定202分治算法框架-1算法设计思想：将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。分治法的基本步骤在每一层递归上都有三个步骤：1)分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；2)解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；3)合并：将已求解的各个子问题的解，逐步合并为原问题的解。212分治算法框架-2有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不必求解了，问题的解就是最后(最小)的子问题的解。分治法的这类应用，又称为“减治法”。多数问题需要所有子问题的解，并由子问题的解，使用恰当的方法合并成为整个问题的解，比如归并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。222分治算法框架-3适合用分治法策略的问题：当求解一个输入规模为n且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。1)能将这n个数据分解成k个不同子集合，且得到k个子集合是可以独立求解的子问题，其中1＜k≤n；2)分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；3)求出这些子问题的解之后，就可推解出原问题的解；232分治算法框架-4分治法的一般递归算法设计模式如下：Divide-and-Conquer(intn){//n为问题规模if(n≤n0){//n0为可解子问题的规模解子问题；return(子问题的解)；}for(i=1;i=k;i++)//分解为较小子问题p1,p2,…pkyi=Divide-and-Conquer(|Pi|);//递归解决PiT=MERGE(y1,y2,...,yk);//合并子问题return(T);}243二分法分治思想：在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。二分法当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。253例6.2金块问题金块问题：老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。26算法设计1：比较简单的方法是逐个进行比较查找。先拿两块比较重量，留下重的一个与下一块比较，直到全部比较完毕，就找到了最重的金子。算法类似于一趟选择排序