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