VB教程03.查找和排序課件

1、查找查找也叫檢索，是根據(jù)給定的某個值，在表中確定一個關鍵字等于給定值的記錄或數(shù)據(jù)元素關鍵字是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，它可以標識一個數(shù)據(jù)元素查找方法評價查找速度占用存儲空間多少算法本身復雜程度平均查找長度ASL(Average Search Length)：為確定記錄在表中的位置，需和給定值進行比較的關鍵字的個數(shù)的期望值叫查找算法的1 順序查找查找過程：從表的一端開始逐個進行記錄的關鍵字和給定值的比較算法描述i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464監(jiān)視哨iiii比較次數(shù)=5比較次數(shù)：查找第n個元素： 1查

2、找第n-1個元素：2.查找第1個元素： n查找第i個元素： n+1-i查找失?。?n+1順序查找方法的ASL2 折半查找查找過程：每次將待查記錄所在區(qū)間縮小一半適用條件：采用順序存儲結(jié)構(gòu)的有序表算法實現(xiàn)設表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點,k為給定值初始時，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k=rmid.key，查找成功若krmid.key，則low=mid+1重復上述操作，直至lowhigh時，查找失敗算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 2

3、1 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185110742936判定樹：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92算法評價判定樹：描述查找過程的

4、二叉樹叫有n個結(jié)點的判定樹的深度為log2n+1折半查找法在查找過程中進行的比較次數(shù)最多不超過其判定樹的深度折半查找的ASL1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38分塊查找方法評價ASL最大最小兩者之間表結(jié)構(gòu)有序表、無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表查找方法比較順序查找折半查找分塊查找哈希表應用哈希函數(shù)，由記錄的關鍵字確定記錄在表中的地址，并將記錄放入此地址，

5、這樣構(gòu)成的表叫哈希查找又叫散列查找，利用哈希函數(shù)進行查找的過程叫例 30個地區(qū)的各民族人口統(tǒng)計表編號 地區(qū)別 總?cè)丝?漢族 回族.1 北京2 上海.以編號作關鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2以地區(qū)別作關鍵字，取地區(qū)名稱第一個拼音字母的序號作哈希函數(shù)：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19從例子可見：哈希函數(shù)只是一種映象，所以哈希函數(shù)的設定很靈活，只要使任何關鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象叫同義詞：具有相同函數(shù)值的兩個關鍵字，叫該哈希函數(shù)的哈希

6、函數(shù)通常是一種壓縮映象，所以沖突不可避免，只能盡量減少；同時，沖突發(fā)生后，應該有處理沖突的方法哈希函數(shù)的構(gòu)造方法直接定址法構(gòu)造：取關鍵字或關鍵字的某個線性函數(shù)作哈希地址，即H(key)=key 或 H(key)=akey+b特點直接定址法所得地址集合與關鍵字集合大小相等，不會發(fā)生沖突實際中能用這種哈希函數(shù)的情況很少平方取中法構(gòu)造：取關鍵字平方后中間幾位作哈希地址適于不知道全部關鍵字情況折疊法構(gòu)造：將關鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址種類移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加適于關鍵字位數(shù)很多，且每一位上數(shù)字分

7、布大致均勻情況例 關鍵字為 ：0442205864，哈希地址位數(shù)為45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位疊加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092間界疊加除留余數(shù)法構(gòu)造：取關鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=key MOD p，pm特點簡單、常用，可與上述幾種方法結(jié)合使用p的選取很重要；p選的不好，容易產(chǎn)生同義詞處理沖突的方法開放定址法方法：當沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即Hi=(H(key)

8、+di)MOD m，i=1,2,k(km-1)其中：H(key)哈希函數(shù) m哈希表表長 di增量序鏈地址法例 表長為11的哈希表中已填有關鍵字為17，60，29的記錄， H(key)=key MOD 11,現(xiàn)有第4個記錄，其關鍵字為38， 按三種處理沖突的方法，將它填入表中0 1 2 3 4 5 6 7 8 9 1060 17 29(1) H(38)=38 MOD 11=5 沖突38例 已知一組關鍵字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為：H(key)=key MOD 13, 用鏈地址法處理沖突0 1 2 3 4 5 6 7 8 9 10 11 1

9、2 14127796855198420231011鏈地址法方法：將所有關鍵字為同義詞的記錄存儲在一個單鏈表中，并用一維數(shù)組存放頭指針哈希查找過程及分析哈希查找過程給定k值計算H(k)此地址為空關鍵字=k查找失敗查找成功按處理沖突方法計算HiYNYN哈希查找分析哈希查找過程仍是一個給定值與關鍵字進行比較的過程評價哈希查找效率仍要用ASL哈希查找過程與給定值進行比較的關鍵字的個數(shù)取決于：哈希函數(shù)處理沖突的方法哈希表的填滿因子=表中填入的記錄數(shù)/哈希表長度排序基本操作比較兩個關鍵字大小將記錄從一個位置移動到另一個位置1 插入排序直接插入排序排序過程：整個排序過程為n-1趟插入，即先將序列中第1個記錄

10、看成是一個有序子序列，然后從第2個記錄開始，逐個進行插入，直至整個序列有序算法描述算法評價時間復雜度若待排序記錄按關鍵字從小到大排列(正序)關鍵字比較次數(shù)：記錄移動次數(shù)：2(n-1)若待排序記錄按關鍵字從大到小排列(逆序)關鍵字比較次數(shù)：記錄移動次數(shù)：若待排序記錄是隨機的，取平均值關鍵字比較次數(shù)：記錄移動次數(shù)：T(n)=O(n)空間復雜度：S(n)=O(1)折半插入排序排序過程：用折半查找方法確定插入位置的排序叫例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20.

11、i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 )算法描述算法評價比較的次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。雖然比較次數(shù)大大減少，可惜移動次數(shù)并未減少，所以排序效率仍為O(n2) 時間復雜度：T(n)=O(n)空間復雜度：S(n)=O(1)希爾排序(縮小增量法)排序過程：先取一個正整數(shù)d1

12、n，把所有相隔d1的記錄放一組，組內(nèi)進行直接插入排序；然后取d2r2.key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止第一趟冒泡排序，結(jié)果關鍵字最大的記錄被安置在最后一個記錄上對前n-1個記錄進行第二趟冒泡排序，結(jié)果使關鍵字次大的記錄被安置在第n-1個記錄位置重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止初態(tài)：46 82 40 52 67 31 21 73i=1： 46 40 52 67 31 21 73 82i=2： 40 46 52 31 21 67 73 82i=3： 40 46 31 21 52 67 73 82i=4

13、： 40 31 21 46 52 67 73 82i=5： 31 21 40 46 52 67 73 82i=6： 21 31 40 46 52 67 73 82i=7： 21 31 40 46 52 67 73 82算法描述算法評價時間復雜度最好情況（正序）比較次數(shù)：n-1移動次數(shù)：0最壞情況（逆序）比較次數(shù)：移動次數(shù)：空間復雜度：S(n)=O(1)T(n)=O(n)快速排序基本思想：通過一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄進行排序，以達到整個序列有序排序過程：對rst中記錄進行一趟快速排序，附設兩個指針i和j，設

14、樞軸記錄rp=rs，x=rp.key初始時令i=s,j=t首先從j所指位置向前搜索第一個關鍵字小于x的記錄，并和rp交換再從i所指位置起向后搜索，找到第一個關鍵字大于x的記錄，和rp交換重復上述兩步，直至i=j為止再分別對兩個子序列進行快速排序，直到每個子序列只含有一個記錄為止例初始關鍵字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 974927ijijij49

15、65ji1349ij4997ij3 選擇排序簡單選擇排序排序過程首先通過n-1次關鍵字比較，從n個記錄中找出關鍵字最小的記錄，將它與第一個記錄交換再通過n-2次比較，從剩余的n-1個記錄中找出關鍵字次小的記錄，將它與第二個記錄交換重復上述操作，共進行n-1趟排序后，排序結(jié)束例初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65