VB教程03.查找和排序

查找查找——也叫檢索，是根據(jù)給定的某個(gè)值，在表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素關(guān)鍵字——是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素查找方法評(píng)價(jià)查找速度占用存儲(chǔ)空間多少算法本身復(fù)雜程度平均查找長(zhǎng)度ASL(AverageSearchLength)：為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值叫查找算法的~1順序查找查找過程：從表的一端開始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較算法描述i例01234567891011513192137566475808892找6464監(jiān)視哨iiii比較次數(shù)=5比較次數(shù)：查找第n個(gè)元素：1查找第n-1個(gè)元素：2……….查找第1個(gè)元素：n查找第i個(gè)元素：n+1-i查找失敗：n+1順序查找方法的ASL2折半查找查找過程：每次將待查記錄所在區(qū)間縮小一半適用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表算法實(shí)現(xiàn)設(shè)表長(zhǎng)為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn),k為給定值初始時(shí)，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k==r[mid].key，查找成功若k<r[mid].key，則high=mid-1若k>r[mid].key，則low=mid+1重復(fù)上述操作，直至low>high時(shí)，查找失敗算法描述lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhigh1185110742936判定樹：1234567891011513192137566475808892算法評(píng)價(jià)判定樹：描述查找過程的二叉樹叫~有n個(gè)結(jié)點(diǎn)的判定樹的深度為log2n+1折半查找法在查找過程中進(jìn)行的比較次數(shù)最多不超過其判定樹的深度折半查找的ASL3分塊查找查找過程：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找適用條件：分塊有序表算法實(shí)現(xiàn)用數(shù)組存放待查記錄,每個(gè)數(shù)據(jù)元素至少含有關(guān)鍵字域建立索引表，每個(gè)索引表結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針?biāo)惴枋鯟h7_3.c12345678910111213141516171822121389203342443824486058745786532248861713索引表查38分塊查找方法評(píng)價(jià)ASL最大最小兩者之間表結(jié)構(gòu)有序表、無序表有序表分塊有序表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性鏈表順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性鏈表查找方法比較順序查找折半查找分塊查找4哈希查找基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法定義哈希函數(shù)——在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系叫~哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象哈希函數(shù)可寫成：addr(ai)=H(ki)ai是表中的一個(gè)元素addr(ai)是ai的存儲(chǔ)地址ki是ai的關(guān)鍵字關(guān)鍵字集合存儲(chǔ)地址集合hash哈希表——應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫~哈希查找——又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過程叫~例30個(gè)地區(qū)的各民族人口統(tǒng)計(jì)表編號(hào)地區(qū)別總?cè)丝跐h族回族…...1北京2上?！?..…...以編號(hào)作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2以地區(qū)別作關(guān)鍵字，取地區(qū)名稱第一個(gè)拼音字母的序號(hào)作哈希函數(shù)：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19從例子可見：哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即可沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象叫~同義詞：具有相同函數(shù)值的兩個(gè)關(guān)鍵字，叫該哈希函數(shù)的~哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免，只能盡量減少；同時(shí)，沖突發(fā)生后，應(yīng)該有處理沖突的方法哈希函數(shù)的構(gòu)造方法直接定址法構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希地址，即H(key)=key或H(key)=a·key+b特點(diǎn)直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會(huì)發(fā)生沖突實(shí)際中能用這種哈希函數(shù)的情況很少數(shù)字分析法構(gòu)造：對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況例有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機(jī)所以：取任意兩位或兩位與另兩位的疊加作哈希地址平方取中法構(gòu)造：取關(guān)鍵字平方后中間幾位作哈希地址適于不知道全部關(guān)鍵字情況折疊法構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）做哈希地址種類移位疊加：將分割后的幾部分低位對(duì)齊相加間界疊加：從一端沿分割界來回折送，然后對(duì)齊相加適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況例關(guān)鍵字為：0442205864，哈希地址位數(shù)為4586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加除留余數(shù)法構(gòu)造：取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=keyMODp，pm特點(diǎn)簡(jiǎn)單、常用，可與上述幾種方法結(jié)合使用p的選取很重要；p選的不好，容易產(chǎn)生同義詞處理沖突的方法開放定址法方法：當(dāng)沖突發(fā)生時(shí)，形成一個(gè)探查序列；沿此序列逐個(gè)地址探查，直到找到一個(gè)空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即Hi=(H(key)+di)MODm，i=1,2,……k(km-1)其中：H(key)——哈希函數(shù)

m——哈希表表長(zhǎng)

di——增量序鏈地址法例表長(zhǎng)為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄，

H(key)=keyMOD11,現(xiàn)有第4個(gè)記錄，其關(guān)鍵字為38，按三種處理沖突的方法，將它填入表中012345678910601729(1)H(38)=38MOD11=5沖突38例已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函數(shù)為：H(key)=keyMOD13,

用鏈地址法處理沖突012345678910111214^127796855198420231011^^^^^^^^^^^^鏈地址法方法：將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，并用一維數(shù)組存放頭指針哈希查找過程及分析哈希查找過程給定k值計(jì)算H(k)此地址為空關(guān)鍵字==k查找失敗查找成功按處理沖突方法計(jì)算HiYNYN哈希查找分析哈希查找過程仍是一個(gè)給定值與關(guān)鍵字進(jìn)行比較的過程評(píng)價(jià)哈希查找效率仍要用ASL哈希查找過程與給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)取決于：哈希函數(shù)處理沖突的方法哈希表的填滿因子=表中填入的記錄數(shù)/哈希表長(zhǎng)度排序排序定義——將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列叫~排序分類按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過程中需對(duì)外存進(jìn)行訪問的排序按排序依據(jù)原則插入排序：直接插入排序、折半插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排序：簡(jiǎn)單選擇排序其它排序:堆排序等排序基本操作比較兩個(gè)關(guān)鍵字大小將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置1插入排序直接插入排序排序過程：整個(gè)排序過程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序算法描述例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827

(13273849657697)排序結(jié)果：算法評(píng)價(jià)時(shí)間復(fù)雜度若待排序記錄按關(guān)鍵字從小到大排列(正序)關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：2(n-1)若待排序記錄按關(guān)鍵字從大到小排列(逆序)關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：若待排序記錄是隨機(jī)的，取平均值關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：T(n)=O(n2)空間復(fù)雜度：S(n)=O(1)折半插入排序排序過程：用折半查找方法確定插入位置的排序叫~例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)算法描述算法評(píng)價(jià)比較的次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。雖然比較次數(shù)大大減少，可惜移動(dòng)次數(shù)并未減少，所以排序效率仍為O(n2)時(shí)間復(fù)雜度：T(n)=O(n2)空間復(fù)雜度：S(n)=O(1)希爾排序(縮小增量法)排序過程：先取一個(gè)正整數(shù)d1<n，把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2<d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹谷3=1三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分組：49

38

65

97

76

13

27

48

55

4取d2=3二趟分組：13

27

48

55

4

49

38

65

97

76希爾排序特點(diǎn)子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列希爾排序可提高排序速度，因?yàn)榉纸M后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序增量序列取法無除1以外的公因子最后一個(gè)增量值必須為12交換排序冒泡排序排序過程將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至第n-1個(gè)記錄和第n個(gè)記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上對(duì)前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交換記錄的操作”為止[初態(tài)]：4682405267312173i=1：4640526731217382i=2：4046523121677382i=3：4046312152677382i=4：4031214652677382i=5：3121404652677382i=6：2131404652677382i=7：2131404652677382算法描述算法評(píng)價(jià)時(shí)間復(fù)雜度最好情況（正序）比較次數(shù)：n-1移動(dòng)次數(shù)：0最壞情況（逆序）比較次數(shù)：移動(dòng)次數(shù)：空間復(fù)雜度：S(n)=O(1)T(n)=O(n2)快速排序基本思想：通過一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄進(jìn)行排序，以達(dá)到整個(gè)序列有序排序過程：對(duì)r[s……t]中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針i和j，設(shè)樞軸記錄rp=r[s]，x=rp.key初始時(shí)令i=s,j=t首先從j所指位置向前搜索第一個(gè)關(guān)鍵字小于x的記錄，并和rp交換再?gòu)膇所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于x的記錄，和rp交換重復(fù)上述兩步，直至i==j為止再分別對(duì)兩個(gè)子序列進(jìn)行快速排序，直到每個(gè)子序列只含有一個(gè)記錄為止例初始關(guān)鍵字：4938659776132750ijxji完成一趟排序：(273813)49(76976550)分別進(jìn)行快速排序：(13)27(38)49(5065)76(97)快速排序結(jié)束：13273849