【正文】 for (i=1。 // 對(duì) [1] 進(jìn)行篩選 } 第十章 內(nèi)部排序 堆 排序 如何“建堆”？ 兩個(gè)問(wèn)題 : 如何“篩選”？ 定義堆類(lèi)型為 : typedef SqList HeapType。 40 55 49 73 81 64 36 12 27 98 例如 : 排序之前的關(guān)鍵字序列為 1236817349988155 現(xiàn)在，左 /右子樹(shù)都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹(shù)是個(gè)“堆”即可。 // 將剩余的 SR[j..n] 復(fù)制到 TR 第十章 內(nèi)部排序 歸并 排序 歸并排序的算法 如果記錄無(wú)序序列 R[s..t] 的兩部分 R[s..?(s+t)/2?] 和 R[?(s+t)/2?+1..t] 分別按關(guān)鍵字有序， 則利用上述歸并算法很容易將它們歸并成整個(gè)記錄序列是一個(gè)有序序列。 第十章 內(nèi)部排序 基數(shù) 排序 先對(duì) Kd1 進(jìn)行排序 ， 然后對(duì) Kd2 進(jìn)行排序，依次類(lèi)推， 直至對(duì)最主位關(guān)鍵字 K0 排序完成為止 。 4. 鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為 O(rd)。 按平均時(shí)間復(fù)雜度劃分，內(nèi)部排序可分為三類(lèi)： O(n2)的簡(jiǎn)單排序方法，O(nlogn)的高效排序方法 和 O(dn)的基數(shù)排序方法。 目錄 第十章 內(nèi)部排序 各種方法比較 一、時(shí)間性能 1. 平均的時(shí)間性能 基數(shù)排序 時(shí)間復(fù)雜度為 O(nlogn)： 快速排序、堆排序和歸并排序 時(shí)間復(fù)雜度為 O(n2)： 直接插入排序、起泡排序和 簡(jiǎn)單選擇排序 時(shí)間復(fù)雜度為 O(n): 第十章 內(nèi)部排序 2. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí) 3. 簡(jiǎn)單選擇排序、堆排序和歸并排序 的時(shí)間性能 不隨 記錄序列中關(guān)鍵字的分布而改變 。 即： 每一趟歸并的時(shí)間復(fù)雜度為 O(n)， 總共需進(jìn)行 ?log2n? 趟。 ++k) { // 將 SR中記錄由小到大地并入 TR if (SR[i].key=SR[j].key) TR[k] = SR[i++]。 // 否則記錄上移，尚需繼續(xù)往下調(diào)整 if ( jm amp。 // 建大頂堆 for ( i=。 第十章 內(nèi)部排序 快速 排序 四、快速排序的時(shí)間分析 假設(shè) 一次劃分所得樞軸位置 i=k，則對(duì) n 個(gè)記錄進(jìn)行快排所需時(shí)間 其中 Tpass(n)為對(duì) n 個(gè)記錄進(jìn)行一次劃分所需時(shí)間， 若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則 k 取 1 至 n 中任意一值的可能性相同。 R[high].key=pivotkey) high。 致使 一趟排序 之后，記錄的無(wú)序序列 R[s..t]將 分割成兩部分 ： R[s..i1]和 R[i+1..t], 且 R[j].key≤ R[i].key ≤ R[j].key (s≤j≤i1) 樞軸 (i+1≤j≤t) 第十章 內(nèi)部排序 快速 排序 52 49 80 36 14 58 61 97 23 75s t low high 設(shè) R[s]=52 為樞軸暫存在 R[0]的位置上 將 R[high].key 和 樞軸的關(guān)鍵字進(jìn)行比較，要求 R[high].key ≥ 樞軸的關(guān)鍵字 將 R[low].key 和 樞軸的關(guān)鍵字進(jìn)行比較，要求 R[low].key ≤ 樞軸的關(guān)鍵字 high 23 low 80 high 14 low 52 例如 R[0] 52 low hig high high low 第十章 內(nèi)部排序 快速 排序 可見(jiàn)，經(jīng)過(guò)“ 一次劃分 ” ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為 : 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調(diào)整過(guò)程中，設(shè)立了兩個(gè)指針 : low 和high，它們的初值分別為 : s 和 t, 之后逐漸減小 high，增加 low，并保證 R[high].key≥52，和 R[low].key≤52,否則進(jìn)行記錄的 “ 交換 ” 。 // 插入 } // if } // ShellInsert 第十章 內(nèi)部排序 插入排序 void ShellSort (SqList amp。 // 交換記錄，使第 i個(gè)記錄到位 SL[i].next = p。 SL[0].key = MAXINT 。 二、折半插入排序 第十章 內(nèi)部排序 插入排序 void BiInsertionSort ( SqList amp。 for ( i=2。 例如： 將下列關(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 } 的 操作 稱(chēng)作 排序 。logn) 的高效排序方法和 O (d // 設(shè)置“哨兵” 循環(huán)結(jié)束表明 R[i]的插入位置為 j +1 R[0] j R[i] for (j=i1。 // 復(fù)制為監(jiān)視哨 [i] = [i1]。 high = i1。 } // 結(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 ) if ( [i].key [idk].key){//將 [i]插入有序子 [0] = [i]。 j++) lastExchangeIndex = 1。 R[low].key=pivotkey) ++low。 無(wú) 序 的 記 錄 序 列 無(wú)序記錄子序列 (1) 無(wú)序子序列 (2) 樞軸 一次劃分 分別進(jìn)行快速排序 第十章 內(nèi)部排序 快速 排序 void QSort (RedTypeamp。 r2i+1 是 ri 的右孩子。 // 暫存 R[s] for ( j=2*s。即： 將兩個(gè)位置相鄰的記錄有序子序列 歸并為一個(gè)記錄的有序序列 。 // 將 SR[s..t]平分為 SR[s..m]和 SR[m+1..t] Msort (SR, TR2, s, m)。 第十章 內(nèi)部排序 基數(shù) 排序 例如：對(duì)下列這組關(guān)鍵字 {209, 386, 768, 185, 247, 606, 230, 834, 539 } 首先按其 “個(gè)位數(shù)” 取值分別為 0, 1, …, 9 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)? 它們 “收集” 在一起 。 例如 : 對(duì) { 4, 3, 4, 2 } 進(jìn)行快速排序， 得到 { 2, 3, 4, 4 } 第十章 內(nèi)部排序 各種方法比較 四、關(guān)于“排序方法的時(shí)間復(fù)雜度的下限” 本章討論的各種排序方法，除基數(shù)排序外，其它方法都是 基于“比較關(guān)鍵字”進(jìn)行排序的排序方法。 (基數(shù)排序不是基于“比較關(guān)鍵字”的排序方法，所以它不受這個(gè)限制 ) 第十章 內(nèi)部排序 各種方法比較 目錄 排序方法 平均時(shí)間 最壞情況 輔助存儲(chǔ) 穩(wěn)定排序 簡(jiǎ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. 了解 排序的定義和各種排序方法的特點(diǎn)。 Ri(K) Rj(K) 第十章 內(nèi)部排序 基數(shù) 排序 在計(jì)算機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，應(yīng)采用鏈表作存儲(chǔ)結(jié)構(gòu)， 即鏈?zhǔn)交鶖?shù)排序，具體作法為： １． 待排序記錄以指針相鏈，構(gòu)成一個(gè)鏈表； ２ ． “ 分配 ” 時(shí)，按當(dāng)前 “ 關(guān)鍵字位 ” 所取值，將記錄分配到不同的 “ 鏈隊(duì)列 ” 中，每個(gè)隊(duì)列中記錄的 “ 關(guān)鍵字位 ” 相同； ３ ． “ 收集 ” 時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大 將各隊(duì)列首尾相鏈成一個(gè)鏈