【文章內容簡介】 整個待排記錄序列分割成若干子序列 ,分分別進行直接插入排序，待整個序列中的記錄別進行直接插入排序，待整個序列中的記錄 ““ 基本有序基本有序”” 時，再對全體記錄進行一次直接插入排序。時，再對全體記錄進行一次直接插入排序。技巧技巧 ：： 子序列的構成不是簡單地子序列的構成不是簡單地 ““ 逐段分割逐段分割 ”” ，而是將，而是將相隔某個增量相隔某個增量 dk的的 記錄組成一個子序列記錄組成一個子序列 ,讓增量讓增量 dk逐趟逐趟 縮縮短（例如依次取短（例如依次取 5,3,1），直到），直到 dk＝＝ 1為止。為止。優(yōu)點優(yōu)點 ：： 讓關鍵字值小的元素能很快前移，且序列若基本讓關鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。有序時，再用直接插入排序處理，時間效率會高很多。數學系計算數學教研室 數據結構 Ch02 38例： 關鍵字序列 T=(49， 38， 65， 97, 76, 13, 27, 49*， 55, 04）， 請寫出希爾排序的具體實現過程。0 1 2 3 4 5 6 7 8 9 1049 38 65 97 76 13 27 49* 55 04初態(tài)：第 1趟 (dk=5)第 2趟 (dk=3)第 3趟 (dk=1)49 1313 4938 2765 49*97 5576 0427 38 65 49* 975513 5576045527 042704 4949* 7638 65 975513 2704 4949* 38 76 65 9713 27 04 49* 76 97 算法分析： 開始時 dk 的值較大，子序列中的對象較少，排序速度較快；隨著排序進展， dk 值逐漸變小，子序列中對象個數逐漸變多，由于前面工作的基礎，大多數對象已基本有序，所以排序速度仍然很快。r[i]數學系計算數學教研室 數據結構 Ch02 void ShellSort(SqList amp。L， int dlta[ ]， int t){ //按增量序列 dlta[0…t1] 對順序表 L作 Shell排序 for(k=0； kt； ++k) ShellSort(L， dlta[k])； //增量為 dlta[k]的一趟插入排序} // ShellSort時間效率：空間效率： O（（ 1）） —— 因為僅占用 1個緩沖單元算法的穩(wěn)定性： 不穩(wěn)定不穩(wěn)定 —— 因為 49*排序后卻到了 49的前面希爾排序算法希爾排序算法 （主程序）（主程序） 參見教材 P272O(）～）～ O（（ ）） —— 經驗公式dk值依次裝在 dlta[t]中數學系計算數學教研室 數據結構 Ch02 附：希爾排序 算法分析對特定的待排序對象序列，可以準確地估算關對特定的待排序對象序列，可以準確地估算關鍵碼的比較次數和對象移動次數。但想要弄清鍵碼的比較次數和對象移動次數。但想要弄清關鍵碼比較次數和對象移動次數與增量選擇之關鍵碼比較次數和對象移動次數與增量選擇之間的依賴關系，并給出完整的數學分析，還沒間的依賴關系，并給出完整的數學分析，還沒有人能夠做到。有人能夠做到。Knuth利用大量的實驗統(tǒng)計資料得出，當利用大量的實驗統(tǒng)計資料得出，當 n很大很大時，時， 關鍵碼平均比較次數和對象平均移動次數關鍵碼平均比較次數和對象平均移動次數大約在大約在 到到 的范圍內的范圍內 。這是在利用。這是在利用直接插入排序作為子序列排序方法的情況下得直接插入排序作為子序列排序方法的情況下得到的。到的。數學系計算數學教研室 數據結構 Ch02 void ShellInsert(SqList amp。L， int dk) { for(i=dk+1； i=； ++ i) if(r[i].key r[idk].key) { r[0]=r[i]； for(j=idk。 j0 amp。amp。(r[0].keyr[j].key)。 j=jdk) r[j+dk]=r[j]； r[j+dk]=r[0]； }}希爾排序算法 （其中某一趟的排序操作）參見教材 P272//對順序表 L進行一趟增量為 dk的 Shell排序， dk為步長因子//開始將 r[i] 插入有序增量子表//暫存在 r[0]//關鍵字較大的記錄在子表中后移//在本趟結束時將 r[i]插入到正確位置數學系計算數學教研室 數據結構 Ch02 課堂練習：1. 欲將序列（ Q, H, C, Y, P, A, M, S, R, D, F, X） 中的關鍵碼按字母升序重排，則初始步長為 4的希爾排序一趟的結果是？答： 原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后：2. 以關鍵字序列（ 256， 301， 751， 129， 937， 863， 742， 694，076， 438）為例，分別寫出執(zhí)行以下算法的 各趟 排序結束時，關鍵字序列的狀態(tài)，并說明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實現？ ① 直接插入排序 ② 希爾排序（取 dk=5,3,1）P, Q, R,A, D, H,C, F, M,S, X , Y答： 顯然，直接插入排序方法易于在鏈表上實現；但希爾排序方法因為是按增量選擇記錄，不易于在鏈表上實現。 兩種排序方法的中間狀態(tài)分別描述如后：數學系計算數學教研室 數據結構 Ch02 原始序列： 256， 301， 751， 129， 937， 863， 742， 694， 076， 438[256， 301]， 751， 129， 937， 863， 742， 694， 076， 438[256， 301， 751]， 129， 937， 863， 742， 694， 076， 438[129， 256， 301， 751]， 937， 863， 742， 694， 076， 438[129， 256， 301， 751， 937]， 863， 742， 694， 076， 438[129， 256， 301， 751， 863， 937]， 742， 694， 076， 438[129， 256， 301， 742， 751， 863， 937]， 694， 076， 438[129， 256， 301， 694， 742， 751， 863，