【正文】 第十章 內(nèi)部排序 本章小結(jié) 2. 掌握各種排序方法的 時(shí)間復(fù)雜度 。 若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 則稱該排序方法是 不穩(wěn)定 的 。 } 排序之后 : { 2. 當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)行 LSD方法排序時(shí)， 必須采用穩(wěn)定 的排序方法。 第十章 內(nèi)部排序 基數(shù) 排序 算法： 基數(shù)排序的時(shí)間復(fù)雜度為 O(d(n+rd)) 其中，分配為 O(n)。 第十章 內(nèi)部排序 基數(shù) 排序 例如 :學(xué)生記錄含三個(gè)關(guān)鍵字 : 系別 、 班號(hào) 和 班內(nèi)的序列號(hào) ，其中以系別為 “ 最主 ” 位關(guān)鍵字。 MSort(, , 1, )。 第十章 內(nèi)部排序 歸并 排序 52, 23, 80, 36, 68, 14 (s=1, t=6) [ 52, 23, 80] [36, 68, 14] [ 52, 23] [80] [ 52] [ 23, 52] [ 23, 52, 80] [36, 68] [14] [36] [36, 68] [14, 36, 68] [ 14, 23, 36, 52, 68, 80 ] [23] [ 52] [23] [36] [68] [80] [14] [68] 例如： 第十章 內(nèi)部排序 歸并 排序 void Msort ( RcdType SR[], RcdType amp。amp。 2. 對(duì) n 個(gè)關(guān)鍵字，建成深度為 h (=?log2n?+1) 的 堆， 所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多 4n。 // 再作“根”和“子樹根”之間的比較， // 若“ =”成立，則說明已找到 rc 的插 // 入位置 s ，不需要繼續(xù)往下調(diào)整 R[s] = R[j]。 堆 堆 篩選 第十章 內(nèi)部排序 堆 排序 98 81 49 73 55 64 12 36 27 40 例如 : 是大頂堆 12但在 98 和 12 進(jìn)行互換之后，它就 不 是堆了 因此，需要對(duì)它進(jìn)行“篩選”（堆頂?shù)饺~子） 9812 81736412比較 第十章 內(nèi)部排序 堆 排序 void HeapAdjust (RcdType amp。 i0。 ++i) { // 選擇第 i 小的記錄，并交換到位 } } // SelectSort j = SelectMinKey(R, i)。 L) { // 對(duì)順序表進(jìn)行快速排序 QSort(, 1, )。 R[low] = R[0]。 // 樞軸 while (lowhigh) { } while(lowhighamp。 R[low]←→R[high] 。 j++) if (R[j+1].key R[j].key) … 1 31. 起泡排序的結(jié)束條件為， 最后一趟沒有進(jìn)行“交換記錄”。 // 本趟進(jìn)行過交換的 // 最后一個(gè)記錄的位置 if (R[j+1].key R[j].key) { Swap(R[j], R[j+1])。 j=dk) [j+dk] = [j]。 例如：將 n 個(gè)記錄分成 d 個(gè)子序列： { R[1]， R[1+d]， R[1+2d]， … ， R[1+kd] } { R[2]， R[2+d]， R[2+2d]， … ， R[2+kd] } … { R[d]， R[2d]， R[3d]， … ， R[kd]， R[(k+1)d] } 第十章 內(nèi)部排序 插入排序 16 25 12 30 47 11 23 36 9 18 31 第一趟希爾排序，設(shè)增量 d =5 11 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序，設(shè)增量 d = 3 9 18 12 11 23 16 25 31 30 47 36 第三趟希爾排序，設(shè)增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 第十章 內(nèi)部排序 插入排序 void ShellInsert ( SqList amp。 q = SL[p].next。SL[k].key= SL[i].key 。利用靜態(tài)鏈表進(jìn)行排序，并 在排序完成之后，一次性地調(diào)整各個(gè)記錄相互之間的位置 ，即將每個(gè)記錄都調(diào)整到它們所應(yīng)該在的位置上。 j ) [j+1] = [j]。 // 插入到正確位置 第十章 內(nèi)部排序 插入排序 內(nèi)部排序的時(shí)間分析： 實(shí)現(xiàn)內(nèi)部排序的 基本操作 有兩個(gè)： （ 2） “移動(dòng)” 記錄。 for ( i=2。 j)。 第十章 內(nèi)部排序 概 述 4. 歸并類 通過 “歸并” 兩個(gè)或兩個(gè)以上的記錄有序子序列，逐步增加記錄有序序列的長(zhǎng)度。在學(xué)習(xí)本章過程中需練習(xí)的算法設(shè)計(jì)題為：， ， ， ， 和 。排序方法有不同的分類方法，基于 “ 關(guān)鍵字間的比較 ” 進(jìn)行排序的方法可以按排序過程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和計(jì)數(shù)排序等五類 ?掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。 本章說明 第十章 內(nèi)部排序 ? 理解排序方法 穩(wěn)定 或 不穩(wěn)定 的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。 經(jīng)過一趟排序 有序序列區(qū) 無(wú) 序 序 列 區(qū) 有序序列區(qū) 無(wú) 序 序 列 區(qū) 第十章 內(nèi)部排序 概 述 基于不同的“擴(kuò)大” 有序序列長(zhǎng)度的方法，內(nèi)部排序方法大致可分下列幾種類型： 插入類 交換類 選擇類 歸并類 其它方法 第十章 內(nèi)部排序 概 述 1. 插入類 將無(wú)序子序列中的 一個(gè)或幾個(gè)記錄 “插入” 到有序序列中，從而增加記錄的有序子序列的長(zhǎng)度。 j)。 插入 R[i] 。 [0].key [j].key。 ++i ) { } // for [0] = [i]。 // 折半 if ([0].key [m].key) high = m1。 for ( i=2。 // p指示第一個(gè)記錄的當(dāng)前位置 for ( i=1。 所謂“宏觀”調(diào)整，指的是，“跳躍式” 的插入排序。 j0amp。 ++t) ShellInsert(L, dlta[k])。 //記下 進(jìn)行交換的記錄位置 第十章 內(nèi)部排序 快速 排序 注意 : 2. 一般情況下，每經(jīng)過一趟“起泡”，“ i 減一”， 但并不是每趟都如此。 while (lowhigh) { while (lowhigh amp。 } return low。amp。 // 對(duì) R[s..t] 進(jìn)行一次劃分 QSort(R, s, pivotloc1)。 第十章 內(nèi)部排序 堆 排序 簡(jiǎn)單選擇排序 堆 排 序 目錄 第十章 內(nèi)部排序 堆 排序 一、簡(jiǎn)單選擇排序 假設(shè)排序過程中，待排記錄序列的狀態(tài)為： 有序序列 R[1..i1] 無(wú)序序列 R[i..n] 第 i 趟 簡(jiǎn)單選擇排序 從中選出 關(guān)鍵字最小的記錄 有序序列 R[1..i] 無(wú)序序列 R[i+1..n] 第十章 內(nèi)部排序 堆 排序 簡(jiǎn)單選擇排序 的算法描述如下： void SelectSort (Elem R[], int n ) { // 對(duì)記錄序列 R[1..n]作簡(jiǎn)單選擇排序。 例如： 建大頂堆 { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 } { 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 } 交換 98 和 12 重新調(diào)整為大頂堆 { 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 } { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 經(jīng)過篩選 第十章 內(nèi)部排序 堆 排序 void HeapSort ( HeapType amp。 // 將堆頂記錄和當(dāng)前未經(jīng)排序子序列 // [1..i]中最后一個(gè)記錄相互交換 HeapAdjust(, 1, i1)。 j*=2 ) { // j 初值指向左孩子 自上而下的篩選過程 。 // 左 /右“子樹根”之間先進(jìn)行相互比較 // 令 j 指示關(guān)鍵字較大記錄的位置 第十章 內(nèi)部排序 堆 排序 建堆是一個(gè)從下往上進(jìn)行“篩選”的過程。 第十章 內(nèi)部排序 歸并 排序 void Merge (RcdT