【正文】 k1排序后 ，便成為一個(gè)有序序列。 Data Structure Page 54 2022/2/17 ? MSD與 LSD不同特點(diǎn) ? 按 MSD排序 ，必須 將序列 逐層 分割成若干子序列 ，然后 對(duì)各子序列分別排序。 ? 按 LSD排序，不必分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序 ；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實(shí)現(xiàn)排序。 Data Structure Page 55 2022/2/17 鏈?zhǔn)交鶖?shù)排序 ?基數(shù)排序 ? 一種 借助 多關(guān)鍵字排序 的思想來實(shí)現(xiàn) 單邏輯關(guān)鍵字排序 的內(nèi)部排序算法。 ?基數(shù)排序的步驟 ? 設(shè)置 10個(gè)隊(duì)列， f[i]和 e[i]分別為 第 i個(gè)隊(duì)列的頭指針和尾指針； ? 第一趟分配對(duì)最低位關(guān)鍵字（個(gè)位）進(jìn)行 ，改變記錄的指針值，將鏈表中記錄分配至 10個(gè)鏈隊(duì)列中， 每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位相同； ? 第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，重新將 10個(gè)隊(duì)列鏈成一個(gè)鏈表； ? 重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集， 分別對(duì)十位、百位進(jìn)行， 最后得到一個(gè)有序序列。 Data Structure Page 56 2022/2/17 初始狀態(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 一趟收集： Data Structure Page 57 2022/2/17 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 一趟收集： Data Structure Page 58 2022/2/17 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 二趟收集： 穩(wěn)定的排序 方法 Data Structure Page 59 2022/2/17 ?算法評(píng)價(jià) ? 時(shí)間復(fù)雜度： ? 分配： T(n)=O(n) ? 收集： T(n)=O(rd) T(n)=O(d(n+rd)) 其中： n—— 記錄數(shù) d—— 關(guān)鍵字?jǐn)?shù) rd—— 關(guān)鍵字取值范圍 ? 空間復(fù)雜度： S(n)=2rd個(gè)隊(duì)列指針 +n個(gè)指針域空間 Data Structure Page 60 2022/2/17 各種內(nèi)部排序方法的比較討論 ?時(shí)間性能 ? 按平均的時(shí)間性能來分，有三類排序方法： ? 時(shí)間復(fù)雜度為 O (nlogn) 的方法有： 快速排序、堆排序和歸并排序，其中 快速排序目前被認(rèn)為是最快的一種排序方法 ，后兩者之比較， 在 n 值較大的情況下，歸并排序較堆排序更快 ； ? 時(shí)間復(fù)雜度為 O (n2) 的有： 插入排序、起泡排序和選擇排序，其中以 插入排序?yàn)樽畛Ｓ?，特別是對(duì)于已按關(guān)鍵字基本有序排列的記錄序列尤為如此 ，選擇排序過程中記錄移動(dòng)次數(shù)最少 ； ? 時(shí)間復(fù)雜度為 O (n) 的排序方法 基數(shù)排序。 Data Structure Page 61 2022/2/17 ? 當(dāng) 待排記錄序列按關(guān)鍵字順序有序時(shí)，插入排序和起泡排序能達(dá)到 O (n)的時(shí)間復(fù)雜度 ；而對(duì)于 快速排序而言，這是最不好的情況，此時(shí)的時(shí)間性能蛻化為 O (n2)，因此應(yīng)盡量避免。 ? 選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變 。 ? 以上 對(duì)排序的 時(shí)間復(fù)雜度的討論主要考慮 排序過程中所需進(jìn)行的關(guān)鍵字間的比較次數(shù) ， 當(dāng)待排序記錄中其它各數(shù)據(jù)項(xiàng)比關(guān)鍵字占有更大的數(shù)據(jù)量時(shí)，還應(yīng)考慮到排序過程中移動(dòng)記錄的操作時(shí)間 ，有時(shí)這種操作的時(shí)間在整個(gè)排序過程中占的比例更大，從這個(gè)觀點(diǎn)考慮，簡(jiǎn)單排序的三種排序方法中起泡排序效率最低。 Data Structure Page 62 2022/2/17 ?空間性能 指的是排序過程中 所需的輔助空間大小 。 ? 所有的簡(jiǎn)單排序方法（包括： 插入、起泡和選擇排序 ）和 堆排序 的空間復(fù)雜度均為 O (1)。 ? 快速排序 為 O (logn)，為遞歸程序執(zhí)行過程中棧所需的輔助空間。 ? 歸并排序和基數(shù)排序 所需輔助空間最多，其空間復(fù)雜度為 O (n)。 ?排序方法的穩(wěn)定性能 ? 除希爾排序、快速排序和堆排序是不穩(wěn)定的排序方法 外，本章討論的其它排序方法都是穩(wěn)定的。 ? 穩(wěn)定性 是由方法本身決定的。一般來說， 排序過程中所進(jìn)行的比較操作和交換數(shù)據(jù)僅發(fā)生在相鄰的記錄之間，沒有大步距的數(shù)據(jù)調(diào)整時(shí)，則排序方法是穩(wěn)定的。 Data Structure Page 63 2022/2/17 Data Structure Page 64 2022/2/17 本章小結(jié) 一般來說，在選擇排序方法時(shí)，可有下列幾種選擇： ? 若待排序的記錄個(gè)數(shù) n值較小（例如 n30），則可選用插入排序法，但若記錄所含數(shù)據(jù)項(xiàng)較多，所占存儲(chǔ)量大時(shí)，應(yīng)選用選擇排序法。 ? 若待排序的記錄個(gè)數(shù) n值較大時(shí)，應(yīng)選用快速排序法。但若待排序記錄關(guān)鍵字有 “ 有序 ” 傾向時(shí)，就慎用快速排序，而寧可選用堆排序或歸并排序，而后兩者的最大差別是所需輔助空間不等。 ? 快速排序和歸并排序在 n值較小時(shí)的性能不及直接插入排序，因此在實(shí)際應(yīng)用時(shí)，可將它們和插入排序 “ 混合 ” 使用。如在快速排序劃分子區(qū)間的長度小于某值時(shí)，轉(zhuǎn)而調(diào)用直接插入排序；或者對(duì)待排記錄序列先逐段進(jìn)行直接插入排序，然后再利用 “ 歸并操作 ” 進(jìn)行兩兩歸并直至整個(gè)序列有序?yàn)橹埂? Data Structure Page 65 2022/2/17 ? 基數(shù)排序的時(shí)間復(fù)雜度為 O (d n)，因此特別適合于待排記錄數(shù) n 值很大，而關(guān)鍵字 “ 位數(shù) d ”較小的情況。并且還可以調(diào)整“ 基數(shù) ” （如將基數(shù)定為 100或 1000等）以減少基數(shù)排序的趟數(shù) d的值。 ? 一般情況下，對(duì)單關(guān)鍵字進(jìn)行排序時(shí)，所用的排序方法是否穩(wěn)定無關(guān)緊要。但當(dāng)按 最次位優(yōu)先 進(jìn)行多關(guān)鍵字排序時(shí) (除第一趟外 )必須選用穩(wěn)定的排序方法。 Data Structure Page 66 2022/2/17 基礎(chǔ)知識(shí)題 ?以關(guān)鍵字序列 (503,087,512,061,908,170,897,275,653,426)為例，手工執(zhí)行以下排序算法，寫出每一趟排序結(jié)束時(shí)的關(guān)鍵碼狀態(tài)： (1) 直接插入排序； (2) 希爾排序 (增量 d[1]=5 )； (3) 快速排序； (4) 堆排序； (5) 歸并排序； (6) 基數(shù)排序。 ?若對(duì)下列關(guān)鍵字序列進(jìn)行快速排序或歸并排序 ,分別寫出三次調(diào)用過程 Partition 和過程 Merge 后的結(jié)果。 ( Tim, Kay, Eva, Roy, Dot, Jon, Kim, Ann, Tom, Jim, Guy, Amy) Data Structure Page 67 2022/2/17 ?試問在 1題所列各種排序方法中，哪些是穩(wěn)定的 ?哪些是不穩(wěn)定的 ?并為每一種不穩(wěn)定的排序方法舉出一個(gè)不穩(wěn)定的實(shí)例。 ?不難看出，對(duì)長度為 n的記錄序列進(jìn)行快速排序時(shí)，所需進(jìn)行的比較次數(shù)依賴于這 n 個(gè)元素的初始排列。 ?n=7 時(shí)在最好情況下需進(jìn)行多少次比較 ? 請(qǐng)說明理由。 ?對(duì) n=7 給出一個(gè)最好情況的初始排列實(shí)例。 Data Structure Page 68 2022/2/17 ?判別以下序列是否為堆（小頂堆或大頂堆）。如果不是，則把它調(diào)整為堆（要求記錄交換次數(shù)最少）。 ? (100, 86, 48, 73, 35, 39, 42, 57, 66, 21)。 ? (12, 70, 33, 65, 24, 56, 48, 92, 86, 33)。 ? (103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20)。 ? (05, 56, 20, 23, 40, 38, 29, 61, 35, 76, 28, 100)。