【正文】 R[s..?(s+t)/2?] 和 R[?(s+t)/2?+1..t] 分別按關(guān)鍵字有序， 則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。即： 將兩個 位置相鄰 的記錄有序子序列 歸并為 一個 記錄的有序序列 。 } } 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 歸并排序 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 歸 并 排 序 歸并排序的過程基于下列基本思想 進行： 將兩個或兩個以上的有序子序列 “歸并” 為一個有序序列。 k t。 // 后移 } elem[j + incr] = e。 e elem[j]。 j = 0 amp。 // 暫存 elem[i] int j。 i n。 其中， d 稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序 減為 1。 所謂“宏觀”調(diào)整，指的是，“跳躍式” 的插入排序。 // 后移 } elem[j + 1] = e。 e elem[j]。 j = 0 amp。 // 暫存 elem[i] int j。 i n。 插入 elem[i] 。 in。 elem[j+1] = elem[j] j elem[i] j= i1 上述循環(huán)結(jié)束后可以直接進行“插入” 插入位置 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 令 i = 1， 3， …, n, 實現(xiàn)整個序列的排序。 e elem[j]。 j)。amp。 2． 將 elem[j+1..i1]中的所有 記錄 均 后移 一個位置； 1． 在 elem[1..i1]中 查找 elem[i]的插入位置， elem[1..j] ? elem[i] elem[j+1..i1] ； 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 直接插入排序 （基于順序查找） 不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述 希爾排序 （基于逐趟縮小增量） 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 一、直接插入排序 利用 “順序查找” 實現(xiàn) “在 elem[0..i1]中 查找 elem[i]的插入位置” 算法的實現(xiàn)要點： 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 從 elem[i1]起向前進行順序查找 循環(huán)結(jié)束表明 elem[i]的插入位置為 j +1 j elem[i] for (j=i1。 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 4. 歸并類 通過 “歸并” 兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 2. 交換類 通過 “交換” 無序序列中的記錄從而得到其中 關(guān)鍵字最小 或 最大的記錄，并將它 加入到有序子序列中 ， 以此方法增加記錄的有序子序列的長度。 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 三、內(nèi)部排序的方法 內(nèi)部排序的過程是一個 逐步擴大 記錄的 有序序列長度 的過程。 例如： 將下列關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 調(diào)整為 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 一般情況下， 假設(shè)含 n個記錄的序列為 { R1, R2, … ， Rn } 其相應(yīng)的關(guān)鍵字序列為 { K1, K2, … ， Kn } 這些關(guān)鍵字相互之間可以進行比較，即在 它們之間存在著這樣一個關(guān)系 ： Kp1≤ Kp2≤ … ≤ Kpn 按此固有關(guān)系將上式記錄序列重新排列為 { Rp1, Rp2, … ， Rpn } 的 操作 稱作 排序 。求“關(guān)鍵字的平方值” 的目的是“擴大差別” ，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響 此方法適合于 : 關(guān)鍵字中的每一位都有某些數(shù)字重 復(fù)出現(xiàn)頻度很高的現(xiàn)象 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 折疊法 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化 ? 平衡化旋轉(zhuǎn)有兩類： ? 單旋轉(zhuǎn) (左旋和右旋 ) ? 雙旋轉(zhuǎn) (左旋加右旋和右旋加左旋 ) 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 右單旋轉(zhuǎn) LL型 左單旋轉(zhuǎn) RR型 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 左右雙旋轉(zhuǎn) LR型 右左雙旋轉(zhuǎn) RL型 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 構(gòu)造二叉平衡（查找）樹的方法 在插入過程中，采用平衡旋轉(zhuǎn)技術(shù) 依次插入的關(guān)鍵字為 5, 4, 2, 8, 6, 9 5 4 2 4 2 5 8 6 6 5 8 4 2 向右旋轉(zhuǎn) 一次 先向右旋轉(zhuǎn) 再向左旋轉(zhuǎn) 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 4 2 6 5 8 9 6 4 2 8 9 5 向左旋轉(zhuǎn)一次 繼續(xù)插入關(guān)鍵字 9 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 B 樹 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 B樹是一種 平衡 的 多路 查找 樹 r o o t 5 0 1 5 7 1 8 4 3 8 2 0 2 6 4 3 5 6 6 2 7 8 8 9 9 6四川大學(xué)計算機學(xué)院，主講教師：游洪躍 在 m 階的 B樹上，每個非終端結(jié)點可能含有： n 個 關(guān)鍵字 Ki（ 1≤ i≤n） nm n 個 指向記錄的指針 Di（ 1≤i≤n） n+1 個 指向子樹的指針 Ai（ 0≤i≤n） 多叉樹的特性 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 ?非葉結(jié)點中的 多個關(guān)鍵字 均 自小至大有序排列，即： K1 K2 … K n ? Ai1 所指子樹上所有關(guān)鍵字均 小于 Ki ? Ai 所指子樹上所有關(guān)鍵字均 大于 Ki 查找樹的特性 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 平衡樹的特性 ?樹中所有葉子結(jié)點均不帶信息，且在樹中的同一層次上 ?根結(jié)點或為葉子結(jié)點，或至少含有兩棵子樹 ?其余所有非葉結(jié)點均至少含有 ?m/2?棵子樹，至多含有 m 棵子樹 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 從根結(jié)點出發(fā)，沿指針 查找結(jié)點 和在結(jié)點內(nèi)進行 順序（或折半） 查找 兩個過程交叉進行 查找過程 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 若 查找成功 ，則 返回指向 被查關(guān)鍵字所在 結(jié)點的指針和關(guān)鍵字在結(jié)點中的位置 若 查找不成功 ，則 返回插入位置 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 是 B樹的一種變型 B+樹 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 ※ 每個葉子結(jié)點中含有 n 個關(guān)鍵字和 n 個指向記錄的指針 ；并且，所有葉子結(jié)點彼此相鏈接構(gòu)成一個有序鏈表 ，其 頭指針指向含最小關(guān)鍵字的結(jié)點 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 ※ 每個非葉結(jié)點中的關(guān)鍵字 Ki 即為 其相應(yīng)指針 Ai 所指子樹中關(guān)鍵字的最大值 ※ 所有葉子結(jié)點都處在 同一層次上，每個葉子結(jié)點中關(guān)鍵字的個數(shù)均介于 ?m/2?和 m 之間 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 查找過程 ※ 在 B+ 樹上，既可以進行縮小范圍的查找，也可以進行順序查找 ※ 在進行縮小范圍的查找時，不管成功與否，都必須查到葉子結(jié)點才能結(jié)束 ※ 若在結(jié)點內(nèi)查找時， Ki1 ＜ 給定值≤ Ki，則應(yīng)繼續(xù)在 Ai 所指子樹中進行查找 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 50 96 15 50 62 78 96 71 78 84 89 96 56 62 20 26 43 50 3 8 15 sq root 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 哈 希 查 找 (Hash) 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 以上討論的表示查找表的各種結(jié)構(gòu) 的共同 特點 ： 記錄在表中的位置和它的關(guān)鍵字之間不存在一個確定的關(guān)系 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 查找的過程 為給定值依次和關(guān) 鍵字集合中各個關(guān)鍵字進行 比較 查找的效率 取決于和給定值 進行比較 的關(guān)鍵字個數(shù) 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 用這類方法表示的查找表，其平均查找長度都不為零 不同的表示方法，其差別僅在于： 關(guān)鍵字和給定值進行比較的順序不同 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 只有一個辦法：預(yù)先知道所查關(guān)鍵字在表中的位置 對于頻繁使用的查找表，希望 ASL = 0 即，要求： 記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 在一般情況下，需在關(guān)鍵字與記錄在表中的存儲位置之間建立一個函數(shù)關(guān)系， 以 H(key) 作為關(guān)鍵字為 key 的記錄在表中的位置 ，通常 稱 這個函數(shù) H(key) 為 哈希函數(shù) 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 ※ 哈希函數(shù)是一個 映象 ，即： 將關(guān)鍵 字的集合映射到某個地址集合上， 它 的設(shè)置很靈活，只要這個地址集合的 大小不超出允許范圍即可 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 ※ 由于哈希函數(shù)是一個 壓縮映象 ，因 此，在一般情況下，很容易產(chǎn)生 “ 沖 突 ” 現(xiàn)象，即： key1? key2，而 H(key1) = H(key2) 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 ※ 很難 找到一個不產(chǎn)生沖突的哈希函數(shù)。 // 查找失敗 } 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 二叉排序樹 （二叉查找樹） 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 （ 1）若它的左子樹不空，則左子樹上 所有 結(jié)點的值 均小于 根結(jié)點的值 二叉排序樹 或者是一棵空樹；或者 是具有如下特性的二叉樹 （ 3）它的左、右子樹 也都 分別 是二叉 排序樹 （ 2）若它的右子樹不空，則右子樹上 所有 結(jié)點的值 均大于 根結(jié)點的值 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 50 30 80 20 90 10 85 40 35 25 23 88 是二叉排序樹 66 不 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 二叉排序樹的 查找算法 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 1）若給定值 等于 根結(jié)點的關(guān)鍵字， 則查找成功 2）若給定值 小于 根結(jié)點的關(guān)鍵字， 則繼續(xù)在左子樹上進行查找 3）若給定值 大于 根結(jié)點的關(guān)鍵字， 則繼續(xù)在右子樹上進行查找 否則 : 若二叉排序樹 為空 ，則查找不成功 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 50 30 80 20 90 85 40 35 88 32 查找關(guān)鍵字 == 50 , 35 , 90 , 95 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 n 個結(jié)點的二叉查找樹的數(shù)目 3 個結(jié)點的二叉查找樹 51*2*34*5*6*41C131 33*2 ???1 2 2 1 3 3 1 3 2 1 2 3 1 2 3 {123} {132} {213} {312} {321} n*n2C1n1?四川大學(xué)計算機學(xué)院，主講教師：游洪躍 如果對一棵二叉查找樹進行中序遍歷，可以按從小到大的順序，將各結(jié)點關(guān)鍵碼排列起來，所以也稱二叉查找樹為二叉排序樹 四川大學(xué)計算機學(xué)院，主講教師：游洪躍 在查找過程中，生成了一條 查找路徑 從根結(jié)點出發(fā)，沿著左分支或右