【正文】 1 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容 2 概述 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 第 10章 內(nèi)部排序 3 概述 1. 什么是排序？ 將一組雜亂無(wú)章的 數(shù)據(jù) 按一定的 規(guī)律 順次排列起來(lái)。 2. 排序的目的是什么？ 存放在數(shù)據(jù)表中 按關(guān)鍵字排序 ？ ? 時(shí)間效率 —排序速度 (即排序所花費(fèi)的全部比較次數(shù) ) ? 空間效率 —占內(nèi)存輔助空間的大小 ? 穩(wěn)定性 —若兩個(gè)記錄 A和 B的關(guān)鍵字值相等 ， 但排序后A、 B的先后次序保持不變 ， 則稱這種排序算法是穩(wěn)定的 。 ——便于查找！ 4 4. 什么叫內(nèi)部排序？什么叫外部排序？ ——若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序； ——若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。 注： 外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來(lái)排序，中間結(jié)果還要及時(shí)放入外存，顯然外部排序要復(fù)雜得多。 ？ ① 順序 排序 ——排序時(shí)直接移動(dòng)記錄； ② 鏈表 排序 ——排序時(shí)只移動(dòng)指針； ③ 地址 排序 ——排序時(shí)先移動(dòng)地址，最后再移動(dòng)記錄。 注： 地址排序 中可以增設(shè)一維數(shù)組來(lái)專門存放記錄的地址。 5 注： 大多數(shù)排序算法都是針對(duì)順序表結(jié)構(gòu)的 (便于直接移動(dòng)元素 ) 6. 順序存儲(chǔ)（順序表）的抽象數(shù)據(jù)類型如何表示？ Typedef struct { //定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu) KeyType key 。 //關(guān)鍵字 InfoType otherinfo。 //其它數(shù)據(jù)項(xiàng) }RecordType 。 define MAXSIZE 20 //設(shè)記錄不超過(guò) 20個(gè) typedef int KeyType 。 //設(shè)關(guān)鍵字為整型量（ int型） Typedef struct { //定義順序表的結(jié)構(gòu) RecordType r [ MAXSIZE +1 ]。 //存儲(chǔ)順序表的向量， r[0]一般作哨兵或緩沖區(qū) int length 。 //順序表的長(zhǎng)度 }SqList 。 6 7. 內(nèi)部排序的算法有哪些？ ——按排序的規(guī)則不同，可分為 5類： ? 插入排序 ? 交換排序（重點(diǎn)是快速排序） ? 選擇排序 ? 歸并排序 ? 基數(shù)排序 d＝關(guān)鍵字的位數(shù) (長(zhǎng)度 ) ——按排序算法的時(shí)間復(fù)雜度不同，可分為 3類： ?簡(jiǎn)單的排序算法：時(shí)間效率低， O(n2) ?先進(jìn)的排序算法 : 時(shí)間效率高， O( nlog2n ) ?基數(shù)排序算算法：時(shí)間效率高， O( d n) 7 插入排序 插入排序的基本思想是： 每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵字大小，插入到前面 已經(jīng)排好序的一組對(duì)象 的 適當(dāng)位置 上，直到對(duì)象全部插入為止。 插入排序的基本操作： 將記錄 R[i]插入到有序子序列 R[1..i1]中，使記錄的有序序列從 R[1..i1]變?yōu)?R[1..i]。 顯然，完成這個(gè)“插入”需分三步進(jìn)行： 1．查找 R[i]的插入位置 j+1； 2．將 R[j+1..i1]中的記錄后移一個(gè)位置； 3．將 R[i]復(fù)制到 R[j+1]的位置上。 8 插入排序 插入排序有多種具體實(shí)現(xiàn)算法： 1) 直接插入排序 2) 折半插入排序 3) 表插入排序 4) 希爾排序 簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。 9 1) 直接插入排序 新元素插入到哪里？ 例 1： 關(guān)鍵字序列 T=(13， 6， 3， 31， 9， 27， 5， 11)，請(qǐng)寫出直接插入排序的中間過(guò)程序列。 【 13】 , 6, 3, 31, 9, 27, 5, 11 【 6, 13】 , 3, 31, 9, 27, 5, 11 【 3, 6, 13】 , 31, 9, 27, 5, 11 【 3, 6, 13， 31】 , 9, 27, 5, 11 【 3, 6, 9, 13， 31】 , 27, 5, 11 【 3, 6, 9, 13， 27, 31】 , 5, 11 【 3, 5, 6, 9, 13， 27, 31】 , 11 【 3, 5, 6, 9, 11， 13， 27, 31】 在已形成的 有序表中 線性查找 ，并在適當(dāng)位置插入，把原來(lái)位置上的元素向后 順移 。 最簡(jiǎn)單的排序法！ 10 例 2： 關(guān)鍵字序列 T= （ 21， 25， 49， 25*， 16， 08）， 請(qǐng)寫出直接插入排序的具體實(shí)現(xiàn)過(guò)程。 *表示后一個(gè) 25 i=1 21 25 49 25* 16 08 0 1 2 3 4 5 6 暫 存 i=2 i=3 i=5 i=4 i=6 25 49 25* 49 16 25* 08 49 解： 假設(shè)該序列已存入一維數(shù)組 V[7]中，將 V[0]作為緩沖或暫存單元（ Temp）。則程序執(zhí)行過(guò)程為： 21 25 49 初態(tài)： 16 25* 25 211608 完成 ! 時(shí)間效率： O(n2)——因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（ 0＋ 1＋ … ＋ n1)→O(n 2)。其他情況下還要加上移動(dòng)元素的次數(shù)。 空間效率： O（ 1） ——因?yàn)閮H占用 1個(gè)緩沖單元 算法的穩(wěn)定性： 穩(wěn)定 ——因?yàn)?25*排序后仍然在 25的后面。 11 直接插入排序算法的三個(gè)要點(diǎn)： 1．從 R[i1]起向前順序查找，監(jiān)視哨設(shè)置在 R[0] R[0] = R[i]。 // 設(shè)置“哨兵” for (j=i1。 R[0].keyR[j].key。 j) 。 // 從后往前找 return j+1。 // 返回 R[i]的插入位置為 j+1 2．對(duì)于在查找過(guò)程中找到的關(guān)鍵字不小于 R[i].key的記錄，在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)； for (j=i1。 R[0].keyR[j].key。 j) R[j+1] = R[j] 3． i = 2， 3， …, n, 實(shí)現(xiàn)整個(gè)序列的排序。 12 直接插入排序算法描述如下 : void InserSort ( SqList amp。L) { // 對(duì)順序表 L作直接插入排序。 for ( i=2。 i=。 ++i ) if (LT([i].key ,[i1].key)) { [0] = [i]。 // 復(fù)制為監(jiān)視哨 for ( j=i1。 LT([i].key ,[i1].key) 。 j ) [j+1] = [j]。 // 記錄后移 [j+1] = [0]。 // 插入到正確位置 } } // InsertSort 13 ? 若設(shè)待排序的對(duì)象個(gè)數(shù)為 n，則算法需要進(jìn)行n1次插入。 ? 最好情況下，排序前對(duì)象已經(jīng)按關(guān)鍵字大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械?最后一個(gè)對(duì)象 的關(guān)鍵字比較 1 次。因此，總的關(guān)鍵字比較次數(shù)為 n1。 直接插入排序的算法分析 14 ? 最壞情況下，第 i趟插入時(shí)，第 i個(gè)對(duì)象必須與前面 i1個(gè)對(duì)象都做關(guān)鍵字比較，并且每做 1 次比較就要做 1 次數(shù)據(jù)移動(dòng)。則總的關(guān)鍵字比較次數(shù) KCN和對(duì)象移動(dòng)次數(shù) RMN分別為 15 ?若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為 n2/4。因此，直接插入排序的時(shí)間復(fù)雜度為 o(n2)。 ?直接插入排序是一種穩(wěn)定的排序方法。 16 2） 折半插入排序 優(yōu)點(diǎn)： 比較的次數(shù)大大減少 ， 全部元素比較次數(shù)僅為O(nlog2n)。 時(shí)間效率： 雖然比較次數(shù)大大減少 ， 可惜移動(dòng)次數(shù)并未減少 ， 所以排序效率仍為 O(n2) 。 空間效率： O（ 1） 穩(wěn)定性： 穩(wěn)定 當(dāng)待排序記錄的數(shù)量 n很小時(shí)，直接插入排序是一種簡(jiǎn)便的方法；但當(dāng)記錄數(shù)量 n很大時(shí)，則不宜采用直接插入排序。 由于插入排序的基本操作是在有序表 R[1..i1]中進(jìn)行查找和插入的；則可以利用折半查找實(shí)現(xiàn)“在 R[1..i1]中查找 R[i]的插入位置”， 并在適當(dāng)位置插入，把原來(lái)位置上的元素向后 順移 。 如此實(shí)現(xiàn)的插入排序?yàn)?折半插入排序 。 17 折半插入排序算法描述如下 : void BInserSort ( SqList amp。L) { // 對(duì)順序表 L作折半插入排序。 for ( i=2。 i=。 ++i ) { [0] = [i]。 while(low=high) { m=(low+high)/2。 if (LT([0].key ,[m].key)) high=m1。 else low=m+1。 } //while for ( j=i1。 j=high+1。 j ) [j+1] = [j]。 // 記錄后移 [j+1] = [0]。 // 插入 }//for } // BInsertSort 18 討論： 若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？ 答： 直接插入不僅可行，而且還無(wú)需移動(dòng)元素，時(shí)間效率更高！ 折半插入排序的改進(jìn) ——2路插入排序見(jiàn)教材 P267。 但鏈表無(wú)法 “ 折半 ” ！ 19 折半插入排序的算法分析 ? 折半查找比順序查找快，所以折半插入排序就平均性能來(lái)說(shuō)比直接插入排序要快。 ? 在插入第 i 個(gè)對(duì)象時(shí)，需要經(jīng)過(guò) ?log2i? +1 次關(guān)鍵字比較，才能確定它應(yīng)插入的位置。因此，將 n 個(gè)對(duì)象用折半插入排序所進(jìn)行的關(guān)鍵字比較次數(shù)為： n*log2n ? 折半插入排序是一個(gè)穩(wěn)定的排序方法。 20 3） 表插入排序 基本思想 ：在順序存儲(chǔ)結(jié)構(gòu)中，給每個(gè)記錄增開(kāi)一個(gè)指針?lè)至?，在排序過(guò)程中將指針內(nèi)容逐個(gè)修改為已經(jīng)整理（排序）過(guò)的后繼記錄地址。 優(yōu)點(diǎn)： 在排序過(guò)程中不移動(dòng)元素，只修改指針。 回憶： ② 鏈表排序 ——排序時(shí)只移動(dòng)指針； ③ 地址排序 ——排序時(shí)先移動(dòng)地址，最后再移動(dòng)記錄。 此方法具有鏈表排序和地址排序的特點(diǎn)。 21 1 例： 關(guān)鍵字序列 T=(21， 25， 49， 25*， 16， 08)， 請(qǐng)寫出表插入排序的具體實(shí)現(xiàn)過(guò)程。 解： 假設(shè)該序列（結(jié)構(gòu)類型 )已存入有序鏈表 SL[7]中，將 SL[0]作為表頭結(jié)點(diǎn)。則 算法執(zhí)行過(guò)程 為： i 關(guān)鍵字 SL[i].key 指針 SL[i].next 0 MaxInt 1 21 2 25 3 49 4 25* 5 16 6 08 指向第 1個(gè)元素 指向頭結(jié)點(diǎn) 初態(tài) i=1 i=2 i=3 i=4 i=5 i=6 0 3 45 65 0 3 1 0 2 *表示后一個(gè) 25 靜態(tài)鏈表 22 表插入排序算法分析： ① 無(wú)需移動(dòng)記錄，只需修改 2n次指針值。但由于比較次數(shù)沒(méi)有減少，故 時(shí)間效率仍為 O(n2) 。 ②