數(shù)據(jù)結構之樹和圖算法

數(shù)據(jù)結構之樹和圖算法第一頁，共七十頁，2022年，8月28日假設Ki=Kj

，且排序前序列中Ri

領先于Rj

；若在排序后的序列中Ri

仍領先于Rj

，則稱排序方法是穩(wěn)定的。若在排序后的序列中Rj

仍領先于Ri

，則稱排序方法是不穩(wěn)定的。例，序列3158

869若排序后得368

8915穩(wěn)定的若排序后得368

8915不穩(wěn)定的穩(wěn)定排序與不穩(wěn)定排序第二頁，共七十頁，2022年，8月28日內部排序:

指的是待排序記錄存放在計算機隨機存儲器中進行的排序過程。外部排序:

指的是待排序記錄的數(shù)量很大，以致內存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。內部排序與外部排序第三頁，共七十頁，2022年，8月28日排序的時間復雜性排序過程主要是對記錄的排序碼進行比較和記錄的移動過程。因此排序的時間復雜性可以算法執(zhí)行中的數(shù)據(jù)比較次數(shù)及數(shù)據(jù)移動次數(shù)來衡量。當一種排序方法使排序過程在最壞或平均情況下所進行的比較和移動次數(shù)越少，則認為該方法的時間復雜性就越好，分析一種排序方法，不僅要分析它的時間復雜性，而且要分析它的空間復雜性、穩(wěn)定性和簡單性等。第四頁，共七十頁，2022年，8月28日按照排序過程中所依據(jù)的原則的不同可以分類為:

插入排序

交換排序(快速排序)

選擇排序

歸并排序

基數(shù)排序

二叉排序樹排序內部排序第五頁，共七十頁，2022年，8月28日思想:利用有序表的插入操作進行排序有序表的插入:

將一個記錄插入到已排好序的有序表中，從而得到一個新的有序表。例，序列132738657697插入4913273849

657697插入排序——直接插入排序第六頁，共七十頁，2022年，8月28日例，序列49386597761327初始，S={49}；{3849}初始，令第1

個元素作為初始有序表；依次插入第

2,3,…,k

個元素構造新的有序表；直至最后一個元素；{384965}{38496597}{3849657697}{133849657697}{13273849657697}直接插入排序算法主要應用比較和移動兩種操作。直接插入排序算法描述第七頁，共七十頁，2022年，8月28日voidinsertsort(ElemTypeR[],intn)//待排序元素用一個數(shù)組R表示，數(shù)組有n個元素{for(inti=1;i<n;i++)//i表示插入次數(shù)，共進行n-1次插入

{ElemTypetemp=R[i];//把待排序元素賦給tempintj=i-1;while((j>=0)&&(temp<R[j])){R[j+1]=R[j];j--;}//順序比較和移動

R[j+1]=temp;}}第八頁，共七十頁，2022年，8月28日直接插入排序的效率分析從空間來看，它只需要一個元素的輔助空間，用于元素的位置交換。從時間分析，首先外層循環(huán)要進行n-1次插入，每次插入最少比較一次（正序），移動兩次；最多比較i次，移動i＋2次（逆序）（i=1，2，…，n-1）。Cmin=n-1Mmin=2（n-1）Cmax=1+2+…+n-1=（n2-n）/2Mmax=3+4+…+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4Mmax=（n2+7n-8）/4因此，直接插入排序的時間復雜度為O（n2）。直接插入算法的元素移動是順序的，該方法是穩(wěn)定的。第九頁，共七十頁，2022年，8月28日由于直接插入排序算法利用了有序表的插入操作，故順序查找操作可以替換為折半查找操作。例，序列49386597761327設已形成有序表{3849659776}插入元素13折半插入排序第十頁，共七十頁，2022年，8月28日算法:voidBinaryInsertSort(ElemTypeR[],intn){for(inti=1;i<n;i++)//共進行n-1次插入

{ intleft=0,right=i-1;ElemTypetemp=R[i];while(left<=right) {intmiddle=(left+right)/2;//取中點

if(temp<R[middle])right=middle-1;//取左區(qū)間

else left=middle+1;}//取右區(qū)間

for(intj=i-1;j>=left;j--) R[j+1]=R[j];//元素后移空出插入位

R[left]=temp;}}第十一頁，共七十頁，2022年，8月28日折半插入效率分析二分插入算法與直接插入算法相比，需要輔助空間與直接插入排序基本一致；時間上，前者的比較次數(shù)比直接插入查找的最壞情況好，最好的情況壞，兩種方法的元素的移動次數(shù)相同，因此二分插入排序的時間復雜度仍為O(n2)。二分插入算法與直接插入算法的元素移動一樣是順序的，因此該方法也是穩(wěn)定的。第十二頁，共七十頁，2022年，8月28日分析直接插入排序1.若待排序記錄序列按關鍵字基本有序，則排序效率可大大提高；2.待排序記錄總數(shù)越少，排序效率越高；希爾(shell)排序第十三頁，共七十頁，2022年，8月28日思想:先將待排序記錄序列分割成為若干子序列分別進行直接插入排序；待整個序列中的記錄基本有序后，再全體進行一次直接插入排序。例，序列493865977613274855419第一趟排序491319382765489755764131949273848655597476第十四頁，共七十頁，2022年，8月28日第二趟排序13194927384865559747613553876274

654948199713385576427

4965194897第三趟排序4131927

38

4849

556576

97第十五頁，共七十頁，2022年，8月28日希爾排序的算法template<classT>voidShellSort(TVector[],intarrSize){Ttemp;

intgap=arrSize/2;//gap是子序列間隔

while(gap!=0){ //循環(huán),直到gap為零

for(inti=gap;i<arrSize;i++){temp=Vector[i]; //直接插入排序

for(intj=i;j>=gap;j-=gap)

if(temp<Vector[j-gap])

Vector[j]=Vector[j-gap];elsebreak;

Vector[j]=temp;}

gap=(int)(gap/2

);}}

第十六頁，共七十頁，2022年，8月28日希爾排序效率分析希爾排序的時間復雜性在O（nlog2n）和O（n2

）之間，大致為O（n1.3）。第十七頁，共七十頁，2022年，8月28日思想:

通過不斷比較相鄰元素大小，進行交換來實現(xiàn)排序。首先將第一個元素與第二個元素比較大小，若為逆序，則交換；然后比較第二個元素與第三個元素的大小，若為逆序，則交換；...直至比較第n-1個元素與第n個元素的大小，若為逆序，則交換；第一趟排序:結果:關鍵字最大的記錄被交換至最后一個元素位置上。交換排序——冒泡排序第十八頁，共七十頁，2022年，8月28日例，序列4938761327493876132738

49

13

27384913762776初始第一趟排序后最大值13

492749次大值第二趟排序后3813

27132713382738第三趟排序后第四趟排序后第十九頁，共七十頁，2022年，8月28日冒泡排序的算法實現(xiàn)。voidBubblesort(ElemTypeR[],intn){intflag=1;//當flag為0則停止排序

for(inti=1;i<n;i++){//i表示趟數(shù)，最多n-1趟

flag=0;//開始時元素未交換

for(intj=n-1;j>=i;j--)if(R[j]<R[j-1]) {//發(fā)生逆序ElemTypet=R[j]; R[j]=R[j-1]; R[j-1]=t;flag=1;}//交換，并標記發(fā)生了交換

if(flag==0)return;}}第二十頁，共七十頁，2022年，8月28日冒泡排序的效率分析從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進行一趟排序，比較次數(shù)為（n-1）次，移動元素次數(shù)為0；若待排序的元素為逆序，則需進行n-1趟排序，比較次數(shù)為(n2-n)/2，移動次數(shù)為3(n2-n)/2，因此冒泡排序算法的時間復雜度為O（n2）。由于其中的元素移動較多，所以屬于內排序中速度較慢的一種。因為冒泡排序算法只進行元素間的順序移動，所以是一個穩(wěn)定的算法。第二十一頁，共七十頁，2022年，8月28日冒泡排序的一種改進算法。思想:以首記錄作為軸記錄，從前、后雙向掃描序列，通過交換，實現(xiàn)大值記錄后移，小值記錄前移，最終將軸記錄安置在一個適當?shù)奈恢谩?小值記錄在前、大值記錄在后)軸記錄將原序列分割成兩部分，依次對前后兩部分重新設定軸記錄，繼而分別再進行快速排序。直至整個序列有序。交換排序——快速排序第二十二頁，共七十頁，2022年，8月28日快排序（QuickSort)

快速排序實例快排序—算法思想第二十三頁，共七十頁，2022年，8月28日快排序（QuickSort)快排序---分割過程快排序是一個分治算法（也是第一個）快排序的關鍵過程是每次遞歸的分割過程分割問題描述：對一個序列，取它的一個元素作為軸，把所有小于軸的元素放在它的左邊，大于它的元素放在它的右邊分割算法：用臨時變量對軸備份取兩個指針low和high，它們的初始值就是序列的兩端下標，在整個過程中保證low不大于high移動兩個指針首先從high所指的位置向左搜索，找到第一個小于軸的元素,把這個元素放在low的位置再從low開始向右，找到第一個大于軸的元素，把它放在high的位置第二十四頁，共七十頁，2022年，8月28日快排序（QuickSort)快排序---分割過程分割算法：重復上述過程，直到low=high，把軸放在low所指的位置這樣所有大于軸的元素被放在右邊，所有小于軸的元素被放在左邊第二十五頁，共七十頁，2022年，8月28日快排序（QuickSort)快排序---分割過程3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high49第二十六頁，共七十頁，2022年，8月28日快排序（QuickSort)快排序---分割過程intPartition(TArray[],intlow,inthigh){Tpivot=Array[low]; //while(low<high){//在作為快排序的子程序時不用

while(low<high&&Array[high]>=pivot) high--;Array[low]=Array[high]; while(low<high&&Array[low]<=pivot) low++;Array[high]=Array[low];//}//在作為快排序的子程序時不用

Array[low]=pivot;returnlow;}第二十七頁，共七十頁，2022年，8月28日快排序（QuickSort)快排序---算法快排序算法是個遞歸地對序列進行分割的過程，遞歸終止的條件是最終序列長度為1

0123456749386597761327497697654927381349491338274965977613173849769749

65第二十八頁，共七十頁，2022年，8月28日快排序（QuickSort)快排序---算法voidQuickSort(TArray[],intlow,inthigh){ intPivotLocation; if(low<high){ PivotLocation=Partition(Array,low,high);QuickSort(Array,low,PivotLocation-1);QuickSort(Array,PivotLocation+1,high); }}第二十九頁，共七十頁，2022年，8月28日3．快速排序的效率分析若快速排序出現(xiàn)最好的情形（左、右子區(qū)間的長度大致相等），則結點數(shù)n與二叉樹深度h應滿足log2n<h<log2n+1，所以總的比較次數(shù)不會超過(n+1)log2n。因此，快速排序的最好時間復雜度應為O（nlog2n）。而且在理論上已經(jīng)證明，快速排序的平均時間復雜度也為O（nlog2n）。若快速排序出現(xiàn)最壞的情形（每次能劃分成兩個子區(qū)間，但其中一個是空），則這時得到的二叉樹是一棵單分枝樹，得到的非空子區(qū)間包含有n-i個(i代表二叉樹的層數(shù)（1≤i≤n）元素，每層劃分需要比較n-i+2次，所以總的比較次數(shù)為（n2+3n-4）/2。因此，快速排序的最壞時間復雜度為O(n2)?？焖倥判蛩加玫妮o助空間為棧的深度，故最好的空間復雜度為O（log2n），最壞的空間復雜度為O(n)?？焖倥判蚴且环N不穩(wěn)定的排序方法。第三十頁，共七十頁，2022年，8月28日思想:

每一趟都選出一個最大或最小的元素，并放在合適當?shù)奈恢谩?/p>

簡單選擇排序

樹形選擇排序

堆排序選擇排序第三十一頁，共七十頁，2022年，8月28日思想:第1趟選擇:從1—n

個記錄中選擇關鍵字最小的記錄，并和第1個記錄交換。第2趟選擇:從2—n

個記錄中選擇關鍵字最小的記錄，并和第2

個記錄交換。第n-1趟選擇:從n-1—n

個記錄中選擇關鍵字最小的記錄，并和第n-1

個記錄交換。...簡單選擇排序第三十二頁，共七十頁，2022年，8月28日例，序列4938976576第1趟選擇:min3849976576第2趟選擇:min38

49976576第3趟選擇:min38

49

659776第4趟選擇:min38

49

65

7697第三十三頁，共七十頁，2022年，8月28日直接選擇排序的算法template<classT>voidSelectSort(TVector[],intCurrentSize){for(inti=0;i<CurrentSize-1;i++){intk=i;//選擇具有最小排序碼的對象

for(intj=i+1;j<CurrentSize;j++)if(Vector[j]<Vector[k])

k=j;//當前具最小排序碼的對象

if(k!=i)

//對換到第

i個位置

Swap(Vector[i],Vector[k]

);} }第三十四頁，共七十頁，2022年，8月28日選擇排序的主要操作是進行關鍵字間的比較。在n個關鍵字中選出最小值，至少需要n-1次比較。在剩余的n-1個關鍵字中選出最小值，至少需要n-2次比較？如果能利用前n-1次比較所得信息，可以減少后面選擇的比較次數(shù)。體育比賽中的錦標賽:第三十五頁，共七十頁，2022年，8月28日例，8名運動員要決出冠、亞、季軍。按簡單選擇排序需要比賽7+6+5=18

場。若能夠利用以前的比賽結果，比賽場次實際可以減少為11

場。前提:

若甲勝乙，乙勝丙，則甲必能勝丙。ZhaoChaLiuBaoDiaoYangXueWangBaoBaoDiaoChaBaoDiaoWang冠軍第三十六頁，共七十頁，2022年，8月28日如何求亞軍？ZhaoChaLiuDiaoYangXueWangChaDiaoCha亞軍可以利用前面的比賽結果！ChaLiuDiaoWang第三十七頁，共七十頁，2022年，8月28日如何求季軍？ZhaoLiuDiaoYangXueWangLiuDiaoDiao季軍同樣可以利用前面的比賽結果！LiuDiaoWangZhao第三十八頁，共七十頁，2022年，8月28日又稱錦標賽排序，是一種按照錦標賽的思想進行選擇排序的方法。例，序列4938659776132750第一趟選擇133813493865977613275038651327最小值樹形選擇排序第三十九頁，共七十頁，2022年，8月28日第二趟選擇2738274938659776∞275038657627次小值第三趟選擇3838504938659776∞∞5038657650次次小值49386597761327504938659776∞2750缺點:

需要大量輔助存儲空間第四十頁，共七十頁，2022年，8月28日堆:

一棵完全二叉樹，任一個非終端結點的值均小于等于(或大于等于)其左、右兒子結點的值。例，128547305336249196381198324根結點為最小值根結點為最大值堆排序第四十一頁，共七十頁，2022年，8月28日2.把這棵普通的完全二叉樹改造成堆，便可獲取最小值；思想:3.輸出最小值；4.刪除根結點，繼續(xù)改造剩余樹成堆，便可獲取次小值；5.輸出次小值；6.重復改造，輸出次次小值、次次次小值，直至所有結點均輸出，便得到一個排序。1.將序列構造成一棵完全二叉樹；第四十二頁，共七十頁，2022年，8月28日例，序列49386597761327501.按順序依次構造成完全二叉樹的結點；49386597761327502.把完全二叉樹改造成堆；從下向上，父子交換；50971365134949273.取得最小值134.刪除13

，重新改造成新堆；1397279797495.取得次小值27；6.刪除27

，重新改造成新堆；9727973897507.取得次次小值38；第四十三頁，共七十頁，2022年，8月28日歸并排序（MergeSort)歸并---合并兩個有序的序列假設有兩個已排序好的序列A（長度為n1），B（長度為n2），將它們合并為一個有序的序列C（長度為n=n1+n2)方法很簡單：把A，B兩個序列的最小元素進行比較，把其中較小的元素作為C的第一個元素；在A，B剩余的元素中繼續(xù)挑最小的元素進行比較，確定C的第二個元素，依次類推，就可以完成對A和B的歸并，其復雜度為O(n)第四十四頁，共七十頁，2022年，8月28日歸并排序（MergeSort)歸并---合并兩個有序的序列A:138911B:2571013C:1

2

3

5

7

89

10

11

13第四十五頁，共七十頁，2022年，8月28日歸并排序（MergeSort)歸并---合并兩個有序的序列voidmerge(TA[],intAlen,TB[],intBlen,TC[]){inti=0,j=0,k=0;while(i<Alen&&j<Blen){if(A[i]<B[j]) C[k++]=A[i++]; else C[k++]=B[j++]; } while(i<Alen) C[k++]=A[i++]; while(j<Blen) C[k++]=B[j++];}第四十六頁，共七十頁，2022年，8月28日歸并排序（MergeSort)歸并---合并一個序列中的兩個有序的數(shù)據(jù)段voidmerge(TA[],intl,intm,inth){inti=l,j=m+1,k=0;T*C=newT[h-l+1];while(i<=m&&j<=h){if(A[i]<A[j])C[k++]=A[i++]; elseC[k++]=A[j++];} while(i<=m)C[k++]=A[i++]; while(j<=h)C[k++]=B[j++];for(k=0;k<h-l+1;k++)A[i+k]=C[k];//將排好序的元素寫回A數(shù)組

delete[]C;}第四十七頁，共七十頁，2022年，8月28日歸并排序（MergeSort)歸并排序歸并排序是一個分治遞歸算法遞歸基礎：若序列只有一個元素，則它是有序的，不執(zhí)行任何操作遞歸步驟：先把序列劃分成長度基本相等的兩個序列對每個子序列遞歸排序把排好序的子序列歸并成最后的結果第四十八頁，共七十頁，2022年，8月28日歸并排序（MergeSort)歸并排序初始序列：[8，4，5，6，2，1，7，3]分解：[8][4][5][6][2][1][7][3]歸并：[4，8][5，6][1，2][3，7]歸并：[4，5，6，8][1，2，3，7]歸并：[1，2，3，4，5，6，7，8]分解：[8，4，5，6][2，1，7，3]分解：[8，4][5，6][2，1][7，3]第四十九頁，共七十頁，2022年，8月28日歸并排序（MergeSort)歸并排序voidMergeSort(intA[],intl,inth)//將數(shù)組A中A[l,…,(l+h)/2]與A[(l+h)/2+1,…,h]兩段數(shù)據(jù)歸并{

if(l==h) return; intm=(l+h)/2; MergeSort(A,l,m); MergeSort(A,m+1,h); Merge(A,l,m,h);}第五十頁，共七十頁，2022年，8月28日歸并排序（MergeSort)算法分析最壞情況：歸并排序是一個遞歸算法，所以很容易得到算法計算量的遞推公式

所以算法最壞情況的復雜度為算法需要的輔助空間

第五十一頁，共七十頁，2022年，8月28日歸并排序（MergeSort)其他策略上面歸并排序每次迭代時將原序列分割為兩個基本等長的序列，稱為二路歸并排序也可以分割成其他的分，如3，4等等評論：盡管歸并排序最壞情況的比較次數(shù)比快速排序少，但它需要更多的元素移動，因此，它在實用中不一定比快速排序快

第五十二頁，共七十頁，2022年，8月28日歸并排序（MergeSort)以比較為基礎的排序算法的下界基于比較的算法總是在一系列比較下完成的每次比較都可能出現(xiàn)兩種情況(a>b和a<b),如果以每次比較作為節(jié)點，則每個以比較為基礎的排序算法都可以用一個二叉樹來表示，其中一個中間節(jié)點表示一次比較，葉子節(jié)點表示排序的一種結果，這樣的二叉樹稱為判定樹或決策樹舉例：比如有一個序列{a,b,c}(a,b,c互不相等），下列算法：先比較a和b,再比較a和c，最后比較b和c

可以用下面的判定樹表示

第五十三頁，共七十頁，2022年，8月28日歸并排序（MergeSort)以比較為基礎的排序算法的下界a<b?yesa<c?yesb<c?yesa<b<ca<c<bnononoc<a<ba<c?yesb<a<cnob<c?yesb<c<ac<b<ano第五十四頁，共七十頁，2022年，8月28日歸并排序（MergeSort)以比較為基礎的排序算法的下界假設輸入為a,b,c,a<c<b,則算法執(zhí)行經(jīng)過的路線為(a<b)—(a<c)—(b<c)，需要3次比較假設輸入為a,b,c,b<a<c,則算法執(zhí)行經(jīng)過的路線為(a<b)—(a<c)需要2次比較任何以比較為基礎的排序算法都可以表示為一棵決策樹樹的形狀和大小表示的是排序算法的功能和需要排序的元素個數(shù)樹的高度表示了算法的運行時間任何排序決策樹都有n!個葉子

第五十五頁，共七十頁，2022年，8月28日歸并排序（MergeSort)以比較為基礎的排序算法的下界根據(jù)數(shù)據(jù)結構中關于二叉樹的性質，有：最壞情況：任何排序算法至少要做 次比較平均情況：任何排序算法的平均比較次數(shù)的下界是結論：具有O(nlgn)復雜度的比較排序算法在漸進意義下是最優(yōu)的算法

第五十六頁，共七十頁，2022年，8月28日是一種借助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。1.多關鍵字排序撲克牌問題:已知撲克牌中52張牌面的次序關系定義為:?

＜

?

＜

?

＜

?花色:面值:2＜3＜＜A...例，?8

?

3＜花色優(yōu)先級更高，為主關鍵字，面值為次關鍵字基數(shù)排序第五十七頁，共七十頁，2022年，8月28日2.52張牌排序方法:最高位優(yōu)先法(MSDF):先按不同“花色”分成有次序的4堆，每一堆均具有相同的花色；然后分別對每一堆按“面值”大小整理有序。最低位優(yōu)先法(LSDF):先按不同“面值”分成13堆；然后將這13堆牌自小至大疊在一起(2,3,...,A)；然后將這付牌整個顛倒過來再重新按不同的“花色”分成4堆；最后將這4堆牌按自小至大的次序合在一起。收集分配第五十八頁，共七十頁，2022年，8月28日3.基數(shù)排序基數(shù)排序就是借助于“分配”和“收集”兩種操作實現(xiàn)對單邏輯關鍵字的排序。首先，單邏輯關鍵字通常都可以看作是由若干關鍵字復合而成。其次，利用LSDF法實現(xiàn)對若干關鍵字的排序。例，若關鍵字是數(shù)值，且值域為0≤K≤999，故可以將K

看作是由3個關鍵字K0K1K2

組成，例，603是由603

組成。第五十九頁，共七十頁，2022年，8月28日例，序列278109063930589184505269008083第一趟分配0123456789278109063930589184505269008083第一