【正文】 7 4 ∧ 8 8 ∧ 4 6 ∧ 6 0 ∧ 3 1 ∧ 4 3 ∧ 2 9 1 6 ∧ 7 7 9 0 ∧ 下標 哈希表 本章小結(jié) 本章基本學習要點如下： (1) 理解查找的基本概念 ,包括靜態(tài)查找表和動態(tài)查找表 、 內(nèi)查找和外查找之間的差異 。 (2) 重點掌握線性表上各種查找算法 ,包括順序查找 、 二分查找和分塊查找的基本思路 、 算法實現(xiàn)和查找效率等 。 (3) 掌握各種樹表的查找算法 ,包括二叉排序樹 、 AVL樹和 B樹的基本思路 、 算法實現(xiàn)和查找效率等 。 (4) 掌握哈希表查找技術(shù)以及哈希表與其他表的本質(zhì)區(qū)別 。 (5) 靈活運用各種查找算法解決一些綜合應用問題 。 練習 教材中 p265習題 3和 5。 上機實習題 教材中 p166題 3和 5。 第 11章 內(nèi) 排 序 基數(shù)排序 本章小結(jié) 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 各種內(nèi)排序方法的比較和選擇 排序的基本概念 所謂 排序 ,就是要整理表中的記錄 ,使之按關(guān)鍵字遞增 (或遞減 )有序排列。其確切定義如下： 輸入： n個記錄 ,R0,R1,… ,Rn1,其相應的關(guān)鍵字分別為k0,k1,… ,kn1。 輸出： Ri0,Ri1,… ,Rin1, 使得 ki0≤ki1≤… ≤kin1 ( 或ki0≥ki1≥… ≥kin1)。 當待排序記錄的關(guān)鍵字均不相同時 ,排序的結(jié)果是惟一的 ,否則排序的結(jié)果不一定惟一。如果待排序的表中 ,存在有多個關(guān)鍵字相同的記錄 ,經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變 ,則稱這種排序方法是 穩(wěn)定的 ；反之 ,若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化 ,則稱這種排序方法是 不穩(wěn)定的 。 在排序過程中 ,若整個表都是放在內(nèi)存中處理 ,排序時不涉及數(shù)據(jù)的內(nèi)、外存交換 ,則稱之為 內(nèi)排序 ；反之 ,若排序過程中要進行數(shù)據(jù)的內(nèi)、外存交換 ,則稱之為 外排序 。 內(nèi)排序的方法 內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。 經(jīng)過一趟排序 有序序列區(qū) 無 序 序 列 區(qū) 有序序列區(qū) 無 序 序 列 區(qū) 待排序的順序表類型的類型定義如下： typedef int KeyType。 /*定義關(guān)鍵字類型 */ typedef struct /*記錄類型 */ { KeyType key。 /*關(guān)鍵字項 */ InfoType data。 /*其他數(shù)據(jù)項 ,類型為 InfoType*/ } RecType。 /*排序的記錄類型定義 */ 插入排序 插入排序的基本思想是：每次將一個待排序的記錄 ,按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子表中的適當位置 ,直到全部記錄插入完成為止 。 兩種插入排序方法： (1)直接插入排序 (2)希爾排序 。 直接插入排序 假設待排序的記錄存放在數(shù)組 R[0..n1]中 ,排序過程的某一中間時刻 ,R被劃分成兩個子區(qū)間 R[0..i1]和R[i..n1],其中：前一個子區(qū)間是已排好序的有序區(qū) ,后一個子區(qū)間則是當前未排序的部分 ,不妨稱其為無序區(qū) 。 直接插入排序的基本操作是將當前無序區(qū)的第 1個記錄 R[i]插入到有序區(qū) R[0..i1]中適當?shù)奈恢蒙?,使R[0..i]變?yōu)樾碌挠行騾^(qū) 。 這種方法通常稱為增量法 ,因為它每次使有序區(qū)增加 1個記錄 。 R[0] j R[i] j=i1 插入位置 在有序區(qū)中插入 R[i]的過程 void InsertSort(RecType R[],int n) /*對 R[0..n1]按遞增有序進行直接插入排序 */ { int i,j。 RecType temp。 for (i=1。in。i++) { temp=R[i]。 j=i1。 /*從右向左在有序區(qū) R[0..i1]找 R[i]的插入位置 */ while (j=0 amp。amp。 R[j].key) { R[j+1]=R[j]。 /*將關(guān)鍵字大于 R[i].key的記錄后移 */ j。 } R[j+1]=temp。 /*在 j+1處插入 R[i]*/ } } 例 設待排序的表有 10個記錄 ,其關(guān)鍵字分別為{9,8,7,6,5,4,3,2,1,0}。說明采用直接插入排序方法進行排序的過程。 初始關(guān)鍵字 9 8 7 6 5 4 3 2 1 0 i= 1 [ 8 9] 7 6 5 4 3 2 1 0 i= 2 [ 7 8 9] 6 5 4 3 2 1 0 i= 3 [ 6 7 8 9] 5 4 3 2 1 0 i= 4 [ 5 6 7 8 9] 4 3 2 1 0 i= 5 [ 4 5 6 7 8 9] 3 2 1 0 i= 6 [ 3 4 5 6 7 8 9] 2 1 0 i= 7 [ 2 3 4 5 6 7 8 9] 1 0 i= 8 [ 1 2 3 4 5 6 7 8 9] 0 i= 9 [ 0 1 2 3 4 5 6 7 8 9] 對于直接插入排序： 最好的情況（關(guān)鍵字在記錄序列中順序有序） ： “比較”的次數(shù)： 最壞的情況（關(guān)鍵字在記錄序列中逆序有序）： “比較”的次數(shù)： 1111?????nni0 “移動”的次數(shù)： “移動”的次數(shù)： 221111)n)(n()i(ni???????221111)n)(n()i(ni??????? 希爾排序 希爾排序也是一種插入排序方法 ,實際上是一種分組插入方法 。 其基本思想是：先取定一個小于 n的整數(shù) d1作為第一個增量 ,把表的全部記錄分成 d1個組 ,所有距離為 d1的倍數(shù)的記錄放在同一個組中 ,在各組內(nèi)進行直接插入排序；然后 ,取第二個增量 d2(＜ d1),重復上述的分組和排序 ,直至所取的增量 dt=1(dtdt1… d2d1),即所有記錄放在同一組中進行直接插入排序為止 。 將記錄序列分成若干子序列，分別對每個子序列進行插入排序。 其中， d 稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為 1。 例如：將 n 個記錄分成 d 個子序列： { R[0]， R[d]， R[2d]， … ， R[kd] } { R[1]， R[1+d]， R[1+2d]， … ， R[1+kd] } … { R[d1]， R[2d1]， R[3d1]， … ， R[(k+1)d1] } 例如： 16 25 12 30 47 11 23 36 9 18 31 第一趟希爾排序，設增量 d =5 11 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序，設增量 d = 3 9 18 12 11 23 16 25 31 30 47 36 第三趟希爾排序，設增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 void ShellSort(RecType R[],int n) /*希爾排序算法 */ { int i,j,d。RecType temp。 d=n/2。 /*d取初值 n/2*/ while (d0) { for (i=d。in。i++) /*將 R[d..n1]分別插入各組當前有序區(qū) */ { j=id。 while (j=0 amp。amp。 R[j].keyR[j+d].key) { temp=R[j]。 /*R[j]與 R[j+d]交換 */ R[j]=R[j+d]。R[j+d]=temp。 j=jd。 } } d=d/2。 /*遞減增量 d*/ } } 例 設待排序的表有 10個記錄 ,其關(guān)鍵字分別為{9,8,7,6,5,4,3,2,1,0}。 說明采用希爾排序方法進行排序的過程 。 9 8 7 6 5 4 3 2 1 0 初始狀態(tài) ( 連線部分為下一趟作準備 ) 4 3 2 1 0 9 8 7 6 5 d =5 (d =5 執(zhí)行結(jié)果 ) 0 1 2 3 4 5 6 7 8 9 d =2 (d =2 執(zhí)行結(jié)果 ) 0 1 2 3 4 5 6 7 8 9 d =1 (d =1 執(zhí)行結(jié)果 ) 交換排序 交換排序的基本思想：兩兩比較待排序記錄的關(guān)鍵字 ,發(fā)現(xiàn)兩個記錄的次序相反時即進行交換 ,直到?jīng)]有反序的記錄為止 。 兩種交換排序 : (1)冒泡排序 (2)快速排序 冒泡排序 冒泡排序的基本思想是： 通過無序區(qū)中相鄰記錄關(guān)鍵字間的比較和位置的交換 ,使關(guān)鍵字最小的記錄如氣泡一般逐漸往上 “ 漂浮 ” 直至 “ 水面 ” 。 整個算法是從最下面的記錄開始 ,對每兩個相鄰的關(guān)鍵字進行比較 ,且使關(guān)鍵字較小的記錄換至關(guān)鍵字較大的記錄之上 ,使得經(jīng)過一趟冒泡排序后 ,關(guān)鍵字最小的記錄到達最上端 ,接著 ,再在剩下的記錄中找關(guān)鍵字次小的記錄 ,并把它換在第二個位置上 。 依次類推 ,一直到所有記錄都有序為止 。 假設在排序過程中，記錄序列 R[0..n1]的狀態(tài)為： 第 i 趟起泡排序 無序序列 R[0..ni+1] 有序序列 R[ni+2..n1] ni+1 無序序列 R[0..ni] 有序序列 R[ni+1..n1] 比較相鄰記錄，將關(guān)鍵字最大的記錄 交換到 ni+1 的位置上 void BubbleSort(RecType R[],int n) { int i,j。 RecType temp。 for (i=0。in1。i++) { for (j=n1。ji。j) /*比較找本趟最小關(guān)鍵字的記錄 */ if (R[j].keyR[j1].key) { temp=R[j]。 /*R[j]與 R[j1]進行交換 */ R[j]=R[j1]。 R[j1]=temp。 } } } 例 設待排序的表有 10個記錄 ,其關(guān)鍵字分別為 {9,8,7,6,5,4,3,2,1,0}。說明采用冒泡排序方法進行排序的過程。 初始關(guān)鍵字 9 8 7 6 5 4 3 2 1 0 i=0 0 9 8 7 6 5 4 3 2 1 i=1 0 1 9 8 7 6 5 4 3 2 i=2 0 1 2 9 8 7 6 5 4 3 i=3 0 1 2 3 9 8 7 6 5 4 i=4 0 1 2 3 4 9 8 7 6 5 i=5 0 1 2 3 4 5 9 8 7 6 i=6 0 1 2 3 4 5 6 9 8 7 i=7 0 1 2 3 4 5 6 7 9 8 i=8 0 1 2 3 4 5 6 7 8 9 在有些情況下 ,在第 i(i＜ n1)趟時已排好序