數(shù)據(jù)結(jié)構(gòu)排序ppt課件-在線瀏覽
2025-06-17 18:12本頁面
【正文】 1【 3, 6, 13， 31】 , 9, 27, 5, 11【 3, 6, 9, 13， 31】 , 27, 5, 11【 3, 6, 9, 13， 27, 31】 , 5, 11【 3, 5, 6, 9, 13， 27, 31】 , 11【 3, 5, 6, 9, 11， 13， 27, 31】 在已形成的 有序表中 線性查找 ，并在適當(dāng)位置插入，把原來位置上的元素向后 順移 。 *表示后一個 25i=121 25 49 25* 16 080 1 2 3 4 5 6暫暫存存i=2 i=3 i=5i=4 i=6254925* 4916 25*08 49解： 假設(shè)該序列已存入一維數(shù)組 V[7]中，將 V[0]作為緩沖或暫存單元（ Temp）。 其他情況下還要加上移動元素的次數(shù)。 對應(yīng)程序參見教材 P265。次插入。因此，總的關(guān)鍵碼比較次數(shù)為次對象。直接插入排序的算法分析數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 ? 最壞情況下，第最壞情況下，第 i趟插入時，第趟插入時，第 i個對象必須與個對象必須與前面前面 i1個對象都做關(guān)鍵碼比較，并且每做個對象都做關(guān)鍵碼比較，并且每做 1 次比較就要做次比較就要做 1 次數(shù)據(jù)移動。則總的關(guān)鍵碼比較次數(shù)比較次數(shù) KCN和對象移動次數(shù)和對象移動次數(shù) RMN分別為分別為數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 ?若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵碼比較次數(shù)和對象移動次數(shù)約為均情況下的關(guān)鍵碼比較次數(shù)和對象移動次數(shù)約為 n2/4。?直接插入排序是一種穩(wěn)定的排序方法直接插入排序是一種穩(wěn)定的排序方法 。時間效率： 雖然比較次數(shù)大大減少，可惜移動次數(shù)并未減少，所以排序效率仍為 O(n2) 。 在已形成的 有序表中 折半查找 ，并在適當(dāng)位置插入，把原來位置上的元素向后 順移 。就平均性能來說比直接插入排序要快。次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 3）表插入排序基本思想基本思想 ：： 在順序存儲結(jié)構(gòu)中，給每個記錄增開一個指針分在順序存儲結(jié)構(gòu)中，給每個記錄增開一個指針分量，在排序過程中將指針內(nèi)容逐個修改為已經(jīng)整理（排序）量，在排序過程中將指針內(nèi)容逐個修改為已經(jīng)整理（排序）過的后繼記錄地址。優(yōu)點：優(yōu)點： 在排序過程中不移動元素，只修改指針?；貞洠烘湵砼判?—— 排序時只移動指針 ；地址排序 —— 排序時先移動地址，最后再移動記錄。此方法具有鏈表排序和地址排序的特點。解： 假設(shè)該序列（結(jié)構(gòu)類型 )已存入一維數(shù)組 V[7]中，將V[0]作為表頭結(jié)點 。 list ) { [0].Key = MaxNum。 [1].Link = 0。 i = 。 //current=當(dāng)前記錄指針 int pre = 0。 // current指針準(zhǔn)備 后移 , pre跟上 ； current = [current]. Link。 //新記錄 v[i]找到合適序位開始插入 [pre]. Link = i。但由于比較次數(shù)沒有減少，故 時間效率仍為 O(n2) 。③ 穩(wěn)定性： 25和 25*排序前后次序未變， 穩(wěn)定 。改進： 可以根據(jù)表中指針線索，很快對所有記錄重排，形成真正的有序表（順序存儲方式），從而能滿足折半查找方式。數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 4）希爾（ shell） 排序 （又稱縮小增量排序 ）基本思想基本思想 ：先將整個待排記錄序列分割成若干子序列：先將整個待排記錄序列分割成若干子序列 ,分分別進行直接插入排序，待整個序列中的記錄別進行直接插入排序，待整個序列中的記錄 ““ 基本有序基本有序”” 時，再對全體記錄進行一次直接插入排序。技巧技巧 ：： 子序列的構(gòu)成不是簡單地子序列的構(gòu)成不是簡單地 ““ 逐段分割逐段分割 ”” ，而是將，而是將相隔某個增量相隔某個增量 dk的的 記錄組成一個子序列記錄組成一個子序列 ,讓增量讓增量 dk逐趟逐趟 縮縮短（例如依次取短（例如依次取 5,3,1），直到），直到 dk＝＝ 1為止。優(yōu)點優(yōu)點 ：： 讓關(guān)鍵字值小的元素能很快前移，且序列若基本讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 38例： 關(guān)鍵字序列 T=(49， 38， 65， 97, 76, 13, 27, 49*， 55, 04）， 請寫出希爾排序的具體實現(xiàn)過程。r[i]數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 void ShellSort(SqList amp。但想要弄清鍵碼的比較次數(shù)和對象移動次數(shù)。有人能夠做到。這是在利用。到的。L， int dk) { for(i=dk+1； i=； ++ i) if(r[i].key r[idk].key) { r[0]=r[i]； for(j=idk。amp。 j=jdk) r[j+dk]=r[j]； r[j+dk]=r[0]； }}希爾排序算法 （其中某一趟的排序操作）參見教材 P272//對順序表 L進行一趟增量為 dk的 Shell排序， dk為步長因子//開始將 r[i] 插入有序增量子表//暫存在 r[0]//關(guān)鍵字較大的記錄在子表中后移//在本趟結(jié)束時將 r[i]插入到正確位置數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 課堂練習(xí)：1. 欲將序列（ Q, H, C, Y, P, A, M, S, R, D, F, X） 中的關(guān)鍵碼按字母升序重排，則初始步長為 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）為例，分別寫出執(zhí)行以下算法的 各趟 排序結(jié)束時，關(guān)鍵字序列的狀態(tài)，并說
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1