【正文】 st amp。amp。 i=n。 具體做法為： 第十章 內(nèi)部排序 插入排序 將記錄序列分成若干子序列，分別對(duì)每個(gè)子序列進(jìn)行插入排序。 // 交換記錄，使第 i個(gè)記錄到位 SL[i].next = p。 in。 SL[i].next = k。 i=n。 SL[0].key = MAXINT 。 // 插入點(diǎn)在低半?yún)^(qū) else low = m+1。 // 插入 第十章 內(nèi)部排序 插入排序 low = 1。 // 將 [i] 暫存到 [0] for ( j=i1。 二、折半插入排序 第十章 內(nèi)部排序 插入排序 void BiInsertionSort ( SqList amp。 j ) [j+1] = [j]。 ++i ) if ([i].key [i1].key) { }//if } // InsertSort [0] = [i]。 } 第十章 內(nèi)部排序 插入排序 void InsertionSort ( SqList amp。 for ( i=2。 // 從后往前找 j=i1 插入位置 第十章 內(nèi)部排序 對(duì)于在查找過程中找到的那些關(guān)鍵字不小于 R[i].key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)； 插入排序 for (j=i1。 2． 將 R[j+1..i1]中的所有 記錄 均 后移 一個(gè)位置； 1． 在 R[1..i1]中 查找 R[i]的插入位置 j ； R[1..j].key ? R[i].key R[j+1..i1].key 第十章 內(nèi)部排序 插入排序 直接插入排序 （基于順序查找） 表插入排序 （基于鏈表存儲(chǔ)） 不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述 折半插入排序 （基于折半查找） 希爾排序 （基于逐趟縮小增量） 目錄 第十章 內(nèi)部排序 插入排序 一、直接插入排序 利用 “順序查找” 實(shí)現(xiàn) “在 R[1..i1]中 查找 R[i]的插入位置” 算法的實(shí)現(xiàn)要點(diǎn)： 第十章 內(nèi)部排序 插入排序 從 R[i1]起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在 R[0]； R[0] = R[i]。 第十章 內(nèi)部排序 概 述 2. 交換類 通過 “交換” 無序序列中的記錄從而得到其中 關(guān)鍵字最小 或 最大的記錄，并將它 加入到有序子序列中 ， 以此方法增加記錄的有序子序列的長度。 例如： 將下列關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 調(diào)整為 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 第十章 內(nèi)部排序 概 述 一般情況下， 假設(shè)含 n個(gè)記錄的序列為 { R1, R2, … ， Rn } 其相應(yīng)的關(guān)鍵字序列為 { K1, K2, … ， Kn } 這些關(guān)鍵字相互之間可以進(jìn)行比較，即在 它們之間存在著這樣一個(gè)關(guān)系 Kp1≤ Kp2≤ … ≤ Kpn 按此固有關(guān)系將上式記錄序列重新排列為 { Rp1, Rp2, … ， Rpn } 的 操作 稱作 排序 。 ?重點(diǎn)和難點(diǎn) 希爾排序、快速排序、堆排序和歸并排序等高效方法是本章的學(xué)習(xí)重點(diǎn)和難點(diǎn) ?知識(shí)點(diǎn) 排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、堆排序、 2路歸并排序、基數(shù)排序、排序方法的綜合比較 本章說明 第十章 內(nèi)部排序 ?學(xué)習(xí)指南 本章學(xué)習(xí)的要點(diǎn)主要是了解各種排序方法實(shí)現(xiàn)時(shí)所依據(jù)的原則以及它們的 主要操作（ 關(guān)鍵字間的 比較 和 記錄的 移動(dòng) ）的時(shí)間分析。按平均時(shí)間復(fù)雜度劃分，內(nèi)部排序可分為三類： O (n2) 的簡單排序方法， O (n第十章 內(nèi)部排序 本 章 說 明 概 述 插入排序 快速排序 堆 排 序 歸并排序 基數(shù)排序 各種方法比較 本 章 小 結(jié) 數(shù)據(jù)結(jié)構(gòu) 返回主目錄 第十章 內(nèi)部排序 ?學(xué)習(xí)目標(biāo) ?理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用。logn) 的高效排序方法和 O (d學(xué)習(xí)中應(yīng)注意 掌握 各種 排序方法實(shí)現(xiàn)的要點(diǎn) ，可通過對(duì)基礎(chǔ)知識(shí)題中算法的手工執(zhí)行和比較分析，切實(shí)掌握各種排序過程的排序特點(diǎn)所在，注意同一排序方法在不同的教科書上可以有不同書寫形式描述的算法。 第十章 內(nèi)部排序 概 述 二、內(nèi)部排序和外部排序 若 整個(gè)排序過程不需要訪問外存 便能完成，則稱此類排序問題 為內(nèi)部排序 反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程 不可能在內(nèi)存中完成 ，則稱此類排序問題 為外部排序 。 第十章 內(nèi)部排序 概 述 3. 選擇類 從記錄的無序子序列中 “選擇”關(guān)鍵字最小或最大 的記錄，并將它加入到有序子序列 中，以此方法增加記錄的有序子序列的長度。 // 設(shè)置“哨兵” 循環(huán)結(jié)束表明 R[i]的插入位置為 j +1 R[0] j R[i] for (j=i1。 R[0].keyR[j].key。 i=n。L ) { // 對(duì)順序表 L 作直接插入排序。 // 復(fù)制為監(jiān)視哨 [i] = [i1]。 // 記錄后移 [j+1] = [0]。L ) { } // BInsertSort 在 [1..i1]中折半查找插入位置； for ( i=2。 j=low。 high = i1。 // 插入點(diǎn)在高半?yún)^(qū) 第十章 內(nèi)部排序 插入排序 i low high m m low low m highi low high m high m high m low 例如 : 再如 : 插入 位置 插入 位置 14 36 49 52 80 58 61 23 97 75 14 36 49 52 58 61 80 23 97 75 第十章 內(nèi)部排序 插入排序 2路插入排序 減少排序中移動(dòng)記錄的次數(shù) 設(shè)一 n個(gè)記錄的輔助數(shù)組 d,將 d看成循環(huán)向量 將 d[1]=[1],然后若 [i].keyd[1],插入在其前 ,否則插入在其后 第十章 內(nèi)部排序 插入排序 三、表插入排序 為了減少在排序過程中進(jìn)行的“移動(dòng)”記錄的操作，必須改變排序過程中采用的存儲(chǔ)結(jié)構(gòu)。 SL[0].next = 1。 ++i ) for ( j=0, k = SL[0].next。 } // 結(jié)點(diǎn) i插入在結(jié)點(diǎn) j和結(jié)點(diǎn) k之間 }// LinsertionSort 第十章 內(nèi)部排序 插入排序 算法中使用了三個(gè)指針 : 其中： p 指示第 i 個(gè)記錄的當(dāng)前位置； i 指示第 i 個(gè)記錄應(yīng)在的位置； q 指示第 i+1 個(gè)記錄的當(dāng)前位置。 ++i ) { while (pi) p = SL[p].next。 // 指向被移走的記錄， }//if p = q。 其中， d 稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序 減為 1。 ++i ) if ( [i].key [idk].key){//將 [i]插入有序子 [0] = [i]。([0].key[j].key)。L, int dlta[], int t) { // 增量為 dlta[]的希爾排序 for (k=0。 i = lastExchangeIndex。 j++) lastExchangeIndex = 1。 j i。 第十章 內(nèi)部排序 快速 排序 int Partition (RedTypeamp。 R[high].key=pivotkey) high。 R[low].key=pivotkey) ++low。 pivotkey = R[low].key。 // 從右向左搜索 R[low] = R[high]。 // 從左向右搜索 R[high] = R[low]。 無 序 的 記 錄 序 列 無序記錄子序列 (1) 無序子序列 (2) 樞軸 一次劃分 分別進(jìn)行快速排序 第十章 內(nèi)部排序 快速 排序 void QSort (RedTypeamp。 // 對(duì)高子序列遞歸排序 第十章 內(nèi)部排序 快速 排序 void QuickSort( SqList amp。 T(n) = Tpass(n) + T(k1) + T(nk) 第十章 內(nèi)部排序 快速 排序 ? ????????nka v ga v ga v g knTkTnCnnT1)()1(1)(設(shè) Tavg(1)≤ b 則可得結(jié)果 : )1l n ()1)(22()( ???? nncbnT