數(shù)據(jù)結(jié)構(gòu)排序ppt課件(編輯修改稿)
2025-05-27 18:12 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 整個(gè)待排記錄序列分割成若干子序列 ,分分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄別進(jìn)行直接插入排序，待整個(gè)序列中的記錄 ““ 基本有序基本有序”” 時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。技巧技巧 ：： 子序列的構(gòu)成不是簡(jiǎn)單地子序列的構(gòu)成不是簡(jiǎn)單地 ““ 逐段分割逐段分割 ”” ，而是將，而是將相隔某個(gè)增量相隔某個(gè)增量 dk的的 記錄組成一個(gè)子序列記錄組成一個(gè)子序列 ,讓增量讓增量 dk逐趟逐趟 縮縮短（例如依次取短（例如依次取 5,3,1），直到），直到 dk＝＝ 1為止。為止。優(yōu)點(diǎn)優(yōu)點(diǎn) ：： 讓關(guān)鍵字值小的元素能很快前移，且序列若基本讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 38例： 關(guān)鍵字序列 T=(49， 38， 65， 97, 76, 13, 27, 49*， 55, 04）， 請(qǐng)寫(xiě)出希爾排序的具體實(shí)現(xiàn)過(guò)程。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 算法分析： 開(kāi)始時(shí) dk 的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展， dk 值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度仍然很快。r[i]數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 void ShellSort(SqList amp。L， int dlta[ ]， int t){ //按增量序列 dlta[0…t1] 對(duì)順序表 L作 Shell排序 for(k=0； kt； ++k) ShellSort(L， dlta[k])； //增量為 dlta[k]的一趟插入排序} // ShellSort時(shí)間效率：空間效率： O（（ 1）） —— 因?yàn)閮H占用 1個(gè)緩沖單元算法的穩(wěn)定性： 不穩(wěn)定不穩(wěn)定 —— 因?yàn)?49*排序后卻到了 49的前面希爾排序算法希爾排序算法 （主程序）（主程序） 參見(jiàn)教材 P272O(）～）～ O（（ ）） —— 經(jīng)驗(yàn)公式dk值依次裝在 dlta[t]中數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 附：希爾排序 算法分析對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算關(guān)對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算關(guān)鍵碼的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。但想要弄清鍵碼的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。但想要弄清關(guān)鍵碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)與增量選擇之關(guān)鍵碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)與增量選擇之間的依賴(lài)關(guān)系，并給出完整的數(shù)學(xué)分析，還沒(méi)間的依賴(lài)關(guān)系，并給出完整的數(shù)學(xué)分析，還沒(méi)有人能夠做到。有人能夠做到。Knuth利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出，當(dāng)利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出，當(dāng) n很大很大時(shí)，時(shí)， 關(guān)鍵碼平均比較次數(shù)和對(duì)象平均移動(dòng)次數(shù)關(guān)鍵碼平均比較次數(shù)和對(duì)象平均移動(dòng)次數(shù)大約在大約在 到到 的范圍內(nèi)的范圍內(nèi) 。這是在利用。這是在利用直接插入排序作為子序列排序方法的情況下得直接插入排序作為子序列排序方法的情況下得到的。到的。數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) 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]； }}希爾排序算法 （其中某一趟的排序操作）參見(jiàn)教材 P272//對(duì)順序表 L進(jìn)行一趟增量為 dk的 Shell排序， dk為步長(zhǎng)因子//開(kāi)始將 r[i] 插入有序增量子表//暫存在 r[0]//關(guān)鍵字較大的記錄在子表中后移//在本趟結(jié)束時(shí)將 r[i]插入到正確位置數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 課堂練習(xí)：1. 欲將序列（ Q, H, C, Y, P, A, M, S, R, D, F, X） 中的關(guān)鍵碼按字母升序重排，則初始步長(zhǎng)為 4的希爾排序一趟的結(jié)果是？答： 原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后：2. 以關(guān)鍵字序列（ 256， 301， 751， 129， 937， 863， 742， 694，076， 438）為例，分別寫(xiě)出執(zhí)行以下算法的 各趟 排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)，并說(shuō)明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實(shí)現(xiàn)？ ① 直接插入排序 ② 希爾排序（取 dk=5,3,1）P, Q, R,A, D, H,C, F, M,S, X , Y答： 顯然，直接插入排序方法易于在鏈表上實(shí)現(xiàn)；但希爾排序方法因?yàn)槭前丛隽窟x擇記錄，不易于在鏈表上實(shí)現(xiàn)。 兩種排序方法的中間狀態(tài)分別描述如后：數(shù)學(xué)系計(jì)算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) 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，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1