【正文】 7 6 9 7 ]（ h ） 第 七 趟 排 序 結(jié) 果“篩選法” 算法的 C函數(shù)如下： void heapSift(RecType R[],int i, int n) /*R[i]為根結(jié)點，調(diào)整 R[i]~R[n]為大根堆 */ { RecType rc。 rc=R[i]。 while(j=n) /*沿排序碼較大的孩子結(jié)點向下篩選 */ { if(jn amp。 R[j].keyR[j+1].key) /*j為排序碼較大的記錄下標(biāo) */ j=j+1。 /*記錄移動到 R[i] */ i=j。} /*調(diào)整進(jìn)入下一層 */ R[i]=rc。 RecType x。i=1。i1。 /*堆頂與最后一個記錄交換位置 */ R[i]=R[1]。 heapSift(R， 1， i1)。 時間效率：堆排序的時間主要消耗在篩選算法中，一共調(diào)用了 ?n/2?+n1（約 3n/2）次的篩選算法，在每次篩選算法中，排序碼之間的比較次數(shù)都不會超過完全二叉樹的高度，即 ?log2n? +1，所以整個堆排序過程的最壞時間復(fù)雜度為 O(nlog2n)，也是其平均時間復(fù)雜度。 空間效率：在整個堆排序過程中，需要 1個與記錄大小相同的輔助空間用于交換記錄，故其空間復(fù)雜度為 O(1)。 堆排序是一種不穩(wěn)定的排序方法。所謂 歸并 就是將兩個或多個有序表合并成一個有序表的過程。本節(jié)主要講二路歸并技術(shù)實現(xiàn)的歸并排序。設(shè) i=u， j=v+1， k=u，即 i， j， k分別指向三個有序表的起始下標(biāo)，歸并過程為：比較 R[i].key和 R[j].key的大小，如果 R[i].key≤R[j].key，則將第一個有序子表的記錄 R[i]復(fù)制到 A[k]中，并令 i和 k分別加 1，指向下一個位置，否則將第二個有序子表的記錄 R[j]復(fù)制到 A[k]中，并令 j和 k分別加 1，如此循環(huán)下去，直到其中一個有序子表已到表尾，然后將另一個有序子表中剩余的記錄復(fù)制到數(shù)組A[k]~A[t]中，至此二路歸并結(jié)束。每完成一趟歸并排序，都會使有序表的長度變?yōu)樯弦惶说?2倍，但最后一個有序表的長度有可能小一些。設(shè)數(shù)組 R中每個有序表的長度為 len，（最后一個表長度可能小于 len） ,對其進(jìn)行一趟歸并排序，結(jié)果存于數(shù)組 A中。 二路歸并算法的 C函數(shù)描述如下： void merge(RecType R[ ], RecType A[], int u, int v, int t) /*將兩個有序表 R[u]~R[v]和 R[v+1]~R[t]歸并到有序表 A[u]~A[t] */ { int i,j,k。amp。 k++； } while (j=t) /*處理第二個有序表中剩余的記錄 */ { A[k]=R[j]； j++。 for(p=1。p=p+2*len) /*歸并長度為 len等長有序表 */ merge(R， A， p， p+len1， p+len*21)。 else for(i=p。i++) /*把剩余的一個有序表復(fù)制到數(shù)組 A中 */ A[i]=R[i]。 len=1。 len=2*len。 len=2*len。 時間效率：歸并排序的時間復(fù)雜度應(yīng)為每一趟歸并排序的時間復(fù)雜度和歸并趟數(shù)的乘積。歸并排序的時間效率主要取決于記錄的移動次數(shù)。 167。 167。 *7． 6 基數(shù)排序 基數(shù)排序 （ Radix Sort）是與前面各類排序方法完全不同的一種排序方法，它是基于排序碼的結(jié)構(gòu)分解，然后通過“分配”和“收集”方法實現(xiàn)的排序。撲克牌的順序是： ?A＜ ?2＜ … ＜ ?J＜ ?Q＜ ?K＜ ?A＜ ?2＜ … ＜ ?K＜ ?A＜ ?2＜ … ＜ ?K＜ ?A＜ ?2＜ … ＜ ?K。 如何將排序碼分解成多個不同位權(quán)的元素 若排序碼 K是個十進(jìn)制整數(shù)，其值在 0~999范圍內(nèi)，則可以把每一位上的十進(jìn)制數(shù)字看成一個元素，即 K由 3個元素（ k1,k2,k3）組成，其中 k1的位權(quán)是 102（百位數(shù)）， k2的位權(quán)是 101（十位數(shù)）， k3的位權(quán)是 100（個位數(shù)）。當(dāng)排序碼為十進(jìn)制數(shù)時，基數(shù) r是 10；當(dāng)排序碼為字符串時，基數(shù) r是 26。排序時先按 kid 的值進(jìn)行分配，即將 n個記錄分到 r個堆中（有時形象地稱為裝箱），再按順序收集；然后按 kid1的值再進(jìn)行分配和收集，直至按 ki1分配和收集完畢為止，這樣重復(fù)做 d趟分配和收集，排序結(jié)束。 /*排序碼由 d個分量組成，這里排序碼是十進(jìn)制數(shù) */ DataType other。 /*靜態(tài)鏈域 */ } RecType。 /*數(shù)組 R存放 n個待排序記錄 */ typedef struct /*定義隊列 */ { int f,e。 Queue Q[r]。 時間效率：基數(shù)排序的平均時間復(fù)雜度為O(n)。 空間效率：在基數(shù)排序中，需要一個輔助空間數(shù)組 Q，但 Q的大小與 n無關(guān)，所以空間復(fù)雜度為 O(1)。 穩(wěn)定性：基數(shù)排序是穩(wěn)定的。 8． 1 查找的基本概念 167。 8． 3 索引查找 167。 8． 5 散列表查找 8．查找的基本概念 1．查找表 查找表 （ Search Table）是由記錄序列組成的文件或線性表。根據(jù)在查找表上實施的操作不同，可將查找表分為。 4．查找依據(jù)：一般是把記錄的關(guān)鍵字作為查找的依據(jù) 5． 查找 （ Search）的定義：給定某個特定值 k，在查找表中找出關(guān)鍵字等于給定值 k的記錄，若找到，則 查找成功 ，返回該記錄在表中的序號；否則 查找不成功 ，給出查找失敗的信息。 7．查找表常用的存儲方式：順序、鏈接、索引和散列四種來存儲。 8． 2順序表查找 167。 167。 DataType other。 RecType R[N+1]。 167。 順序查找的 基本思想 是：從表的一端開始，依次將每個記錄的關(guān)鍵字與給定值 k進(jìn)行比較，若某個記錄的關(guān)鍵字與 k相等，表明查找成功，并給出記錄在表中的位置（序號）；若整個表檢測完，仍未找到與 k相等的關(guān)鍵字，表明查找失敗，給出查找失敗的信息。 /*R[0]用作監(jiān)視哨 */ i=N。 平均查找長度 查找成功時，平均查找長度為： 查找不成功時，與關(guān)鍵字的比較次數(shù)總是 n+1次。 查找算法的平均時間復(fù)雜度 O(n)。 優(yōu)缺點 優(yōu)點是算法簡單，可以方便地插入記錄。 順序查找方法不僅適用于順序表，也同樣適合于單鏈表。 二分查找 （ Binary Search）又稱 折半查找 ，是一種效率較高的查找方法。 二分查找的 基本思想 是：初始時，查找區(qū)間為整個有序表，取查找區(qū)間的中間記錄作為比較對象，若中間記錄的關(guān)鍵字與給定值相等，則查找成功；若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的前半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵字，則在中間記錄的后半?yún)^(qū)繼續(xù)查找。 167。設(shè)變量 mid表示查找區(qū)間中間位置的下標(biāo)，計算公式： mid=? (low+hign)/2? （ 2）當(dāng) low≤high（查找區(qū)間非空）時，求 mid=? (low+hign)/2?，進(jìn)行如下比較： 若 k==R[mid].key，查找成功，返回記錄在表中位置 若 kR[mid].key，則 high=mid1，在前半?yún)^(qū)繼續(xù)查找 若 kR[mid].key，則 low=mid+1，在后半?yún)^(qū)繼續(xù)查找 （ 3）當(dāng) lowhigh時，查找區(qū)間為空，說明查找失敗 例 一個有序表中有 13個記錄，記錄的關(guān)鍵字序列為（ 7， 14， 18， 21， 23， 29， 31， 35， 38， 42， 46， 49， 52），給定值 k分別為 14和 22，在表中查找關(guān)鍵字與 k相等的記錄。 查找 k=22的過程示意圖 7 14 18 21 23 29 31 35 38 42 46 49 52 0 1 2 3 4 5 6 7 8 9 10 11 12 13 二分查找非遞歸算法的 C函數(shù)： int binarySearch(RecType R[ ], KeyType k) /*用二分查找法在數(shù)組 R中查找關(guān)鍵字為 k的記錄，若找到返回該記錄的位置，否則返回0。 low=1。 /*設(shè)置初始查找區(qū)間 */ while(low=high) /*查找區(qū)間非空 */ { mid=(low+high)/2。 /*查找成功，返回記錄的位置 */ else if(kR[mid].key) high=mid1。 /*調(diào)整到后半?yún)^(qū) */ } return 0。 二分查找過程 判定樹 例 查找成功情況下的平均查找長度為： ASL=（ 1+2 2+3 4+4 6） /13=36/13。 3 11 84 27 2 3 3 54 91 4 2 1 2 9 3 8 4 6 5 2二分查找性能分析 167。 二分查找算法的平均時間復(fù)雜度為 O(log2n) 0 1 111 1 2 2 2 . . . 2n kiiiA S L P C kn ????? ? ? ? ? ? ? ????221 l o g ( 1 ) 1 l o g ( 1 ) 1n nnn?? ? ? ? ? ?167。 缺點：在查找之前需要建立有序表，二分查找要求順序存儲有序表，因而在表中插入或刪除記錄都需要移動大量的記錄， 二分查找方法適合于數(shù)據(jù)相對穩(wěn)定的靜態(tài)查找表。 8． 3 索引查找 索引查找是建立在 索引存儲結(jié)構(gòu) 上的查找方法。把字典看作是索引查找的對象，其中，字典的正文是主要部分，稱作是 主表 ，字母索引表是為了方便查找而建立的索引，稱作是 索引表 。 索引存儲的 基本思想 是：除了存儲主表的記錄外，還要為主表建立一個或若干個附加的索引表。 167。 167。若一組記錄對應(yīng)一個索引項，則該索引表為 稀疏索引 （ Sparse Index）。 編號 姓名 性別 職稱 電話號碼 所在院系 1001 劉林 女 講師 82626777 法學(xué)院 1002 趙紅 男 教授 67891234 法學(xué)院 1003 陳曲 女 副教授 68889245 法學(xué)院 1004 南方 男 講師 89891900 理學(xué)院 1005 朱紅 男 講師 23452345 理學(xué)院 1006 劉微微 女 副教授 56347812 外語學(xué)院 1007 陳俊亮 男 副教授 34512345 外語學(xué)院 1008 趙婷婷 女 講師 67645321 外語學(xué)院 1009 陳華 女 教授 89764567 藝術(shù)學(xué)院 1010 佟曉偉 男 講師 34523455 藝術(shù)學(xué)院 （ 1）稠密索引： 稠密索引為每個記錄建立索引項（索引關(guān)鍵字，地址） 主表： 0 1 2 3 4 5 6 7 8 9 … 索引表： 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 …… 關(guān)鍵字 地址 1001 0 1002 1 1003 2 1004 3 1005 4 1006 5 1007 6 1008 7 1009 8 1010 9 1） 稀疏索引：把主表的記錄按照某種規(guī)則劃分為幾個 子表 ，然后再為每個子表建立索引項（索引關(guān)鍵字，地址） 按照所在院系劃分，可以有 4個子表，分別為：法學(xué)院LA1=（ 1001， 1002， 1003），理學(xué)院 LA2=（ 1004，1005），外語學(xué)院 LA3=（ 1006， 1007， 1008），藝術(shù)學(xué)院 LA4=（ 1009，