【文章內(nèi)容簡介】 52,否則進行記錄的 “ 交換 ” 。 湖北師范學院物理系 王秀章主講 2/14/2022 例 初始關(guān)鍵字： 49 38 65 97 76 13 27 50 l h x h l 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 49 27l l h l 49 65h 13 49l 49 97l h 湖北師范學院物理系 王秀章主講 2/14/2022 int Partition(SqList amp。L,int low,int high) { // 交換順序表 L中子表 [low..high]的記錄，使樞軸記錄到位， // 并返回其所在位置，此時在它之前 (后 )的記錄均不大 (小 )于它。算法(a) RedType t。 KeyType pivotkey。 pivotkey=[low].key。 // 用子表的第一個記錄作樞軸記錄 while(lowhigh) { // 從表的兩端交替地向中間掃描 while(lowhighamp。amp。[high].key=pivotkey) high。 t=[low]。 // 將比樞軸記錄小的記錄交換到低端 [low]=[high]。 [high]=t。 while(lowhighamp。amp。[low].key=pivotkey) ++low。 t=[low]。 // 將比樞軸記錄大的記錄交換到高端 [low]=[high]。 [high]=t。 } return low。 // 返回樞軸所在位置 } 算法描述 湖北師范學院物理系 王秀章主講 2/14/2022 在對無序序列中記錄進行了一次分割之后，分別對分割所得兩個子序列進行快速排序，依次類推，直至每個子序列中只含一個記錄為止。 三、快速排序 湖北師范學院物理系 王秀章主講 2/14/2022 例 初始關(guān)鍵字： 49 38 65 97 76 13 27 50 i j x j i 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 97 49 27i i j i j 49 65j 13 49i 49 97i j 湖北師范學院物理系 王秀章主講 2/14/2022 快速排序的算法描述如下 : void QSort (Elem R[], int low, int high) { // 對記錄序列 R[low..high]進行快速排序 if (low high1) { // 長度大于 1 pivotloc = Partition(L, low, high)。 // 將 [low..high]一分為二 QSort(L, low, pivotloc1)。 // 對低子表遞歸排序， pivotloc是樞軸位置 QSort(L, pivotloc+1, high)。 // 對高子表遞歸排序 } } // QSort 湖北師范學院物理系 王秀章主講 2/14/2022 void QuickSort(Elem R[], int n) { // 對記錄序列進行快速排序 QSort(R, 1, n)。 } // QuickSort 湖北師范學院物理系 王秀章主講 2/14/2022 ? 時間復雜度 ? 最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n) ? 最壞情況（每次總是選到最小或最大元素作樞軸） T(n)=O(n178。) ? 空間復雜度：需?？臻g以實現(xiàn)遞歸 ? 最壞情況： S(n)=O(n) ? 一般情況： S(n)=O(log2n) ?T(n)=O(n178。) 四、快速排序的時間分析 湖北師范學院物理系 王秀章主講 2/14/2022 一、簡單選擇排序 二、堆排序 167。 選擇排序 湖北師范學院物理系 王秀章主講 2/14/2022 一、簡單選擇排序 假設(shè)排序過程中，待排記錄序列的狀態(tài)為： 無序序列 R[i..n] 有序序列 R[1..i1] 從中選出關(guān)鍵字最小的記錄加入有序序列。 第i趟簡單選擇排序是 有序序列 R[1..i] 無序序列 R[i+1..n] 有序序列中所有記錄的關(guān)鍵字均小于無序序列中記錄的關(guān)鍵字 湖北師范學院物理系 王秀章主講 2/14/2022 例 初始： [ 49 38 65 97 76 13 27 ] k j j j j j j k k i=1 13 49 一趟： 13 [38 65 97 76 49 27 ] i=2 k k j j j j j 27 38 二趟： 13 27 [65 97 76 49 38 ] 三趟： 13 27 38 [97 76 49 65 ] 四趟： 13 27 38 49 [76 97 65 ] 五趟： 13 27 38 49 65 [97 76 ] 六趟： 13 27 38 49 65 76 [97 ] 排序結(jié)束： 13 27 38 49 65 76 97 湖北師范學院物理系 王秀章主講 2/14/2022 void SelectSort(SqList amp。L) { // 對順序表 L作簡單選擇排序。 int i,j。 RedType t。 for(i=1。i。++i) { // 選擇第 i小的記錄，并交換到位 j=SelectMinKey(L,i)。 // 在 [i..]中選擇 key最小的記錄 if(i!=j) { // 與第 i個記錄交換 t=[i]。 [i]=[j]。 [j]=t。 } } } 算法描述 湖北師范學院物理系 王秀章主講 2/14/2022 ? 算法評價 ? 時間復雜度 ? 記錄移動次數(shù) ? 最好情況： 0 ? 最壞情況： 3(n1) ? 比較次數(shù) ： )(21)( 211nninni??????? 空間復雜度 ： S(n)=O(1) T(n)=O(n178。) 湖北師范學院物理系 王秀章主講 2/14/2022 二、堆排序 堆排序的特點是， 在以后各趟的“選擇”中利用在第一趟選擇中已經(jīng)得到的關(guān)鍵字比較的結(jié)果。 堆的定義： 堆是滿足下列性質(zhì)的數(shù)列 {r1, r2, … ， rn}： ????????122iriririr 或 ??????122iiiirrrrri r2i R2i+1 湖北師范學院物理系 王秀章主講 2/14/2022 若將此數(shù)列看成是一棵完全二叉樹，則 堆或是空樹或是滿足下列特性的完全二叉樹：其左、右子樹分別是堆，并且當左 /右子樹不空時，根結(jié)點的值小于 (或大于 )左 /右子樹根結(jié)點的值 。 ri r2i R2i+1 湖北師范學院物理系 王秀章主講 2/14/2022 例 （ 96， 83， 27， 38， 11， 9） 例 （ 13， 38， 27， 50， 76， 65， 49， 97） 96 27 9 11 38 83 13 27 38 49 65 76 50 97 可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中 n個元素的最大值或最小值 ,分別稱作大頂堆或小頂堆。 湖北師范學院物理系 王秀章主講 2/14/2022 先建一個 “ 大頂堆 ” ，即先選得一個關(guān)鍵字為最大的記錄，然后與序列中最后一個記錄交換，之后繼續(xù)對序列中前 n1記錄進行 “ 篩選 ” ，重新將它調(diào)整為一個 “ 大頂堆 ” ，再將堆頂記錄和第 n1個記錄交換，如此反復直至排序結(jié)束。 堆排序即是利用堆的特性對記錄序列進行排序的一種排序方法。具體作法是： 湖北師范學院物理系 王秀章主講 2/14/2022 例如： {40， 55， 49， 73， 12， 27， 98， 81， 64， 36} {98， 81， 49， 73， 36， 27， 40， 55， 64， 12} {12， 81， 49， 73， 36， 27， 40， 55， 64， 98} {81， 73， 49， 64， 36， 27， 40， 55， 12， 98} 建大頂堆 交換 98和 12 篩選 湖北師范學院物理系 王秀章主講 2/14/2022 所謂 “ 篩選 ” 指的是，對一棵左 /右子樹均為堆的完全二叉樹 ， “ 調(diào)整 ” 根結(jié)點 使整個二叉樹為堆。 方法： 輸出堆頂元素之后，以堆中最