數(shù)據(jù)結(jié)構(gòu)排序ppt課件-文庫吧資料
2025-05-06 18:12本頁面
【正文】 301， 751， 129， 937， 863， 742， 694， 076， 438(取 dk=5,3,1)256， 301， 751， 129， 937， 863， 742， 694， 076， 438， ， ， ， ， ， ， ， ， ， 694， ， ， ， ， 751， ， ， ， 076， ， ， ， ， 129， ， ， ， 438， ， ， ， ， 937第 1趟dk=5第 2趟dk=3第 3趟dk=1256， 301， 694， 076， 438， 863， 742， 751， 129， 937， ， ， ， ， ， ， ， ，076， ， ， 256， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 129， ， ， 694， ， ， 863，076， 301， 129， 256， 438， 694， 742， 751， 863， 937， ， ， ， ， ， ， ， ， 129， 256， 301， ， ， ， ， ，數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 交換排序 兩兩比較待排序記錄的關(guān)鍵兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。(r[0].keyr[j].key)。 j0 amp。數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 void ShellInsert(SqList amp。這是在利用直接插入排序作為子序列排序方法的情況下得直接插入排序作為子序列排序方法的情況下得到的。Knuth利用大量的實驗統(tǒng)計資料得出，當利用大量的實驗統(tǒng)計資料得出，當 n很大很大時，時， 關(guān)鍵碼平均比較次數(shù)和對象平均移動次數(shù)關(guān)鍵碼平均比較次數(shù)和對象平均移動次數(shù)大約在大約在 到到 的范圍內(nèi)的范圍內(nèi) 。但想要弄清關(guān)鍵碼比較次數(shù)和對象移動次數(shù)與增量選擇之關(guān)鍵碼比較次數(shù)和對象移動次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學分析，還沒間的依賴關(guān)系，并給出完整的數(shù)學分析，還沒有人能夠做到。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（（ ）） —— 經(jīng)驗公式dk值依次裝在 dlta[t]中數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 附：希爾排序 算法分析對特定的待排序?qū)ο笮蛄?，可以準確地估算關(guān)對特定的待排序?qū)ο笮蛄?，可以準確地估算關(guān)鍵碼的比較次數(shù)和對象移動次數(shù)。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 值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎，大多數(shù)對象已基本有序，所以排序速度仍然很快。有序時，再用直接插入排序處理，時間效率會高很多。為止。時，再對全體記錄進行一次直接插入排序。 具體實現(xiàn)見教材 P269。討論： 此算法得到的只是一個有序鏈表，查找記錄時只能滿足順序查找方式。② 空間效率肯定低 ，因為增開了指針分量（但在運算過程中沒有用到更多的輔助單元）。 //在 pre與 current之間鏈入 }}數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 表插入排序算法分析：① 無需移動記錄，只需修改 2n次指針值。 } //找插入位置 (即 p=plink)[i]. Link = current。 //pre=當前記錄 current的前驅(qū)指針 while ( [current]. Key = [i]. Key) { pre = current。 i++ ) { int current = [0]. Link。 //形成循環(huán)鏈表表插入排序的算法for ( int i = 2。 [0]. Link = 1。 則 算法執(zhí)行過程 為：i 關(guān) 鍵 字 V[i].key 指 針 V[i].link0 MaxNum1 212 253 494 25*5 166 08指向第 1個元素指向頭結(jié)點初態(tài)初態(tài)i=1i=2i=3i=4i=5i=603456503102*表示后一個 25數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 int LinkInsertSort ( staticlinklisType amp。數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 1例： 關(guān)鍵字序列 T=(21， 25， 49， 25*， 16，08）， 請寫出表插入排序的具體實現(xiàn)過程。此方法具有鏈表排序和地址排序的特點。在排序過程中不移動元素，只修改指針。過的后繼記錄地址。因此，將因此，將 n 個對象用折半插入排序所進行個對象用折半插入排序所進行的關(guān)鍵碼比較次數(shù)為：的關(guān)鍵碼比較次數(shù)為： n*log2n? 折半插入排序是一個穩(wěn)定的排序方法折半插入排序是一個穩(wěn)定的排序方法 。? 在插入第在插入第 i 個對象時，需要經(jīng)過個對象時，需要經(jīng)過 ?log2i? +1 次關(guān)鍵碼比較，才能確定它應插入的位置。但鏈表無法但鏈表無法 ““ 折半折半 ”” ！！數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 折半插入排序的算法分析? 折半查找比順序查找快，所以折半插入排序折半查找比順序查找快，所以折半
教學課件相關(guān)推薦
鄂ICP備17016276號-1