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