【正文】 為次對象。 對應(yīng)程序參見教材 P265。 *表示后一個 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）。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。 //順序表的長度}SqList 。 //關(guān)鍵字 InfoType otherinfo。注： 外部排序時，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時放入外存，顯然外部排序要復(fù)雜得多。數(shù) 據(jù) 結(jié) 構(gòu)—— With C/C++主講教師：石振鋒主講教師：石振鋒哈爾濱工業(yè)大學(xué)數(shù)學(xué)系哈爾濱工業(yè)大學(xué)數(shù)學(xué)系2022年 6月1數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 概述 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序第 9章 內(nèi)部排序數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 概述1. 什么是排序？ 將一組雜亂無章的 數(shù)據(jù) 按一定的 規(guī)律 順次排列起來。 ？① 順序 排序 —— 排序時直接移動記錄；② 鏈表 排序 —— 排序時只移動指針；③ 地址 排序 —— 排序時先移動地址，最后再移動記錄。 //其它數(shù)據(jù)項}RecordType 。 define MAXSIZE 20 //設(shè)記錄不超過 20個typedef int KeyType 。數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 1) 直接插入排序新元素插入到哪里？例 1： 關(guān)鍵字序列 T=（ 13， 6， 3， 31， 9， 27， 5， 11）， 請寫出直接插入排序的中間過程序列。 則程序執(zhí)行過程為：21 25 49初態(tài)：16 25*25211608完成完成 !時間效率： O(n2)—— 因為在最壞情況下，所有元素的比較次數(shù)總和為（ 0＋ 1＋ … ＋ n1)→O(n 2)。數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 n 若設(shè)待排序的對象個數(shù)為若設(shè)待排序的對象個數(shù)為 n， 則算法需要進(jìn)行則算法需要進(jìn)行 n1次插入。因此，總的關(guān)鍵碼比較次數(shù)為 n1，對象移動次數(shù)為對象移動次數(shù)為 2(n1)。在平，則可取上述最好情況和最壞情況的平均情況。數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 2） 折半插入排序優(yōu)點(diǎn)： 比較的次數(shù)大大減少，全部元素比較次數(shù)僅為 O(nlog2n)。但鏈表無法但鏈表無法 ““ 折半折半 ”” ??！數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 折半插入排序的算法分析? 折半查找比順序查找快，所以折半插入排序折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。因此，將因此，將 n 個對象用折半插入排序所進(jìn)行個對象用折半插入排序所進(jìn)行的關(guān)鍵碼比較次數(shù)為：的關(guān)鍵碼比較次數(shù)為： n*log2n? 折半插入排序是一個穩(wěn)定的排序方法折半插入排序是一個穩(wěn)定的排序方法 。在排序過程中不移動元素，只修改指針。數(shù)學(xué)系計算數(shù)學(xué)教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 1例： 關(guān)鍵字序列 T=(21， 25， 49， 25*， 16，08）， 請寫出表插入排序的具體實(shí)現(xiàn)過程。 [0]. Link = 1。 i++ ) { int current = [0]. Link。 } //找插入位置 (即 p=plink)[i]. Link = current。② 空間效率肯定低 ，因為增開了指針分量（但在運(yùn)算過程中沒有用到更多的輔助單元）。 具體實(shí)現(xiàn)見教材 P269。為止。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 的值較大，子序列中的對象較少，排序速度較快；隨著排序進(jìn)展， dk 值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。但想要弄清關(guān)鍵碼比較次數(shù)和對象移動次數(shù)與增量選擇之關(guān)鍵碼比較次數(shù)和對象移動次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒有人能夠做到。這是在利用直接插入排序作為子序列排序方法的情況下得直接插入排序作為子序列排序方法的情況下得到的。 j0 amp。 兩種排序方法的中間狀態(tài)分別描述如后：數(shù)學(xué)系計算數(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， 937]， 076， 438[076， 129， 256， 301， 694， 742， 751， 863， 937]， 438[076， 129， 256， 301， 438， 694， 742， 751， 863， 937]第 1趟第 2趟第 3趟第 4趟第 5