【正文】 a v g結論 : 快速排序的時間復雜度為 O(nlogn) 由此可得快速排序所需時間的平均值為： 第十章 內(nèi)部排序 快速 排序 若待排記錄的初始狀態(tài)為按關鍵字有序時，快速排序將蛻化為起泡排序 ，其時間復雜度為 O(n2)。 in。 r2i+1 是 ri 的右孩子。 } // HeapSort for ( i=。 i1。 // 堆采用順序表表示之 第十章 內(nèi)部排序 堆 排序 所謂 “篩選” 指的是，對一棵左 /右子樹 均為堆的完全二叉樹， “調(diào)整”根結點 使整個二叉樹也成為一個堆 。 // 暫存 R[s] for ( j=2*s。 // 將調(diào)整前的堆頂記錄插入到 s 位置 第十章 內(nèi)部排序 堆 排序 if ( = R[j].key ) break。amp。 9840第十章 內(nèi)部排序 堆 排序 堆排序的時間復雜度分析： 1. 對深度為 k 的堆，“篩選”所需進行的關鍵字 比較的次數(shù)至多為 2(k1)。即： 將兩個位置相鄰的記錄有序子序列 歸并為一個記錄的有序序列 。 i=m amp。 else TR[k] = SR[j++]。 由此，應該先分別對這兩部分進行 2路歸并排序。 // 將 SR[s..t]平分為 SR[s..m]和 SR[m+1..t] Msort (SR, TR2, s, m)。L) {// // 對順序表 L 作 2路歸并排序。 目錄 第十章 內(nèi)部排序 基數(shù) 排序 基數(shù)排序是一種 借助 “多關鍵字排序” 的思想來實現(xiàn)“單關鍵字排序”的內(nèi)部排序算法。 排序過程中不需要根據(jù) “ 前一個 ” 關鍵字的排序結果，將記錄序列分割成若干個 (“前一個 ” 關鍵字不同的 )子序列。 第十章 內(nèi)部排序 基數(shù) 排序 例如：對下列這組關鍵字 {209, 386, 768, 185, 247, 606, 230, 834, 539 } 首先按其 “個位數(shù)” 取值分別為 0, 1, …, 9 “分配” 成 10 組，之后按從 0 至 9 的順序將 它們 “收集” 在一起 。 第十章 內(nèi)部排序 基數(shù) 排序 例如： p→ 369→ 367→ 167→ 239→ 237→ 138→ 230→ 139 進行第一次分配 進行第一次收集 f[0] r[0] f[7] r[7] f[8] r[8] f[9] r[9] p→230 → 230← → 367 ← →16 7 →23 7 →367→167→237 →138 →368→239→139 → 369 ← →23 9 →13 9 → 138← 第十章 內(nèi)部排序 基數(shù) 排序 進行第二次分配 p→230→237→138→239→139 p→230→367→167→237→138→368→239→139 f[3] r[3] f[6] r[6] → 230 ← →2 37→1 38→2 39 →1 39 → 367 ← →1 67 →3 68 →367→167→368 進行第二次收集 第十章 內(nèi)部排序 基數(shù) 排序 進行第三次收集之后便得到記錄的有序序列 f[1] r[1] p→230→237→138→239→139→367→167→368 進行第三次分配 f[2] r[2] f[3] r[3] → 138 ← → 139 → 167 → 230 ← → 237 → 239 → 367 ← → 368 p→138→139→167 →230→237→239 →367→368 第十章 內(nèi)部排序 基數(shù) 排序 提醒注意： １． “ 分配 ” 和 “ 收集 ” 的實際操作僅為修改鏈表中的指針和設置隊列的頭、尾指針； ２．為查找使用，該鏈表尚需應用算法 Arrange() 將它調(diào)整為有序表。 直接插入排序 和 起泡排序 能達到 O(n)的時間復雜度 。 各種方法比較 第十章 內(nèi)部排序 各種方法比較 三、排序方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對于 兩個關鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。 Rj(K) } 第十章 內(nèi)部排序 各種方法比較 例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 ) 若排序后得到結果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 則稱該排序方法是 穩(wěn)定 的 。 例如 : 對 { 4, 3, 4, 2 } 進行快速排序， 得到 { 2, 3, 4, 4 } 第十章 內(nèi)部排序 各種方法比較 四、關于“排序方法的時間復雜度的下限” 本章討論的各種排序方法，除基數(shù)排序外，其它方法都是 基于“比較關鍵字”進行排序的排序方法?；?“ 關鍵字間的比較 ” 進行排序的方法可以按排序過程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序等五類。 第十章 內(nèi)部排序 本章小結 3． 理解排序方法 “ 穩(wěn)定 ” 或 “ 不穩(wěn)定 ”的含義，弄清楚在 什么情況下 要求應用的排序方法必須是穩(wěn)定的。能從 “ 關鍵字間的比較次數(shù) ” 分析排序算法的 平均 情況和 最壞 情況的時間性能。 (基數(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)部排序 本章小結 1. 了解 排序的定義和各種排序方法的特點。 第十章 內(nèi)部排序 各種方法比較 2. 對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。 Ri(K) Rj(K) 排序之前 : { 各種方法比較 第十章 內(nèi)部排序 3. 歸并排序 所需輔助空間最多，其空間復雜度為 O(n)。 收集為 O(rd)(rd為“基” ), d為“分配 收集”的趟數(shù)。 第十章 內(nèi)部排序 基數(shù) 排序 在計算機上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應采用鏈表作存儲結構， 即鏈式基數(shù)排序，具體作法為： １． 待排序記錄以指針相鏈，構成一個鏈表； ２ ． “ 分配 ” 時，按當前 “ 關鍵字位 ” 所取值，將記錄分配到不同的 “ 鏈隊列 ” 中，每個隊列中記錄的 “ 關鍵字位 ” 相同； ３ ． “ 收集 ” 時，按當前關鍵字位取值從小到大 將各隊列首尾相鏈成一個鏈表 。 無序序列 對 K2排序 對 K1排序 對 K0排序 3,2,30 1,2,15 3,1,20 2,3,18 2,1,20 1,2,15 2,3,18 3,1,20 2,1,20 3,2,30 3,1,20 2,1,20 1,2,15 3,2,30 2,3,18 1,2,15 2,1,20 2,3,18 3,1,20 3,2,30 LSD的排序過程如下 : 第十章 內(nèi)部排序 基數(shù) 排序 二、鏈式基數(shù)排序 假如多關鍵字的記錄序列中，每個關鍵字的取值范圍相同，則按 LSD法進行排序時，可以采用 “分配 收集 ” 的方法，其好處是不需要進行關鍵字間的比較。 對于序列中任意兩個記錄 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 進行排序 ， ...… ， 依次類推， 直至最后對最次位關鍵字排序完成為止 。 } // MergeSort 容易看出，對 n 個記錄進行歸并排序的時間復雜