[其它]ch10內(nèi)部排序-資料下載頁
2024-10-16 17:39本頁面
【正文】 序 47 ? 鏈式基數(shù)排序 ?基數(shù)排序 ：借助“分配”和“收集”對單邏輯關(guān)鍵字進行排序的一種方法 ?鏈式基數(shù)排序 ：用 鏈表 作存儲結(jié)構(gòu)的基數(shù)排序 48 ? 鏈式基數(shù)排序步驟 ① 設(shè)置 10個隊列， f[i]和 e[i]分別為第 i個隊列的頭指針和尾指針 ② 第一趟分配對最低位關(guān)鍵字（個位）進行，改變記錄的指針值，將鏈表中記錄分配至10個鏈隊列中，每個隊列記錄的關(guān)鍵字的個位相同 ③ 第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將 10個隊列鏈成一個鏈表 ④ 重復(fù)上述兩步，進行第二趟、第三趟分配和收集，分別對十位、百位進行，最后得到一個有序序列 49 例 初始狀態(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 一趟收集： 50 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 一趟收集： 51 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 二趟收集： 52 ?算法描述 ?算法評價 ? 時間復(fù)雜度 ： ?分配 ： T(n)=O(n) ?收集 ： T(n)=O(rd) T(n)=O(d(n+rd)) 其中： n—— 記錄數(shù) d—— 關(guān)鍵字數(shù) rd—— 關(guān)鍵字取值范圍 ? 空間復(fù)雜度 ： S(n)=2rd個隊列指針 53 一 .時間性能 1. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時 2. 簡單選擇排序 、 堆排序 和 歸并排序 的時間性能 不隨 記錄序列中關(guān)鍵字的分布而改變 。 直接插入排序 和 起泡排序 能達到 O(n)的時間復(fù)雜度 。 快速排序 的時間性能 蛻化為 O(n2) 各種排序方法的綜合比較 54 二、空間性能 指的是排序過程中所需的輔助空間大小 1. 所有的 簡單排序方法 (包括：直接插入、 起泡和簡單選擇 ) 和堆排序 的空間復(fù)雜度 為 O(1)； 2. 快速排序為 O(logn)， 為遞歸程序執(zhí)行過程中，棧所需的輔助空間 。 各種排序方法的綜合比較 3. 歸并排序 所需輔助空間最多，其空間復(fù)雜度為 O(n)。 4. 鏈式基數(shù)排序 需附設(shè)隊列首尾指針，則空間復(fù)雜度為 O(rd)。 55 三、排序方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對于 兩個關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。 排序之前 : { Ri(K) Rj(K) } 排序之后 : { Ri(K) Rj(K) } 各種排序方法的綜合比較 56 例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 ) 若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 則稱該排序方法是 穩(wěn)定 的 。 若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 則稱該排序方法是 不穩(wěn)定 的 。 各種排序方法的綜合比較 57 3. 對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。 4. 快速排序 、 堆排序 和 希爾排序 是不穩(wěn)定的排序方法 。 例如 : 對 { 4, 3, 4, 2 } 進行快速排序， 得到 { 2, 3, 4, 4 } 各種排序方法的綜合比較 58 四、關(guān)于“排序方法的時間復(fù)雜度的下限” 本章討論的各種排序方法，除基數(shù)排序外，其它方法都是基于“比較關(guān)鍵字”進行排序的排序方法。 可以證明， 這類排序法 可能達到的最快的時間復(fù)雜度為 O(nlogn)。 (基數(shù)排序不是基于“比較關(guān)鍵字”的排序方法，所以它不受這個限制 ) 各種排序方法的綜合比較 59 各種排序方法的綜合比較 比較次數(shù) 移動次數(shù) 附加存儲排 序 方 法最好 最差最好 最差穩(wěn)定 性最好 最差直接插入排序 n n2 0 n2 ? 1折半插入排序 n l og2n 0 n2 ? 1起泡排序n n2 0 n2 ? 1快速排序 n l og2n n2n l og2n n2 ? l og2n n2簡單選擇排序 n2 0 n ? 1錦標賽排序 n l og2n n l og2n ? n堆排序 n l og2n n l og2n ? 1歸并排序n l og2n n l og2n ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1