【正文】 if ( [0].key [m].key ) high = m1。 // 插入點在低半?yún)^(qū) else low = m+1。 // 插入點在高半?yún)^(qū) } for( j=i1。 j=high+1。 j ) [j+1]=[j]。 // 記錄后移 [high+1]=[0]。 // 插入 } } 算法分析： ? 折半插入排序所需要的關鍵字比較次數(shù)與待排序記錄序列的初始排列無關，僅依賴于記錄個數(shù)。在插入第 i 個記錄時，需要經(jīng)過 ?log2i? +1 次關鍵字比較，才能確定它應插入的位置。 將 n 個記錄用折半插入排序所進行的關鍵字比較次數(shù)為O(nlog2n) . ? 折半插入排序的時間復雜度仍為 O（ n2） ? 當 n 較大時 ， 總的關鍵字比較次數(shù)比直接插入排序的最壞情況要好得多 ， 但比其最好情況要差 。 ? 在記錄的初始排列已經(jīng)按關鍵字排好序或接近有序時 ， 直接插入排序比折半插入排序執(zhí)行的關鍵字比較次數(shù)要少 。 折半插入排序的記錄移動次數(shù)與直接插入排序相同 ， 依賴于記錄的初始排列 。 ? 折半插入排序是一個穩(wěn)定的排序方法 。 希爾排序 (Shell Sort) ? 從對直接插入排序的分析可知 ， 其時間復雜度為O(n2), 但是當待排序記錄處于 “ 基本有序 ” 狀態(tài)或 當 n值較小 時 ， 直接插入排序的效率可大大提高 。Shell 排序方法正是基于這兩點考慮對直接插入排序加以改進而提出的一種插入排序算法 。 ? Shell 排序方法是一種 “ 逐漸縮小插入間隔 ” 的插入排序方法 ， 在時間效率上較直接插入排序有較大的改進 。 ? 先確定一個小于 n 的整數(shù) d1作為第一個 增量 ，把記錄序列分為 d1個組，所有距離為 d1倍數(shù)的記錄放在同一個組中，在各組內進行直接插入排序； ? 然后，取第二個增量 d2（ d2 d1 ） ,重復上述分組和排序，直至所取的增量 dt=1（ dtdt1… d 2 d1 ） , 即所有記錄處在同一組中進行直接插入排序為止。 Shell 排序的基本做法： 21 25 49 25* 16 08 1 2 3 4 5 6 21 25* i = 1 d1 = 3 49 25 16 08 25 16 49 25* 08 21 08 49 25 21 25* 16 21 25 49 25* 16 08 1 2 3 4 5 6 21 i = 2 08 d2 = 2 25 49 16 25* 16 08 21 25 49 25* 49 08 16 21 25* 25 21 25 49 25* 16 08 0 1 2 3 4 5 21 i = 3 08 d3 = 1 25 16 49 25* ?開始時 增量 值較大，子序列中的 記錄較少 ，排序速度較快；隨著排序進展，增量值逐漸變小，子序列中記錄個數(shù)逐漸變多，由于前面工作的基礎，大多數(shù)記錄已 基本有序 ，所以排序速度仍然很快。 void ShellInsert( SqList amp。L,int dk ){ for( i=dk+1。 i=。 i++ ) if([i].key [idk].key){ // 需將 [i]插入有序增量子表 [0] = [i]。 // 暫存在 [0],但不是哨兵 。 for(j=idk。 j0 amp。amp。 [0].key[j].key。 j=dk) [j+dk] = [j]。 // 記錄后移 ， 查找插入位置 [j+dk] = [0]。 } } void ShellSort(SqList amp。L, int dlta[], int t){ // 按增量序列 dlta[0..t1]對順序表 L作希爾排序 for(k=0。 kt。 t++){ ShellInsert( L, dlta[k] )。 // 一趟增量為 dlta[k]的插入排序 } 希爾排序的算法： ? 增量 的取法有多種。最初 shell 提出取 d1 = ?n/2?， d2 = ?d1/2?，直到 dt = 1。后來 knuth 提出取 di+1 = ?di/3? +1。還有人提出都取奇數(shù)為好，也有人提出各 增量 互質為好。 算法分析： 對特定的待排序記錄序列 ， 可以準確地估算關鍵字的比較次數(shù)和記錄移動次數(shù) 。 但想要弄清關鍵字比較次數(shù)和記錄移動次數(shù)與增量選擇之間的依賴關系 ， 并給出完整的數(shù)學分析 ， 還沒有人能夠做到 。 快速排序 ( Exchange Sort ) ? 基本方法 ： 比較相鄰兩個記錄的關鍵字，若R[i].keyR[i+1].key，則交換之，其中 i 從 0到 npass1（ pass的初值為 1）稱之為一趟起泡排序，其結果是使最大關鍵字的記錄被交換到 npass的位置上，如果某一趟起泡排序過程中沒有進行一次記錄的交換，則排序過程結束。最壞情況下需 n1趟排序。 基本思想： 是兩兩比較待排序記錄的關鍵字，如果發(fā)生逆序 (即排列順序與排序后的次序正好相反 )，則交換之，直到所有記錄都排好序為止。 起泡排序 (Bubble Sort) 21 25 49 25* 16 08 0 1 2 3 4 5 21 25* i = 1 49 25 16 25 16 08 49 noSwap=1 08 25* 49 21 noSwap =1 i = 2 i = 3 08 16 noSwap =1 25* 25 21 25* 0 1 2 3 4 5 i = 4 49 16 noSwap =0 08 25 21 void BubbleSort( SqList amp。L ){ // 從下往上掃描的起泡排序 for( i=0。 in2。i++ ){ // 做 n1趟排序 noSwap=TRUE。 // 置未交換標志 for( j=n1。j=i。j ) // 從下往上掃描 if([j+1].key [j].key) { temp=[j+1]。 // 交換記錄 [j+1]=[j]。 [j]=temp。 noSwap=FALSE。 } if( noSwap ) break。 // 本趟掃描未發(fā)生交換 ， 則終止算法 } } 起泡排序的算法： 算法分析： 在記錄的初始排列已經(jīng)按關鍵字從小到大排好序時，此算法只執(zhí)行一趟起泡，做 n1 次關鍵字比較，不移動記錄。這是最好的情形。 ? 最壞的情形是算法執(zhí)行了 n1趟起泡，第 i 趟 (1? i? n) 做了 n i 次關鍵字比較，執(zhí)行了 ni 次記錄交換。這樣在最壞情形下總的關鍵字比較次數(shù) KCN和記錄移動次數(shù) RMN為： ? 起泡排序需要一個附加記錄以實現(xiàn)記錄值的對換。 ? 起泡排序是一個穩(wěn)定的排序方法。 ??????????????11111233121nininninR M NnninK C N)()()()(快速排序 (Quick Sort) ? 基本思想 ： – 是任取待排序記錄序列中的某個記錄 (例如取第一個記錄 ) 作為 基準 ，按照該記錄的關鍵字大小，將整個記錄序列劃分為左右兩個子序列： ? 左側子序列中所有記錄的關鍵字都小于或等于基準記錄的關鍵字 ? 右側子序列中所有記錄的關鍵字都大于或等于基準記錄的關鍵字 – 基準記錄則排在這兩個子序列中間 (這也是該記錄最終應安放的位置 )。 – 然后分