【正文】 / 將 [1..i1]重新調(diào)整為大頂堆 } } 算法描述 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 ? 算法評價 ?時間復(fù)雜度：最壞情況下 T(n)=O(nlogn) ?空間復(fù)雜度： S(n)=O(1) 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 歸并排序的基本思想是： 將兩個或兩個以上的有序子序列“ 歸并 ” 為一個有序序列。 [i]=t。i) { // 將堆頂記錄和當(dāng)前未經(jīng)排序子序列 [1..i]中 // 最后一個記錄相互交換 t=[1]。 for(i=。i0。 int i。H) { // 對順序表 H進行堆排序。 } [s]=rc。 // rc應(yīng)插入在位置 s上 [s]=[j]。LT([j].key,[j+1].key)) ++j。j*=2) { // 沿 key較大的孩子結(jié)點向下篩選 if(jmamp。 for(j=2*s。 int j。 方法： 輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較，并與其中大（?。┱哌M行交換；重復(fù)上述操作，直至葉子結(jié)點，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選” 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 （ 40， 55， 49， 73， 12， 27， 98， 81， 64， 36，） 40 49 55 98 27 12 73 81 36 64 40 49 55 98 27 36 73 81 12 64 40 49 55 98 27 36 81 73 12 64 40 98 55 49 27 36 81 73 12 64 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 （ 40， 55， 49， 73， 12， 27， 98， 81， 64， 36） 40 98 81 49 27 36 73 55 12 64 98 49 81 40 27 36 73 55 12 64 （ 98， 81， 49， 73， 36， 27， 40， 55， 64， 12） 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 例 含 8個元素的無序序列（ 49， 38， 65， 97， 76， 13， 27， 50） 49 65 38 27 13 76 97 50 49 65 38 27 13 76 50 97 49 13 38 27 65 76 50 97 49 13 38 27 65 76 50 97 13 27 38 49 65 76 50 97 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 例 13 27 38 49 65 76 50 97 97 27 38 49 65 76 50 13 輸出： 13 27 49 38 97 65 76 50 13 輸出： 13 97 49 38 27 65 76 50 13 輸出： 13 27 38 49 50 27 65 76 97 13 輸出： 13 27 65 49 50 27 38 76 97 13 輸出： 13 27 38 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 49 65 50 27 38 76 97 13 輸出： 13 27 38 76 65 50 27 38 49 97 13 輸出： 13 27 38 49 50 65 76 27 38 49 97 13 輸出： 13 27 38 49 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 97 76 27 38 49 50 13 輸出： 13 27 38 49 50 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 76 65 97 27 38 49 50 13 輸出： 13 27 38 49 50 65 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 76 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 76 97 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 void HeapAdjust(HeapType amp。 堆排序即是利用堆的特性對記錄序列進行排序的一種排序方法。 ri r2i R2i+1 湖北師范學(xué)院物理系 王秀章主講 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個元素的最大值或最小值 ,分別稱作大頂堆或小頂堆。) 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 二、堆排序 堆排序的特點是， 在以后各趟的“選擇”中利用在第一趟選擇中已經(jīng)得到的關(guān)鍵字比較的結(jié)果。 [j]=t。 // 在 [i..]中選擇 key最小的記錄 if(i!=j) { // 與第 i個記錄交換 t=[i]。i。 RedType t。L) { // 對順序表 L作簡單選擇排序。 選擇排序 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 一、簡單選擇排序 假設(shè)排序過程中，待排記錄序列的狀態(tài)為： 無序序列 R[i..n] 有序序列 R[1..i1] 從中選出關(guān)鍵字最小的記錄加入有序序列。) ? 空間復(fù)雜度：需?？臻g以實現(xiàn)遞歸 ? 最壞情況： S(n)=O(n) ? 一般情況： S(n)=O(log2n) ?T(n)=O(n178。 // 對高子表遞歸排序 } } // QSort 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 void QuickSort(Elem R[], int n) { // 對記錄序列進行快速排序 QSort(R, 1, n)。 // 將 [low..high]一分為二 QSort(L, low, pivotloc1)。 // 返回樞軸所在位置 } 算法描述 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 在對無序序列中記錄進行了一次分割之后，分別對分割所得兩個子序列進行快速排序，依次類推，直至每個子序列中只含一個記錄為止。 [high]=t。 t=[low]。amp。 [high]=t。 t=[low]。amp。 pivotkey=[low].key。算法(a) RedType t。 湖北師范學(xué)院物理系 王秀章主講 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 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 int Partition(SqList amp。) 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 目標(biāo)： 找一個記錄，以它的關(guān)鍵字作為 “ 樞軸 ” ，凡其 關(guān)鍵字小于樞軸 的記錄均 移動至該記錄之前 ，反之，凡 關(guān)鍵字大于樞軸 的記錄均 移動至該記錄之后 。 }//while }//bubble_sort 起泡排序的結(jié)束條件為： 最后一趟沒有進行“交換”。 lastexchangeIndex=j。 ji。 while(i1) { lastexchangeIndex=1。),所以T(n)從總體上看是減小了 關(guān)鍵字較小的記錄跳躍式前移，在進行最后一趟增量為 1的插入排序時，序列已基本有序 增量序列取法 無除 1以外的公因子 最后一個增量值必須為 1 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 一、起泡排序 二、一趟快速排序 三、快速排序 四、快速排序的時間分析 167。 } } 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 希爾排序特點 子序列的構(gòu)成不是簡單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列 希爾排序可提高排序速度，因為 分組后 n值減小， n178。 // 一趟增量為 dlta[k]的插入排序 printf(第 %d趟排序結(jié)果 : ,k+1)。kt。 int k。 // 插入 } } 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 void ShellSort(SqList amp。j=dk) [j+dk]=[j]。amp。 // 暫存在 [0] for(j=idk。i=。 int i,j。 {R[1], R[1+d], R[1+2d], … ,R[1+kd]} {R[2], R[2d], R[3d], … ,