【正文】 97 65 49 (a) 一趟快排過程 pivotkey [初始關鍵字 ] 49 38 65 97 76 13 27 49 j i j P275 圖 初始狀態(tài) {49 38 65 97 76 13 27 49} 一次劃分之后 {27 38 13} 49 {76 97 65 49} 分別進行快速排序 {13} 27 {38} 結束 結束 {49 65} 76 {97} 49 {65} 結束 結束 有序序列 {13 27 38 49 49 65 76 97} (b) 排序的全過程 圖 快速排序示例 ③ 快速排序算法實現(xiàn) 整個快速排序的過程可遞歸進行。 若待排序列中只有一個記錄，顯然已有 序 ，否則進行一趟快速排序后再分別對分割所得的兩個子序列進行快速排序， 如圖 (b)所示。 ④ 快速排序的平均時間 快速排序的平均時間為： nknTavg ln?其中， n為待排序序列中記錄的個數(shù)， k為某個常數(shù)。 ￡ 選擇排序 選擇排序（ Selection Sort）的基本思想是：每一趟 ni+1(i = 1, 2, … , n 1) 個記錄中選取關鍵字 最小 的記錄作為有序序列中第 i個記錄 ￡ 簡單選擇排序 （ 1）算法實現(xiàn)： 一趟簡單選擇排序的操作為：通過 ni次關鍵字間的比較，從 ni+1個記錄中選出關鍵字最小的記錄，并和第 i（ 1≤i≤n）個記錄交換之。 （ 2）簡單選擇排序的改進 選擇排序的主要操作是進行 關鍵字間的比較 。因此改進簡單選擇排序應減少“比較”。 顯然，在 n個關鍵字中選出最小值，至少進行 n1次比較 . 若能利用前 n1次比較所得信息，則可減少以后各趟選擇排序中所用的比較次數(shù)。 例如，在 8個運動員中決出前 3名至多需要 11場比賽，而不是 7+6+5=18場比賽（前提：若乙勝丙，甲勝乙，則認為甲必能勝丙）。 ￡ 樹形選擇排序 首先對 n個記錄的關鍵字進行兩兩比較 如此重復，直至選 出最小關鍵字的記錄為止 。 然后在其中 個較小者之間再進行兩兩比較 樹形選擇排序 , 又稱錦標賽排序 ，是一種按照錦標賽的思想進行選擇排序的方法。 ??????2n￡ 樹形選擇排序 上述過程可用一棵有 n個葉子結點的完全二叉樹表示。 圖 (a)中的二叉樹表示從 8個關鍵字中選出最小關鍵字的過程。 (a) 選出最小關鍵字為 13 13 38 13 38 65 13 27 49 38 65 97 76 13 27 49 27 38 27 38 65 76 27 49 38 65 97 76 ∞ 27 49 輸出 13之后 (b) 選出次小關鍵字為 27 在輸出最小關鍵字之后，僅需將葉子結點中的最小關鍵字（ 13）改為“最大值”，再從下到上開始比較 38 38 38 65 76 49 38 65 97 76 49 ∞ ∞ 49 49 輸出 13， 27之后 (c) 選出居第三的關鍵字為 38 樹形選擇排序的時間復雜度：由于含有 n個葉子結點的完全二叉樹的深度為 ? ?1lo g 2 ?n則在樹形選擇排序中，除了最小關鍵字之外，每選擇一個次小關鍵 字僅需進行 次比較，因此它的時間復雜度為 O(nlog2n)。 ? ?n2log? 堆排序 ? 堆的定義： n個元素的序列 (k1,k2,……kn) ， 當且僅當滿足下列關系時，稱之為堆 或 (i=1,2,…... ?n/2?) ki?k2i ki?k2i+1 ki?k2i ki?k2i+1 例 （ 96， 83， 27， 38， 11， 9） 例 （ 13， 38， 27， 50， 76， 65， 49， 97） 96 27 9 11 38 83 13 27 38 49 65 76 50 97 可將堆序列看成完全二叉樹，則堆頂 元素（完全二叉樹的根）必為序列中 n個元素的最小值或最大值 ? 堆排序：將無序序列建成一個堆，得到關鍵字最小（或最大）的記錄；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余?n1個元素重又建成一個堆，則可得到 n個元素的次小值；重復執(zhí)行，得到一個有序序列，這個過程叫 ~ ? 堆排序需解決的兩個問題： ? 如何由一個無序序列建成一個堆？ ? 如何在輸出堆頂元素之后，調整剩余元素，使之成為一個新的堆？ ? 第二個問題解決方法 —— 篩選 ? 方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結點值與左、右子樹的根結點值進行比較，并與其中小者進行交換；重復上述操作，直至葉子結點，將得到新的堆，稱這個從堆頂至葉子的調整過程為“篩選” 例 13 27 38 49 65 76 50 97 97 27 38 49 65 76 50 13 輸出： 13 27 49 38 97 65 76 50 13 輸出： 13 97 49 38 27 65 76 50 13 輸出： 13 27 38 49 50 27 65 76 97 13 輸出： 13 27 65 49 50 27 38 76 97 13 輸出： 13 27 38 49 65 50 27 38 76 97 13 輸出： 13 27 38 76 65 50 27 38 49 97 13 輸出： 13 27 38 49 50 65 76 27 38 49 97 13 輸出： 13 27 38 49 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 97 76 27 38 49 50 13 輸出： 13 27 38 49 50 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 76 65 97 27 38 49 50 13 輸出： 13 27 38 49 50 65 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 76 97 65 76 27 38 49 50 13 輸出： 13 27 38 49 50 65 76 97 ? 算法描述 ? 第一個問題解決方法 ? 方法：從無序序列的第 ?n/2?個元素（即此無序序列對應的完全二叉樹的最后一個非終端結點）起，至第一個元素止，進行反復篩選 例 含 8個元素的無序序列（ 49， 38， 65， 97， 76， 13， 27， 50） 49 65 38 27 13 76 97 50 49 65 38 27 13 76 50 97 49 13 38 27 65 76 50 97 49 13 38 27 65 76 50 97 13 27 38 49 65 76 50 97 P281 圖 ? 算法描述 ? 算法評價 ? 時間復雜度：最壞情況下 T(n)=O(nlogn) ? 空間復雜度： S(n)=O(1) ? 歸并排序 ? 歸并 —— 將兩個或兩個以上的有序表組合成一個新的有序表，叫 ~ ? 2路歸并排序 ? 排序過程 ? 設初始序列含有 n個記錄，則可看成 n個有序的子序列，每個子序列長度為 1 ? 兩兩合并，得到 ?n/2?個長度為 2或 1的有序子序列 ? 再兩兩合并， …… 如此重復，直至得到一個長度為 n的有序序列為止 例 初始關鍵字： [49] [38] [65] [97] [76] [13] [27] 一趟歸并后： [38 49] [65 97] [13 76] [27] 二趟歸并后： [38 49 65 97] [13 27 76] 三趟歸并后： [13 27 38 49 65 76 97] ? 算法描述 ? 算法評價 ? 時間復雜度： T(n)=O(nlog2n) ? 空間復雜度： S(n)=O(n) ? 基數(shù)排序 ? 鏈式基數(shù)排序 ? 基數(shù)排序：借助“分配”和“收集”對單邏輯關鍵字進行排序的一種方法 ? 鏈式基數(shù)排序：用鏈表作存儲結構的基數(shù)排序 P284 而實現(xiàn) 基數(shù)排序不需要進行記錄關鍵字間的比較 例 初始狀態(tài)： 278 109 063 930 589 184 505 269 008 083 109 589 269 278 063 930 083 184 505 008 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 一趟分配 930 063 083 184 505 278 008 109 589 269 一趟收集： 505 008 109 930 063 269 278 083 184 589 二趟收集： 083 184 589 063 505 269 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 二趟分配 008 109 278 930 063 083 184 505 278 008 109 589 269 一趟收集： 008 063 083 109 184 269 278 505 589 930 三趟收集： 109 008 184 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 三趟分配 063 083 269 278 505 589 505 008 109 930 063 269 278 083 184 589 二趟收集： ? 算法描述 ? 算法評價 ? 時間復雜度： ? 分配： T(n)=O(n) ? 收集： T(n)=O(rd) T(n)=O(d(n+rd)) 其中： n—— 記錄數(shù) rd—— 關鍵字取值范圍 d—— 關鍵字數(shù) (分配收集的趟數(shù) ) ? 空間復雜度： S(n)=2rd個隊列指針 +n個指針域空間 ￡ 各種內部排序方法的比較討論 （ 1）算法比較 綜合比較本章內討論的各種內部排序方法，大致有如下結果： 基數(shù)排序 O(d(n+rd)) O(d(n+rd)) O(rd) 排序方法 平均時間 最壞情況 輔助存儲 簡單排序 O(n2) O(n2) O(1) 快速排序 O(nlogn) O(n2) O(nlogn) 堆排序 O(nlogn) O(nlogn) O(1) 歸并排序 O(nlogn) O(nlogn) O(n) 從上表易知，本章討論的所有排序方法中，沒有哪一種是絕對最優(yōu)的。 在實用時需根據(jù)不同情況適當選用，甚至可將多種方法結合起來使用。