【導讀】排序方法有不同的分類方法，基于“關。壞情況的時間性能。按平均時間復雜度劃分，內(nèi)部。的高效排序方法和O的基數(shù)排序方法。理解排序方法"穩(wěn)定"或"不穩(wěn)定"的含義，學習中應注意掌握各種排序方法實現(xiàn)。教科書上可以有不同書寫形式描述的算法。排序是計算機內(nèi)經(jīng)常進行的一種操作，整為“有序”的記錄序列。假設含n個記錄的序列為{R1,R2,…其相應的關鍵字序列為{K1,K2,…反之，若參加排序的記錄數(shù)量很大，成，則稱此類排序問題為外部排序。3．將R[i]插入(復制)到R[j+1]的位置上。監(jiān)視哨設置在R[0]；{在R[1..i-1]中查找R[i]的插入位置;//對順序表L作直接插入排序。

　　

【正文】 對 K2排序 對 K1排序 對 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的排序過程如下 : 第十章 內(nèi)部排序 基數(shù) 排序 二、鏈式基數(shù)排序 假如多關鍵字的記錄序列中，每個關鍵字的取值范圍相同，則按 LSD法進行排序時，可以采用 “分配 收集 ” 的方法，其好處是不需要進行關鍵字間的比較。 對于數(shù)字型或字符型的 單關鍵字 ，可以 看成 是由多個數(shù)位或多個字符構成的 多關鍵字 ，此時可以 采用 這種 “分配 收集”的辦法 進行排序 ， 稱作基數(shù)排序法 。 第十章 內(nèi)部排序 基數(shù) 排序 例如：對下列這組關鍵字 {209, 386, 768, 185, 247, 606, 230, 834, 539 } 首先按其 “個位數(shù)” 取值分別為 0, 1, …, 9 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)? 它們 “收集” 在一起 。 然后按其 “十位數(shù)” 取值分別為 0, 1, …, 9 “分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈? “ 收集 ” 在一起； 最后按其 “ 百位數(shù) ” 重復一遍上述操作。 第十章 內(nèi)部排序 基數(shù) 排序 在計算機上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應采用鏈表作存儲結構， 即鏈式基數(shù)排序，具體作法為： １． 待排序記錄以指針相鏈，構成一個鏈表； ２ ． “ 分配 ” 時，按當前 “ 關鍵字位 ” 所取值，將記錄分配到不同的 “ 鏈隊列 ” 中，每個隊列中記錄的 “ 關鍵字位 ” 相同； ３ ． “ 收集 ” 時，按當前關鍵字位取值從小到大 將各隊列首尾相鏈成一個鏈表 。 ４． 對每個關鍵字位均重復 2) 和 3) 兩步。 第十章 內(nèi)部排序 基數(shù) 排序 例如： p→ 369→ 367→ 167→ 239→ 237→ 138→ 230→ 139 進行第一次分配 進行第一次收集 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← 第十章 內(nèi)部排序 基數(shù) 排序 進行第二次分配 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 進行第二次收集 第十章 內(nèi)部排序 基數(shù) 排序 進行第三次收集之后便得到記錄的有序序列 f[1] r[1] p→230→237→138→239→139→367→167→368 進行第三次分配 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 第十章 內(nèi)部排序 基數(shù) 排序 提醒注意： １． “ 分配 ” 和 “ 收集 ” 的實際操作僅為修改鏈表中的指針和設置隊列的頭、尾指針； ２．為查找使用，該鏈表尚需應用算法 Arrange() 將它調(diào)整為有序表。 第十章 內(nèi)部排序 基數(shù) 排序 算法： 基數(shù)排序的時間復雜度為 O(d(n+rd)) 其中，分配為 O(n)。 收集為 O(rd)(rd為“基” ), d為“分配 收集”的趟數(shù)。 目錄 第十章 內(nèi)部排序 各種方法比較 一、時間性能 1. 平均的時間性能 基數(shù)排序 時間復雜度為 O(nlogn)： 快速排序、堆排序和歸并排序 時間復雜度為 O(n2)： 直接插入排序、起泡排序和 簡單選擇排序 時間復雜度為 O(n): 第十章 內(nèi)部排序 2. 當待排記錄序列按關鍵字順序有序時 3. 簡單選擇排序、堆排序和歸并排序 的時間性能 不隨 記錄序列中關鍵字的分布而改變 。 直接插入排序 和 起泡排序 能達到 O(n)的時間復雜度 。 快速排序 的時間性能 蛻化為 O(n2) 各種方法比較 第十章 內(nèi)部排序 二、空間性能 指的是排序過程中所需的輔助空間大小 1. 所有的 簡單排序方法 (包括：直接插入、 起泡和簡單選擇 ) 和 堆排序 的空間復雜度為 O(1)； 2. 快速排序為 O(logn)， 為遞歸程序執(zhí)行過程中，棧所需的輔助空間 。 各種方法比較 第十章 內(nèi)部排序 3. 歸并排序 所需輔助空間最多，其空間復雜度為 O(n)。 4. 鏈式基數(shù)排序需附設隊列首尾指針，則空間復雜度為 O(rd)。 各種方法比較 第十章 內(nèi)部排序 各種方法比較 三、排序方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對于 兩個關鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。 2. 當對多關鍵字的記錄序列進行 LSD方法排序時， 必須采用穩(wěn)定 的排序方法。 排序之前 : { Ri(K) Rj(K) } 排序之后 : { Ri(K) Rj(K) } 第十章 內(nèi)部排序 各種方法比較 例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 ) 若排序后得到結果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 則稱該排序方法是 穩(wěn)定 的 。 若排序后得到結果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 則稱該排序方法是 不穩(wěn)定 的 。 第十章 內(nèi)部排序 各種方法比較 2. 對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。 3. 快速排序、堆排序和希爾排序是不穩(wěn)定的排序方法 。 例如 : 對 { 4, 3, 4, 2 } 進行快速排序， 得到 { 2, 3, 4, 4 } 第十章 內(nèi)部排序 各種方法比較 四、關于“排序方法的時間復雜度的下限” 本章討論的各種排序方法，除基數(shù)排序外，其它方法都是 基于“比較關鍵字”進行排序的排序方法。 可以證明， 這類排序法 可能達到的最快的時間復雜度為 O(nlogn)。 (基數(shù)排序不是基于“比較關鍵字”的排序方法，所以它不受這個限制 ) 第十章 內(nèi)部排序 各種方法比較 目錄 排序方法 平均時間 最壞情況 輔助存儲 穩(wě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)部排序 本章小結 1. 了解 排序的定義和各種排序方法的特點。 熟悉 各種方法的排序過程及其依據(jù)的原則?；?“ 關鍵字間的比較 ” 進行排序的方法可以按排序過程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序等五類。 第十章 內(nèi)部排序 本章小結 2. 掌握各種排序方法的 時間復雜度 。能從 “ 關鍵字間的比較次數(shù) ” 分析排序算法的 平均 情況和 最壞 情況的時間性能。 按平均時間復雜度劃分，內(nèi)部排序可分為三類： O(n2)的簡單排序方法，O(nlogn)的高效排序方法 和 O(dn)的基數(shù)排序方法。 第十章 內(nèi)部排序 本章小結 3． 理解排序方法 “ 穩(wěn)定 ” 或 “ 不穩(wěn)定 ”的含義，弄清楚在 什么情況下 要求應用的排序方法必須是穩(wěn)定的。