【正文】 } } while(i=j)。 iright ) i++ ； /* 確定 i點交換位置 */ while(xitem[j] amp。 下一頁 上一頁 停止放映 [第 67頁 /81] 快速排序算法舉例 對于數(shù)列 {49， 38， 60， 90， 70， 15， 30， 49}， 采用中點分界法： 初始狀態(tài) : 49 38 60 90 70 15 30 49 比較次數(shù) 第 1趟 49 38 60 90 70 15 30 49 49 38 60 90 70 15 30 49 5（ i j1） 49 38 60 49 70 15 30 90 5（ i j1） { 49 38 60 49 70 15 30 } 90 小計： 10 i k = 90 j i j j i 下一頁 上一頁 停止放映 [第 68頁 /81] 快速排序算法舉例（續(xù)一） 初始狀態(tài) : 49 38 60 49 70 15 30 比較次數(shù) 第 2趟 49 38 60 49 70 15 30 2（ i j1） 30 38 60 49 70 15 49 30 38 60 49 70 15 49 30 38 15 49 70 60 49 { 30 38 15}49{ 70 60 49 } 小計： 8 i j k = 49 j i i j 3（ i j1） i j 3（ i j2） 下一頁 上一頁 停止放映 [第 69頁 /81] 快速排序算法舉例（續(xù)二） 初始狀態(tài) : 30 38 15 比較次數(shù) 第 3趟 30 38 15 3（ i j1） { 30， 15 } 38 小計： 3 第 4趟 70 60 49 2（ i j1） 49 60 70 2（ i j1） 小計： 4 k = 38 i j j i k = 60 j i j i 下一頁 上一頁 停止放映 [第 70頁 /81] 快速排序算法舉例（續(xù)三） 初始狀態(tài) : 30 15 比較次數(shù) 第 5趟 30 15 2（ i j1） 15 30 小計： 2 最后狀態(tài)： { 15 30 38 49 49 60 70 90 } 總計： 27 k = 30 i j 下一頁 上一頁 停止放映 [第 71頁 /81] 快速排序算法 quick_sort(item,count) int *item,count。 下一頁 上一頁 停止放映 [第 65頁 /81] 快速排序基本思想 ? 在待排序序列中按某種方法選取一個元素 K， 以它為分界點 ， 用交換的方法將序列分為兩個部分：比該值小的放在左邊 ， 否則在右邊 。 //交換位置 item[b1]=item[b]。 ? 用改進的冒泡算法進行處理 ， 比較次數(shù)有所減少 。 i++) for (int j=0。 直到全部元素有序為止 。++j) //尋找最小值循環(huán) { if(item[j]t) { k=j。 ? Step3 重復(fù) Step2， 共進行 n1趟的選擇處理 ， 數(shù)列全部有序 。 //有序部分起始位置 while(j=0amp。 下一頁 上一頁 停止放映 [第 51頁 /81] 插入排序算法步驟 ? Step1 從有序數(shù)列 {a1}和無序數(shù)列 {a2,a3,… ,an}開始進行排序 。 這些關(guān)鍵字相互之間可以進行比較 ， 即在它們之間存在著這樣一個關(guān)系Kp1≤K p2≤ … ≤K pn， 按此固有關(guān)系將最初的記錄序列重新排列為 { Rp1, Rp2, … ， Rpn }的操作稱作排序 。 Step2 重復(fù)計算處理沖突的下一個存儲地址 Dk=R （ Dk1 ） ， 直到 HST[Dk] 為空 ， 或HST[Dk}=k為止 。 若該地址對應(yīng)的存儲空間還沒有被占用 ， 則將該元素存入；否則執(zhí)行 step2解決沖突 。 處理沖突是建立哈希表過程中不可缺少的一部分 。 在哈希表中可以實現(xiàn)對數(shù)據(jù)元素的快速檢索 。假定由整數(shù)序列 {10， 6， 19， 22， 8， 2}生成一棵二叉排序樹，可以采用逐個元素插入的方法實現(xiàn)。 return root。 //或插入右子 } else //若根為空 { rright=0。 } } 下一頁 上一頁 停止放映 [第 28頁 /81] 生成二叉排序樹程序 struct tree create_btree(struct tree *root, struct tree *r, char info) { if (r == 0 ) { r = new (struct tree)。 //插入頭結(jié)點 else create_btrr(root,root,*s)。 下一頁 上一頁 停止放映 [第 24頁 /81] 二叉排序樹結(jié)點結(jié)構(gòu) typedef struct BinNode { ElemType x。能否設(shè)計更好的算法？使其既有二分法的高效率，又有鏈表靈活性的查找方法？ ? 動態(tài)查找技術(shù)所依賴的查找表就是這樣的算法，例如二叉排序樹等。 下一頁 上一頁 停止放映 [第 19頁 /81] 分塊查找舉例 有數(shù)列如下： { 22,12,13,9,8,33,42,44,38,24,48,60,58,75,47} 按 “ 塊有序 ” 分三塊 : (22,12,13,9,8),(33,42,44,38,24), (48,60,58,74,47) 選取每塊中最大的關(guān)鍵字組成索引表 [22,44,74],查找關(guān)鍵字值為 60的元素。 //繼續(xù)在前半?yún)^(qū)間進行查找 else low = mid + 1。 – Step3 對確定的縮小區(qū)域再按二分公式 ， 重復(fù)上述步驟； – 最后 ， 得到結(jié)果： ?要么 ， 查找成功 ， 要么 ， 查找失敗 。 //找不到時 ， k為 0 } 該算法若查找成功 ， 則函數(shù)返回值為目標(biāo)元素在表中的位置 ， 否則返回 0。為提高效率，對查找表的結(jié)構(gòu)改動如下： 適當(dāng)設(shè)置數(shù)組長度，將元素存于 data[1]至data[length1]中，在 0號單元預(yù)存待查找數(shù)據(jù) key作為監(jiān)視哨。 while(kamp。 //表的長度 }。就是統(tǒng)計一篇文章中使用了多少詞匯以及每個詞匯的使用次數(shù)。 查找往往根據(jù)數(shù)據(jù)元素的某個屬性進行。 下一頁 上一頁 停止放映 [第 3頁 /81] 靜態(tài)查找表 : 查找表一旦建立 ， 在以后的查找過程中就不會改變 。 下一頁 上一頁 停止放映 [第 4頁 /81] 平均查找長度： 為了確定數(shù)據(jù)元素在查找表中的位置，需要將給定值和表中的數(shù)據(jù)元素的關(guān)鍵字進行比較的次數(shù)的期望值。 下一頁 上一頁 停止放映 [第 7頁 /81] 算法描述 ? 查找操作步驟： – step1 從第 1個元素開始查找； – step2 用待查關(guān)鍵字值與各結(jié)點（ 記錄 ） 的關(guān)鍵字值逐個進行比較；若找到相等的結(jié)點 ， 則查找成功；否則 ， 查找失敗 。 if (k) return k+1。 下一頁 上一頁 停止放映 [第 11頁 /81] 改進的順序查找算法 C++語言描述如下： int SqSearch(SSTable amp。 即通過一次比較 ， 將查找區(qū)間縮小一半 。 low = 0。 則查找過程如下： 第 1次 ： { 5， 6， 11， 17， 21， 23， 28， 30， 32， 40 } low=0 mid=(0+9)/2 =4 high=9 等概率情況下其平均查找長度 為 1)1(l o g 2 ??? nA S L ，即 O(log2n) 例子 第 2次： { 5， 6， 11， 17， 21， 23， 28， 30， 32， 40 } low=5 mid=7 high=9 下一頁 上一頁 停止放映 [第 17頁 /81] 分塊查找 ? 分塊查找又稱索引順序查找 ， 這是順序查找的一種改進方法 。 下一頁 上一頁 停止放映 [第 20頁 /81] 索引表結(jié)構(gòu)定義 typedef st