天津科技大學數(shù)據(jù)結(jié)構(gòu)排序(編輯修改稿)
2024-11-15 15:10 本頁面
【文章內(nèi)容簡介】 使得這個位置的左邊的所有結(jié)點的值都小于等于這個控制值，而這個位置的右邊的所有結(jié)點的值都大于等于這個控制值。 49 38 65 97 76 13 27 49’ 38 65 97 76 13 27 49’ 27 38 65 97 76 13 49’ 27 38 97 76 13 65 49’ 27 38 13 97 76 65 49’ 27 38 13 76 97 65 49’ 27 38 13 49 76 97 65 49’ 49 temp 快速排序示例 快速排序算法 int PARTITION(rectype R[],int l,int h){ int i=l。 j=h。 rectype temp=R[i]。 do { while ((R[j].key = )amp。amp。(ij)) j。 if (ij) R[i++]=R[j]。 while ((R[i].key=)amp。amp。(ij)) i++。 if (ij) R[j]=R[i]。 } while (i!=j)。 R[i]=temp。 return i。 } QUICKSORT(rectype R[],int s1,int t1){ int i。 if (s1t1){ i=PARTITION(R,s1,t1)。 QUICKSORT(R,s1,i1)。 QUICKSORT(R,i+1,t1)。 } } ????????112 )(2/)1()(ninOnnin比較次數(shù)的最大值最好情況 每次所取的基準都是當前無序區(qū)的 “中值”記錄，劃分的結(jié)果是基準的左右兩個無序子區(qū)的長度大致相等。 快速排序的時間復(fù)雜度 考慮關(guān)鍵字的比較次數(shù)和對象移動次數(shù) 最壞情況 每次劃分選取的基準都是當前無序區(qū)中關(guān)鍵字最小 (或最大 )的記錄，劃分的結(jié)果是基準的左邊 (或右邊 )為空，劃分前后無序區(qū)的元素個數(shù)減少一個，因此，排序必須做 n1趟，每一趟中需做 ni次比較，所以最大比較次數(shù)為 n)O ( n l o gn C ( 1)nn l o g)C ( n / 22kn.. ....)8 C ( n / 23n)]2 C ( n / 24 [ n / 42n)4 C ( n / 22n)]2 C ( n / 22 [ n / 2n2 C ( n / 2)nC ( n )22kk3322?????????????????? 設(shè) C(n)表示對長度為 n的序列進行快速排序所需的比較次數(shù)，顯然，它應(yīng)該等于對長度為 n的無序區(qū)進行劃分所需的比較次數(shù) n1，加上遞歸地對劃分所得的左右兩個無序子區(qū)進行快速排序所需的比較次數(shù)。假設(shè)文件長度 n=2k ， k=log2n，因此有： 快速排序的記錄移動次數(shù)不會大于比較次數(shù)，所以，快速排序的最壞時間復(fù)雜度為 O(n2)；最好時間復(fù)雜度為 O(nlog2n)。 可證 :快速排序的平均時間復(fù)雜度也是 O(nlog2n)。 快速排序是不穩(wěn)定的排序方法。 四、選擇排序 基本原理 將待排序的結(jié)點分為已排序 (初始為空 )和為未排序兩組，依次將未排序的結(jié)點中值最小的結(jié)點插入已排序的組中。 兩種常見的選擇排序 直接選擇排序 堆排序 直接選擇排序的基本過程 在一組對象 V[i]到 V[n1]中選擇具有最小關(guān)鍵字的對象若它不是這組對象中的第一個對象，則將它與這組對象中的第一個對象對調(diào)。刪除具有最小關(guān)鍵字的對象，在剩下的對象中重復(fù)第 (1)、 (2)步，直到剩余對象只有一個為止。 49 38 65 97 76 13 27 49’ 13 38 65 97 76 49 27 49’ 13 27 65 97 76 49 38 49’ 13 27 38 97 76 49 65 49’ 13 27 38 49 76 97 65 49’ 13 27 38 49 49’ 97 65 76 13 27 38 49 49’ 65 97 76 13 27 38 49 49’ 65 76 97 直 接 選擇 排序 示 例 直接選擇排序算法 SELECTSORT(rectype R[]) { int i,j,k。 rectype temp。 for (i=0。in1。i++) { k=i。 for (j=i+1。jn。j++) if (R[j].keyR[k].key) k=j。 if (k!=i) { temp=R[i]。 R[i]=R[k]。 R[k]=temp。 } } } ???????112 )(2/)1()(ninOnnin2. 當文件為正序時，移動次數(shù)為 0，文件初態(tài)為反序時，每趟排序均要執(zhí)行交換操作，總的移動次數(shù)取最大值 3(n1)。 直接選擇排序是不穩(wěn)定的排序方法。 直接選擇排序的時間復(fù)雜度 無論初始狀態(tài)如何，第 i 趟排序中選擇最小關(guān)鍵字的記錄，需做 ni次比較，因此總的比較次數(shù)為： 堆排序 樹型選擇排序 。 堆是一關(guān)鍵字序列 {k1,k2,…,k n},它具有如下特性： ki≤k2i 且 ki ≤ k2i+1 或 ki≥k2i 且 ≥ k2i+1 (i=1,2,…, └n/2┘) 堆的特性在完全二叉樹中解釋： 在排序過程中，將 R[1]到 R[n]看成是一個完全二叉樹順序存儲結(jié)構(gòu)，在完全二叉樹中任一結(jié)點的關(guān)鍵字都小于等于（或大于等于）它的左右孩子的關(guān)鍵字。 堆排序分為兩個步驟： 根據(jù)初始輸入，形成初始堆。 通過一系列的對象交換和重新調(diào)整進行排序。 10 15 56 25 30 70 10 15 56 25 30 70 小根堆示例 70 56 30 25 15 10 70 56 30 25 15 10 大根堆示例 堆排序的第一個工作是 建堆 ，即把整個記錄數(shù)組R[1]到 R[n]調(diào)整為一個堆。 只有一個結(jié)點的樹是堆，而在完全二叉樹中，所有序號 i low(n/2)的結(jié)點都是葉子，因此，以這些結(jié)點為根的子樹都已是堆。 即只需依次將序號為 low(n/2)， low(n/2)1， ...，1的結(jié)點作為根的子樹都調(diào)整為堆即可。 以 大根堆 為例進行說明 “篩選法”基本思想： 因為 R[i]的左右子樹已是堆，這兩棵子樹的根分別是各自子樹中關(guān)鍵字最大的結(jié)點，所以在 R[i]和它的左右孩子中選取關(guān)鍵字最大的結(jié)點放到 R[i]的位置上。 若 R[i]的關(guān)鍵字已是三者中的最大者，則無須做任何調(diào)整，以 R[i]為根的子樹已構(gòu)成堆， 否則，將 R[i]和具有最大關(guān)鍵字的左孩子 R[2i]或右孩子 R[2i+1]進行交換。 假定 R[2i]的關(guān)鍵字最大，將 R[i]和 R[2i]交換位置，交換之后有可能導致 R[2i]為根的子樹不再是堆，但由于 R[2i]的左右子樹仍然是堆，于是可以重復(fù)上
教學課件相關(guān)推薦
鄂ICP備17016276號-1