【正文】 ype SR[], RcdType amp。 // 將剩余的 SR[i..m] 復制到 TR if (j=n) TR[k..n] = SR[j..n]。 //遞歸地 SR[m+1..t]歸并為有序的 TR2[m+1..t] Merge (TR2, TR1, s, m, t)。 對于序列中任意兩個記錄 Ri 和 Rj (1≤ ij≤ n) 都 滿足 下列 (詞典 )有序 關系： (Ki0, Ki1, … ,Kid1) (Kj0, Kj1, … ,Kjd1) 第十章 內(nèi)部排序 基數(shù) 排序 實現(xiàn)多關鍵字排序通常有兩種作法 : 最低位優(yōu)先 LSD法： 最高位優(yōu)先 MSD法： 第十章 內(nèi)部排序 基數(shù) 排序 先對 K0進行排序 ，并按 K0 的不同值將記錄序列 分成若干子序列 之后， 分別對 K1 進行排序 ， ...… ， 依次類推， 直至最后對最次位關鍵字排序完成為止 。 第十章 內(nèi)部排序 基數(shù) 排序 在計算機上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應采用鏈表作存儲結(jié)構(gòu)， 即鏈式基數(shù)排序，具體作法為： １． 待排序記錄以指針相鏈，構(gòu)成一個鏈表； ２ ． “ 分配 ” 時，按當前 “ 關鍵字位 ” 所取值，將記錄分配到不同的 “ 鏈隊列 ” 中，每個隊列中記錄的 “ 關鍵字位 ” 相同； ３ ． “ 收集 ” 時，按當前關鍵字位取值從小到大 將各隊列首尾相鏈成一個鏈表 。 各種方法比較 第十章 內(nèi)部排序 3. 歸并排序 所需輔助空間最多，其空間復雜度為 O(n)。 Ri(K) Rj(K) (基數(shù)排序不是基于“比較關鍵字”的排序方法，所以它不受這個限制 ) 第十章 內(nèi)部排序 各種方法比較 目錄 排序方法 平均時間 最壞情況 輔助存儲 穩(wěn)定排序 簡單排序 O(n2) O(n2) O(1) ? 希爾排序 O(n3/2) O(n2) O(1) 快速排序 O(nlogn) O(n2) O(logn) 堆 排 序 O(nlogn) O(nlogn) O(1) 歸并排序 O(nlogn) O(nlogn) O(n) ? 基數(shù)排序 O(d(n+rd)) O(d(n+rd)) O(rd) ? 第十章 內(nèi)部排序 本章小結(jié) 1. 了解 排序的定義和各種排序方法的特點。 第十章 內(nèi)部排序 本章小結(jié) 3． 理解排序方法 “ 穩(wěn)定 ” 或 “ 不穩(wěn)定 ”的含義，弄清楚在 什么情況下 要求應用的排序方法必須是穩(wěn)定的。 例如 : 對 { 4, 3, 4, 2 } 進行快速排序， 得到 { 2, 3, 4, 4 } 第十章 內(nèi)部排序 各種方法比較 四、關于“排序方法的時間復雜度的下限” 本章討論的各種排序方法，除基數(shù)排序外，其它方法都是 基于“比較關鍵字”進行排序的排序方法。 Rj(K) 直接插入排序 和 起泡排序 能達到 O(n)的時間復雜度 。 第十章 內(nèi)部排序 基數(shù) 排序 例如：對下列這組關鍵字 {209, 386, 768, 185, 247, 606, 230, 834, 539 } 首先按其 “個位數(shù)” 取值分別為 0, 1, …, 9 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)? 它們 “收集” 在一起 。 目錄 第十章 內(nèi)部排序 基數(shù) 排序 基數(shù)排序是一種 借助 “多關鍵字排序” 的思想來實現(xiàn)“單關鍵字排序”的內(nèi)部排序算法。 // 將 SR[s..t]平分為 SR[s..m]和 SR[m+1..t] Msort (SR, TR2, s, m)。 else TR[k] = SR[j++]。即： 將兩個位置相鄰的記錄有序子序列 歸并為一個記錄的有序序列 。amp。 // 暫存 R[s] for ( j=2*s。 i1。 r2i+1 是 ri 的右孩子。 T(n) = Tpass(n) + T(k1) + T(nk) 第十章 內(nèi)部排序 快速 排序 ? ????????nka v ga v ga v g knTkTnCnnT1)()1(1)(設 Tavg(1)≤ b 則可得結(jié)果 : )1l n ()1)(22()( ???? nncbnT a v g結(jié)論 : 快速排序的時間復雜度為 O(nlogn) 由此可得快速排序所需時間的平均值為： 第十章 內(nèi)部排序 快速 排序 若待排記錄的初始狀態(tài)為按關鍵字有序時，快速排序?qū)⑼懟癁槠鹋菖判?，其時間復雜度為 O(n2)。 無 序 的 記 錄 序 列 無序記錄子序列 (1) 無序子序列 (2) 樞軸 一次劃分 分別進行快速排序 第十章 內(nèi)部排序 快速 排序 void QSort (RedTypeamp。 // 從右向左搜索 R[low] = R[high]。 R[low].key=pivotkey) ++low。 第十章 內(nèi)部排序 快速 排序 int Partition (RedTypeamp。 j++) lastExchangeIndex = 1。L, int dlta[], int t) { // 增量為 dlta[]的希爾排序 for (k=0。 ++i ) if ( [i].key [idk].key){//將 [i]插入有序子 [0] = [i]。 // 指向被移走的記錄， }//if p = q。 } // 結(jié)點 i插入在結(jié)點 j和結(jié)點 k之間 }// LinsertionSort 第十章 內(nèi)部排序 插入排序 算法中使用了三個指針 : 其中： p 指示第 i 個記錄的當前位置； i 指示第 i 個記錄應在的位置； q 指示第 i+1 個記錄的當前位置。 SL[0].next = 1。 high = i1。L ) { } // BInsertSort 在 [1..i1]中折半查找插入位置； for ( i=2。 // 復制為監(jiān)視哨 [i] = [i1]。 i=n。 // 設置“哨兵” 循環(huán)結(jié)束表明 R[i]的插入位置為 j +1 R[0] j R[i] for (j=i1。 第十章 內(nèi)部排序 概 述 二、內(nèi)部排序和外部排序 若 整個排序過程不需要訪問外存 便能完成，則稱此類排序問題 為內(nèi)部排序 反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程 不可能在內(nèi)存中完成 ，則稱此類排序問題 為外部排序 。logn) 的高效排序方法和 O (d按平均時間復雜度劃分，內(nèi)部排序可分為三類： O (n2) 的簡單排序方法， O (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)部排序 概 述 一般情況下， 假設含 n個記錄的序列為 { R1, R2, … ， Rn } 其相應的關鍵字序列為 { K1, K2, … ， Kn } 這些關鍵字相互之間可以進行比較，即在 它們之間存在著這樣一個關系 Kp1≤ Kp2≤ … ≤ Kpn 按此固有關系將上式記錄序列重新排列為 { Rp1, Rp2, … ， Rpn } 的 操作 稱作 排序 。 2． 將 R[j+1..i1]中的所有 記錄 均 后移 一個位置； 1． 在 R[1..i1]中 查找 R[i]的插入位置 j ； R[1..j].key ? R[i].key R[j+1..i1].key 第十章 內(nèi)部排序 插入排序 直接插入排序 （基于順序查找） 表插入排序 （基于鏈表存儲） 不同的具體實現(xiàn)方法導致不同的算法描述 折半插入排序 （基于折半查找） 希爾排序 （基于逐趟縮小增量） 目錄 第十章 內(nèi)部排序 插入排序 一、直接插入排序 利用 “順序查找” 實現(xiàn) “在 R[1..i1]中 查找 R[i]的插入位置” 算法的實現(xiàn)要點： 第十章 內(nèi)部排序 插入排序 從 R[i1]起向前進行順序查找，監(jiān)視哨設置在 R[0]； R[0] = R[i]。 for ( i=2。 ++i ) if ([i].key [i1].key) { }//if } // InsertSort [0] = [i]。 二、折半插入排序 第十章 內(nèi)部排序 插入排序 void BiInsertionSort ( SqList amp。 // 插入 第十章 內(nèi)部排序 插入排序 low = 1。 SL[0].key = MAXINT 。 SL[i].next = k。 // 交換記錄，使第 i個記錄到位 SL[i].next = p。 i=n。 // 插入 } // if } // ShellI