數據結構(嚴蔚敏)課件第10章(編輯修改稿)

　

【文章內容簡介】 = R[low].key。 while (lowhigh) { while (lowhigh amp。amp。 R[high].key=pivotkey) high。 R[low]←→R[high] 。 while (lowhigh amp。amp。 R[low].key=pivotkey) ++low。 R[low]←→R[high]。 } return low。 // 返回樞軸所在位置 } // Partition 2022年 8月 26日星期五 第 51頁 int Partition (RedType R[], int low, int high) { }// Partition R[0] = R[low]。 pivotkey = R[low].key。 // 樞軸 while (lowhigh) { } while(lowhighamp。amp。 R[high].key=pivotkey) high。 // 從右向左搜索 R[low] = R[high]。 while (lowhigh amp。amp。 R[low].key=pivotkey) ++ low。 // 從左向右搜索 R[high] = R[low]。 R[low] = R[0]。 return low。 2022年 8月 26日星期五 第 52頁 三、快速排序 首先對無序的記錄序列進行“ 一次劃分 ”，之后 分別 對分割所得兩個子序列“ 遞歸 ”進行快速排序 。 無 序 的 記 錄 序 列 無序記錄子序列 (1) 無序子序列 (2) 樞軸 一次劃分 分別進行快速排序 2022年 8月 26日星期五 第 53頁 void QSort (RedType amp。 R[], int s, int t ) { // 對記錄序列 R[s..t]進行快速排序 if (s t1) { // 長度大于 1 } } // QSort pivotloc = Partition(R, s, t)。 // 對 R[s..t] 進行 一次劃分 QSort(R, s, pivotloc1)。 // 對低子序列遞歸排序， pivotloc是樞軸位置 QSort(R, pivotloc+1, t)。 // 對高子序列遞歸排序 2022年 8月 26日星期五 第 54頁 void QuickSort( SqList amp。 L) { // 對順序表進行快速排序 QSort(, 1, )。 } // QuickSort 第一次調用函數 Qsort 時，待排序記錄序列的上、下界分別為 1 和 。 2022年 8月 26日星期五 第 55頁 四、快速排序的時間分析 假設 一次劃分所得樞軸位置 i=k，則對n 個記錄進行快排所需時間： 其中 Tpass(n)為對 n 個記錄進行一次劃分所需時間。 若待排序列中記錄的關鍵字是隨機分布的，則 k 取 1 至 n 中任意一值的可能性相同。 T(n) = Tpass(n) + T(k1) + T(nk) 2022年 8月 26日星期五 第 56頁 ? ????????nka v ga v ga v g knTkTnCnnT1)()1(1)(設 Tavg(1)≤ b 則可得結果： )1l n ()1)(22()( ???? nncbnT a v g結論 : 快速排序的時間復雜度為 O(nlogn) 由此可得快速排序所需時間的平均值為： 2022年 8月 26日星期五 第 57頁 若待排記錄的初始狀態為按關鍵字有序時，快速排序將蛻化為起泡排序 ，其時間復雜度為 O(n2)。 為避免出現這種情況， 需在進行一次劃分之前，進行“ 予處理 ”， 即： 先對 R(s).key, R(t).key 和 R[?(s+t)/2?].key，進行相互比較，然后 取 關鍵字為 “三者之中” 的記錄 為樞軸 記錄。 2022年 8月 26日星期五 第 58頁 堆 排 序 簡 單 選 擇 排 序 堆 排 序 2022年 8月 26日星期五 第 59頁 一、簡單選擇排序 假設排序過程中，待排記錄序列的狀態為： 有序序列 R[1..i1] 無序序列 R[i..n] 第 i 趟 簡單選擇排序 從中選出 關鍵字最小的記錄 有序序列 R[1..i] 無序序列 R[i+1..n] 2022年 8月 26日星期五 第 60頁 簡單選擇排序 的算法描述如下： void SelectSort (Elem R[], int n ) { // 對記錄序列 R[1..n]作簡單選擇排序。 for (i=1。 in。 ++i) { // 選擇第 i 小的記錄，并交換到位 } } // SelectSort j = SelectMinKey(R, i)。 // 在 R[i..n] 中選擇關鍵字最小的記錄 if (i!=j) R[i]←→ R[j]。 // 與第 i 個記錄交換 2022年 8月 26日星期五 第 61頁 時間性能分析 對 n 個記錄進行簡單選擇排序，所需進行的 關鍵字間的比較次數 總計為： 移動記錄的次數 ， 最小值為 0, 最大值為 3(n1) 。 2)1()(11??????nninni2022年 8月 26日星期五 第 62頁 二、堆排序 堆是滿足下列性質的數列 {r1, r2, … ， rn}： 或 ??? ??? 122iiiirrrr?????? 122iiiirrrr堆的定義 : {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 例如 : 是 小頂堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 (小頂堆 ) (大頂堆 ) 2022年 8月 26日星期五 第 63頁 ri r2i r2i+1 若將該數列視作完全二叉樹， 則 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子。 12 36 27 65 49 81 73 55 40 34 98 例如 : 是堆 14不 2022年 8月 26日星期五 第 64頁 堆排序即是利用 堆的特性 對記錄序列進行排序的一種排序方法。 例如： 建大頂堆 { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 } { 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 } 交換 98 和 12 重新調整為大頂堆 { 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 } { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 經過篩選 2022年 8月 26日星期五 第 65頁 void HeapSort ( HeapType amp。H ) { // 對順序表 H 進行堆排序 } // HeapSort for ( i=。 i0。 i ) HeapAdjust ( , i, )。 // 建大頂堆 for ( i=。 i1。 i ) { [1]←→[i]。 // 將堆頂記錄和當前未經排序子序列 // [1..i]中最后一個記錄相互交換 HeapAdjust(, 1, i1)。 // 對 [1] 進行篩選 } 2022年 8月 26日星期五 第 66頁 如何“建堆”？ 兩個問題 : 如何“篩選”？ 定義堆類型為 : typedef SqList HeapType。 // 堆采用順序表表示之 2022年 8月 26日星期五 第 67頁 所謂 “篩選” 指的是，對一棵左 /右子樹 均為堆的完全二叉樹， “調整”根結點 使整個二叉樹也成為一個堆 。 堆 堆 篩選 2022年 8月 26日星期五 第 68頁 98 81 49 73 55 64 12 36 27 40 例如 : 是大頂堆 12但在 98 和 12 進行互換之后，它就 不 是堆了， 因此，需要對它進行“篩選”。 9812 81736412比較 2022年 8月 26日星期五 第 69頁 void HeapAdjust (RcdType amp。R[], int s, int m) { // 已知 R[s..m]中記錄的關鍵字除 R[s] 之外均 // 滿足堆的特征，本函數自上而下調整 R[s] 的 // 關鍵字，使 R[s..m] 也成為一個大頂堆 } // HeapAdjust rc = R[s]。 // 暫存 R[s] for ( j=2*s。 j=m。 j*=2 ) { // j 初值指向左孩子 自上而下的篩選過程 。 } R[s] = rc。 // 將調整前的堆頂記錄插入到 s 位置 2022年 8月 26日星期五 第 70頁 if ( = R[j].key ) break。 // 再作“根”和“子樹根”之間的比較， // 若“ =” 成立，則說明已找到 rc 的插 // 入位置 s ，不需要繼續往下調整 R[s] = R[j]。 s = j。 // 否則記錄上移，尚需繼續往下調整 if ( jm amp。amp。 R[j].keyR[j+1].key ) ++j。 // 左 /右“子樹根”之間先進行相互比較 // 令 j 指示關鍵字較大記錄的位置 2022年 8月 26日星期五 第 71頁 建堆是一個從下往上進行“篩選”的過程。 40 55 4