递归与分治策略课件.pptVIP

複雜度分析說明：整形二維數組Board表示棋盤，Borad[0][0]使棋盤的左上角方格。tile是一個全局整形變數，用來表示L形骨牌的編號，初始值為0。tr：棋盤左上角方格的行號；tc：棋盤左上角方格的列號；dr：特殊方各所在的行號；dc：特殊方各所在的列號；size：size=2k，棋盤規格為2k×2k。複雜度分析：T(k)=4k-1=O(4k)漸進意義下的最優演算法*2.7合併排序基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合併成為所要求的排好序的集合。遞歸演算法描述：publicstaticvoidmergeSort(Comparablea[],intleft,intright){if(leftright){//至少有2個元素inti=(left+right)/2;//取中點mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);//合併到數組bcopy(a,b,left,right);//複製回數組a}}複雜度分析T(n)=O(nlogn)漸進意義下的最優演算法*演算法改進演算法mergeSort的遞歸過程可以消去。初始序列[49][38][65][97][76][13][27]第一步[3849][6597][1376][27]第二步[38496597][132776]第三步[13273849657697]*改進後的演算法描述及其複雜性演算法描述：略複雜性分析：最壞時間複雜度：O(nlogn)平均時間複雜度：O(nlogn)輔助空間：O(n)思考題：給定有序表A[1:n]，修改合併排序演算法，求出該有序表的逆序對數。*2.8快速排序快速排序是基於分治策略的另一個排序演算法，其基本思想是：分解——以ap為基準元素將ap：r劃分成3段ap：q-1、aq和aq+1：r，使得ap：q-1中任何元素小於aq，aq+1：r中任何元素大於aq；下標q在劃分過程中確定；遞歸求解——通過遞歸調用快速排序演算法分別對ap：q-1和aq+1：r進行排序；合併——由於對ap：q-1和aq+1：r的排序是就地進行的，所以在ap：q-1和aq+1：r都已排好序後不需要執行任何計算ap：r就已排好序。在快速排序中，記錄的比較和交換是從兩端向中間進行的，關鍵字較大的記錄一次就能交換到後面單元，關鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數較少。快速演算法描述：templateclassTypevoidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//對左半段排序QuickSort(a,q+1,r);//對右半段排序}}*分解/劃分演算法描述分解/劃分演算法描述：templateclassTypeintPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//將x的元素交換到左邊區域//將x的元素交換到右邊區域while(true){while(a[++i]x);while(a[--j]x);if(i=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}{6,7,51,2,5,8}初始序列{6,7,51,2,5,8}j--;↑i↑j{5,7,51,2,6,8}i++;↑i↑j{5,6,51,2,7,8}j--;↑i↑j{5,2,51,6,7,8}i++;↑i↑j{5,2,51}6{7,8}完成快速排序具有不穩定性！*複雜性分析及隨機化的快速排序演算法演算法複雜性分析：最壞時間複雜度：O(n2)平均時間複雜度：O(nlogn)輔助空間：O(n)或O(logn)快速排序演算法的性能取決於劃分的對稱性。通過修改演算法partition，可以設計出採用隨機選擇策略