【導(dǎo)讀】排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，整為“有序”的記錄序列。假設(shè)含n個(gè)記錄的序列為{R1,R2,…其相應(yīng)的關(guān)鍵字序列為{K1,K2,…的操作稱作排序。反之，若參加排序的記錄數(shù)量很大，完成，則稱此類排序問(wèn)題為外部排序。3．將R[i]插入(復(fù)制)到R[j+1]的位置上。從R[i-1]起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在R[0]；同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；//對(duì)順序表L作直接插入排序。在[1..i-1]中折半查找插入位置；

　　

【正文】 ,Kid1) (Kj0, Kj1, … ,Kjd1) 實(shí)現(xiàn)多關(guān)鍵字排序 通常有兩種作法 : 最低位優(yōu)先 LSD法 最高位優(yōu)先 MSD法 先對(duì) K0進(jìn)行排序 ，并按 K0 的不同值將記錄序列 分成若干子序列 之后， 分別對(duì) K1 進(jìn)行排序 ， ...… ， 依次類推， 直至最后對(duì)最次位關(guān)鍵字排序完成為止 。 先對(duì) Kd1 進(jìn)行排序 ， 然后對(duì) Kd2 進(jìn)行排序，依次類推， 直至對(duì)最主位關(guān)鍵字 K0 排序完成為止 。 排序過(guò)程中不需要根據(jù) “ 前一個(gè) ” 關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個(gè) (“前一個(gè) ” 關(guān)鍵字不同的 )子序列。 例如 :學(xué)生記錄含三個(gè)關(guān)鍵字 : 系別 、 班號(hào) 和 班內(nèi)的序列號(hào) ，其中以系別為最主位關(guān)鍵字。 無(wú)序序列 對(duì) K2排序 對(duì) K1排序 對(duì) 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的排序過(guò)程如下 : 二、鏈?zhǔn)交鶖?shù)排序 假如多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的取值范圍相同，則按 LSD法進(jìn)行排序時(shí)，可以采用 “分配 收集 ” 的方法，其好處是不需要進(jìn)行關(guān)鍵字間的比較。 對(duì)于數(shù)字型或字符型的 單關(guān)鍵字 ，可以 看成 是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的 多關(guān)鍵字 ，此時(shí)可以 采用 這種 “分配 收集”的辦法 進(jìn)行排序 ， 稱作基數(shù)排序法 。 例如： 對(duì)下列這組關(guān)鍵字 {209, 386, 768, 185, 247, 606, 230, 834, 539 } 首先按其 “個(gè)位數(shù)” 取值分別為 0, 1, …, 9 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)? 它們 “收集” 在一起； 然后按其 “十位數(shù)” 取值分別為 0, 1, …, 9 “分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈? “ 收集 ” 在一起； 最后按其 “ 百位數(shù) ” 重復(fù)一遍上述操作。 在計(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è)鏈表 。 ４． 對(duì)每個(gè)關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。 例如： p→ 368→ 367→ 167→ 239→ 237→ 138→ 230→ 139 進(jìn)行第一次分配 進(jìn)行第一次收集 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← 進(jìn)行第二次分配 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 進(jìn)行第二次收集 進(jìn)行第三次收集之后便得到記錄的有序序列 f[1] r[1] p→230→237→138→239→139→367→167→368 進(jìn)行第三次分配 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 提醒注意： １． “ 分配 ” 和 “ 收集 ” 的實(shí)際操作僅為修改鏈表中的指針和設(shè)置隊(duì)列的頭、尾指針； ２．為查找使用，該鏈表尚需應(yīng)用算法 Arrange 將它調(diào)整為有序表。 基數(shù)排序的時(shí)間復(fù)雜度為 O(d(n+rd)) 其中：分配為 O(n) 收集為 O(rd)(rd為“基” ) d為“分配 收集”的趟數(shù) 各種排序方法的綜合比較 一、時(shí)間性能 1. 平均的時(shí)間性能 基數(shù)排序 時(shí)間復(fù)雜度為 O(nlogn)： 快速排序、堆排序和歸并排序 時(shí)間復(fù)雜度為 O(n2)： 直接插入排序、起泡排序和 簡(jiǎn)單選擇排序 時(shí)間復(fù)雜度為 O(n): 2. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí) 3. 簡(jiǎn)單選擇排序、堆排序和歸并排序 的時(shí)間性能 不隨 記錄序列中關(guān)鍵字的分布而改變 。 直接插入排序 和 起泡排序 能達(dá)到 O(n)的時(shí)間復(fù)雜度， 快速排序 的時(shí)間性能 蛻化為 O(n2) 。 二、空間性能 指的是排序過(guò)程中所需的輔助空間大小 1. 所有的 簡(jiǎn)單排序方法 (包括：直接插入、起泡和簡(jiǎn)單選擇 ) 和 堆排序 的空間復(fù)雜度為 O(1)； 2. 快速排序?yàn)?O(logn)， 為遞歸程序執(zhí)行過(guò)程中，棧所需的輔助空間； 3. 歸并排序 所需輔助空間最多，其空間復(fù)雜度為 O(n)。 4. 鏈?zhǔn)交鶖?shù)排序 需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為 O(rd)。 三、排序方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對(duì)于 兩個(gè)關(guān)鍵字相等的記錄，它們?cè)谛蛄兄械南鄬?duì)位置，在排序之前和經(jīng)過(guò)排序之后，沒(méi)有改變。 2. 當(dāng) 對(duì)多關(guān)鍵字的記錄序列進(jìn)行 LSD方法排序時(shí)，必須采用穩(wěn)定的排序方法 。 排序之前 : { Ri(K) Rj(K) } 排序之后 : { Ri(K) Rj(K) } 例如： 排序前 ( 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)定 的。 3. 對(duì)于不穩(wěn)定的排序方法，只要能舉出一個(gè)實(shí)例說(shuō)明即可。 4. 快速排序、堆排序和希爾排序是不穩(wěn)定的排序方法 。 例如 : 對(duì) { 4, 3, 4, 2 } 進(jìn)行快速排序， 得到 { 2, 3, 4, 4 } 四、關(guān)于“排序方法的時(shí)間復(fù)雜度的下限” 本章討論的各種排序方法，除基數(shù)排序外，其它方法都是 基于“比較關(guān)鍵字”進(jìn)行排序的排序方法。 可以證明， 這類排序法 可能達(dá)到的最快的時(shí)間復(fù)雜度為 O(nlogn)。 (基數(shù)排序不是基于“比較關(guān)鍵字”的排序方法，所以它不受這個(gè)限制。 ) 例如 :對(duì)三個(gè)關(guān)鍵字進(jìn)行排序的判定樹(shù) 如下： K1K3 K1K2 K1K3 K2K3 K2 K3 K2K1K3 K1K2K3 K3K2K1 K2K3K1 K3K1K2 K1K3K2 １．樹(shù)上的 每一次“比較”都是必要的 。 ２． 樹(shù)上的 葉子結(jié)點(diǎn)包含所有可能情況 。 T F F F F F T T T T 一般情況下，對(duì) n個(gè)關(guān)鍵字進(jìn)行排序，可能得到的結(jié)果有 n! 種，由于含 n! 個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)的深度不小于 ?log2(n!)? +1, 則對(duì) n 個(gè)關(guān)鍵字進(jìn)行排序的比較次數(shù)至少是 ?log2(n!)? ? nlog2n (斯蒂林近似公式 )。 所以， 基于“比較關(guān)鍵字”進(jìn)行排序的 排序方法，可能達(dá)到的最快的時(shí)間復(fù)雜度為 O(nlogn)。 1. 了解排序的 定義 和各種排序方法的特點(diǎn)。熟悉各種 方法的排序過(guò)程及其依據(jù)的原則 ?；?“ 關(guān)鍵字間的比較 ” 進(jìn)行排序的方法可以按排序過(guò)程所依據(jù)的不同原則分為 插入排序 、 交換排序 、 選擇排序 、 歸并排序 和計(jì)數(shù)排序等五類。 2. 掌握各種排序方法的 時(shí)間復(fù)雜度的分析方法。能從 “ 關(guān)鍵字間的比較次數(shù) ” 分析排序算法的 平均 情況和 最壞 情況的時(shí)間性能。 按平均時(shí)間復(fù)雜度劃分，內(nèi)部排序可分為三類： O(n2)的簡(jiǎn)單排序方法，O(nlogn)的高效排序方法 和 O(dn)的基數(shù)排序方法。 3． 理解排序方法 “ 穩(wěn)定 ” 或 “ 不穩(wěn)定 ”的含義，弄清楚在 什么情況下 要求應(yīng)用的排序方法必須是穩(wěn)定的。 4. 了解外部排序的基本過(guò)程及其時(shí)間分析 。