【文章內容簡介】 上 將 R[high].key 和 樞軸的關鍵字進行比較，要求 R[high].key ≥ 樞軸的關鍵字 將 R[low].key 和 樞軸的關鍵字進行比較，要求 R[low].key ≤ 樞軸的關鍵字 high 23 low 80 high 14 low 52 例如 R[0] 52 low hig high high low 第十章 內部排序 快速 排序 可見，經過“ 一次劃分 ” ，將關鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調整為 : 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調整過程中，設立了兩個指針 : low 和high，它們的初值分別為 : s 和 t, 之后逐漸減小 high，增加 low，并保證 R[high].key≥52，和 R[low].key≤52,否則進行記錄的 “ 交換 ” 。 第十章 內部排序 快速 排序 int Partition (RedTypeamp。 R[], int low, int high) { pivotkey = 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 第十章 內部排序 快速 排序 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。 第十章 內部排序 快速 排序 三、快速排序 首先對無序的記錄序列進行 “ 一次劃分 ”，之后 分別 對分割所得兩個子序列 “ 遞歸 ”進行快速排序 。 無 序 的 記 錄 序 列 無序記錄子序列 (1) 無序子序列 (2) 樞軸 一次劃分 分別進行快速排序 第十章 內部排序 快速 排序 void QSort (RedTypeamp。 R[], int s, int t ) { // 對記錄序列 R[s..t]進行快速排序 if (s t) { // 長度大于 1 } } // QSort pivotloc = Partition(R, s, t)。 // 對 R[s..t] 進行一次劃分 QSort(R, s, pivotloc1)。 // 對低子序列遞歸排序， pivotloc是樞軸位置 QSort(R, pivotloc+1, t)。 // 對高子序列遞歸排序 第十章 內部排序 快速 排序 void QuickSort( SqList amp。 L) { // 對順序表進行快速排序 QSort(, 1, )。 } // QuickSort 第一次調用函數(shù) Qsort 時，待排序記錄序列的上、下界分別為 1 和 。 第十章 內部排序 快速 排序 四、快速排序的時間分析 假設 一次劃分所得樞軸位置 i=k，則對 n 個記錄進行快排所需時間 其中 Tpass(n)為對 n 個記錄進行一次劃分所需時間， 若待排序列中記錄的關鍵字是隨機分布的，則 k 取 1 至 n 中任意一值的可能性相同。 T(n) = Tpass(n) + T(k1) + T(nk) 第十章 內部排序 快速 排序 ? ????????nka v ga v ga v g knTkTnCnnT1)()1(1)(設 Tavg(1)≤ b 則可得結果 : )1l n ()1)(22()( ???? nncbnT a v g結論 : 快速排序的時間復雜度為 O(nlogn) 由此可得快速排序所需時間的平均值為： 第十章 內部排序 快速 排序 若待排記錄的初始狀態(tài)為按關鍵字有序時，快速排序將蛻化為起泡排序 ，其時間復雜度為 O(n2)。 為避免出現(xiàn)這種情況， 需在進行一次劃分之前，進行“予處理”， 即： 先對 R(s).key, R(t).key 和 R[?(s+t)/2?.key，進行相互比較，然后 取 關鍵字為 “三者之中” 的記錄 為樞軸 記錄。 第十章 內部排序 堆 排序 簡單選擇排序 堆 排 序 目錄 第十章 內部排序 堆 排序 一、簡單選擇排序 假設排序過程中，待排記錄序列的狀態(tài)為： 有序序列 R[1..i1] 無序序列 R[i..n] 第 i 趟 簡單選擇排序 從中選出 關鍵字最小的記錄 有序序列 R[1..i] 無序序列 R[i+1..n] 第十章 內部排序 堆 排序 簡單選擇排序 的算法描述如下： 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 個記錄交換 第十章 內部排序 堆 排序 時間性能分析 對 n 個記錄進行簡單選擇排序，所需進行的 關鍵字間的比較次數(shù) 總計為 移動記錄的次數(shù) ， 最小值為 0, 最大值為 3(n1) 2)1()(11??????nninni第十章 內部排序 堆 排序 二、堆排序 堆是滿足下列性質的數(shù)列 {r1, r2, … ， rn}： 或 ??? ?? ? 12 2ii ii rr rr ??? ?? ? 12 2ii ii rr rr堆的定義 : {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 例如 : 是 小頂堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 (小頂堆 ) (大頂堆 ) 第十章 內部排序 堆 排序 ri r2i r2i+1 若將該數(shù)列視作完全二叉樹， 則 r2i 是 ri 的左孩子 。 r2i+1 是 ri 的右孩子。 12 36 27 65 49 81 73 55 40 34 98 例如 : 是堆 14不 第十章 內部排序 堆 排序 堆排序即是利用 堆的特性 對記錄序列進行排序的一種排序方法。 例如： 建大頂堆 { 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 } 經過篩選 第十章 內部排序 堆 排序 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] 進行篩選 } 第十章 內部排序 堆 排序 如何“建堆”？ 兩個問題 : 如何“篩選”？ 定義堆類型為 : typedef SqList H