第四講 查找及排序

第四講查找與排序★交換排序★插入排序★順序查找★二分查找★選擇排序查找(Searching)，也稱檢索，亦即查表，就是在大量的信息集中尋找一個(gè)“特定的”信息元素。人們幾乎每天都要做“查找”工作，如查詢電話號(hào)碼、查字典、查圖書目錄卡片等。查找是數(shù)據(jù)處理領(lǐng)域中的一個(gè)重要內(nèi)容，查找的效率將直接影響到數(shù)據(jù)處理的效率。查找基本概念☆查找表以集合為邏輯結(jié)構(gòu)，以查找為核心運(yùn)算，同時(shí)包括其他運(yùn)算的數(shù)據(jù)結(jié)構(gòu)?！铌P(guān)鍵字用來(lái)標(biāo)識(shí)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)，簡(jiǎn)稱鍵?！钪麝P(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字?！畲侮P(guān)鍵字可以標(biāo)識(shí)若干數(shù)據(jù)元素的關(guān)鍵字。☆查找

根據(jù)某個(gè)給定的K值，在查找表中尋找一個(gè)鍵值等于K的元素，若找到這樣的元素，則稱查找成功，此時(shí)的運(yùn)算結(jié)果為該數(shù)據(jù)元素在查找表中的位置，否則稱查找不成功，運(yùn)算結(jié)果為一特殊標(biāo)志。 查找是許多重要的計(jì)算機(jī)程序中最耗費(fèi)時(shí)間的部分，查找算法的優(yōu)劣密切關(guān)系著查找操作的速度?！锊檎业姆椒? 查找某個(gè)數(shù)據(jù)元素依賴于該數(shù)據(jù)元素在一組數(shù)據(jù)中所處的位置，即該組數(shù)據(jù)的組織方式，故應(yīng)按照數(shù)據(jù)元素的組織方式?jīng)Q定采用的查找方法；反過(guò)來(lái)，為了提高查找方法的效率，要求數(shù)據(jù)元素采用某些特殊的組織方式?！锼惴ǖ脑u(píng)價(jià) 查找時(shí)通常只需要很少的輔助空間，因此更關(guān)心的是它的時(shí)間復(fù)雜度。在查找算法中，基本運(yùn)算是給定值與關(guān)鍵字的比較，所以算法的主要時(shí)間是花費(fèi)在“比較”上。 對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表，查找成功時(shí)的平均查找長(zhǎng)度為：ASL= 其中，Pi為查找第i個(gè)數(shù)據(jù)元素的概率；Ci為查到第i個(gè)數(shù)據(jù)元素時(shí)，需與關(guān)鍵字進(jìn)行比較的次數(shù)。順序查找 基本思想：從表的一端開(kāi)始，依次將每個(gè)元素的關(guān)鍵字同給定值K進(jìn)行比較，若某個(gè)元素的關(guān)鍵字等于給定值K，則表明查找成功，返回該元素的下標(biāo)；反之，若直到所有元素都比較完畢，仍找不到關(guān)鍵字為K的元素，則表明查找失敗，返回特定的值。#definemaxsize表長(zhǎng)typedefstruct{keytypekey;//關(guān)鍵字………//其他域}rec;typedefstructrecsqtable[maxsize+1];intn;//最后一個(gè)數(shù)據(jù)元素的下標(biāo)voidseqsrch(sqtabler，keytypek){//在長(zhǎng)度為n的表r中查找關(guān)鍵字為k的元素，r[n]為表尾的擴(kuò)充;i指示查找結(jié)果r[n].key=k;i=0;//給監(jiān)督哨賦值while(r[i].key!=k)i++;if(i<n)printf(“succ,i=%d”,i);//查找成功，i指示待查元素在表中位置elseprintf(“unsucc”);//i=n時(shí)表明查找不成功}算法在順序查找時(shí)，Ci取決于所查元素在表中的位置，Ci=i，設(shè)每個(gè)元素的查找概率相等，即Pi=1/n，則查找成功的平均查找長(zhǎng)度為：ASL=查找不成功的查找長(zhǎng)度為n+1。優(yōu)點(diǎn)： 算法簡(jiǎn)單且適應(yīng)面廣，對(duì)表的結(jié)構(gòu)無(wú)任何要求，無(wú)論元素是否按關(guān)鍵字有序都可應(yīng)用缺點(diǎn)：平均查找長(zhǎng)度比較大，特別是當(dāng)n較大時(shí)，查找效率較低。二分查找 基本思想：設(shè)三個(gè)指針low,high和mid分別指示待查有序表的表頭，表尾和中間元素，在開(kāi)始查找時(shí)，三個(gè)指針的初值分別為：low=1；high=n；mid=(low+high)/2。折半查找是從表的中間元素開(kāi)始，用待查元素的關(guān)鍵字k和r[mid].key比較，此時(shí)有三種情況(假設(shè)該查找表按關(guān)鍵字的非遞減次序排列)。1)若r[mid].key=k，則查找成功；2)若r[mid].key>k，則k必在較低標(biāo)號(hào)的那一半表中，令high=mid-13)若r[mid].key<k，則k必在較高標(biāo)號(hào)的那一半表中，令low=mid+1例：給出表元素關(guān)鍵字為：{05,13,19,21,37,56,64,75,80,88,92}1.查找關(guān)鍵字k=21的情況(1)low=1;high=11;mid=(1+11)div2=60513192137566475808892lowmidhigh因?yàn)閞[mid].key>k，所以向左找，令high=mid-1=5(2)low=1;high=5;mid=(1+5)div2=30513192137566475808892lowmidhigh因?yàn)閞[mid].key<k，所以向右找，令low=mid+1=4(3)low=4;high=5;mid=(4+5)div2=40513192137566475808892lowmidhigh因?yàn)閞[mid].key=k，查找成功，所查元素在表中的序號(hào)為mid的值(1)low=1;high=11;mid=(1+11)div2=6因?yàn)閞[mid].key<k，所以向右找，令low=mid+1=7(2)low=7;high=11;mid=(7+11)div2=90513192137566475808892lowmidhigh因?yàn)閞[mid].key<k，所以向右找，令low=mid+1=10(3)low=10;high=11;mid=(10+11)div2=100513192137566475808892lowmidhigh因?yàn)閞[mid].key>k，所以向左找，high=mid-1=92.查找關(guān)鍵字k=85的情況0513192137566475808892lowmidhigh因?yàn)閘ow>high，所以查找失敗voidBinsrch(sqtabler，keytypek)//在長(zhǎng)度為n的有序表r中查找關(guān)鍵字為k的元素，查到后輸出{low=1；high=n；//置初值while(low<=high){mid=(low+high)/2；if(k==r[mid].key){printf("succi=%d\n"，mid)；break；}elseif(k>r[mid].key)

low=mid+1；//向右找else

high=mid-1；//向左找}if(low>high)printf("nosucc\n")；//low>high，查找不成功}算法以上面的11個(gè)元素的查找表為例，找到第6個(gè)元素僅需比較1次；找到第3個(gè)和第9個(gè)元素需比較2次；找到第1,4,7和10個(gè)元素需比較3次；找到第2,5,8和11個(gè)元素需比較4次。上面的查找過(guò)程可以用下圖所示的一棵二叉樹(shù)來(lái)表示。6391471011258樹(shù)中每一個(gè)結(jié)點(diǎn)表示表中的一個(gè)數(shù)據(jù)元素，結(jié)點(diǎn)中的值為該元素在表中的位置 查找某一元素的比較次數(shù)最多等于樹(shù)的深度.即log2n找到元素的過(guò)程正好是從根節(jié)點(diǎn)一直走到某個(gè)葉子節(jié)點(diǎn)的路徑，因此所用的比較次數(shù)最多等于樹(shù)的深度。由此看來(lái)，無(wú)論元素找到或找不到，查找某一元素的比較次數(shù)最多等于樹(shù)的深度.即log2n。排序(Sorting)，是指將一個(gè)無(wú)序序列整理成按值非遞減（遞增）順序排列的有序序列。排序排序分為內(nèi)排序和外排序。內(nèi)排序的整個(gè)排序過(guò)程都在內(nèi)存進(jìn)行。當(dāng)文件很大以至于內(nèi)存不足以存放全部記錄，在排序過(guò)程中需要對(duì)外存進(jìn)行存取訪問(wèn)，稱之為外排序。我們只討論內(nèi)排序，并且排序的對(duì)象一般認(rèn)為是順序存儲(chǔ)的線性表（一維數(shù)組）。內(nèi)部排序的方法

在排序的過(guò)程中，參與排序的記錄序列中存在兩個(gè)區(qū)域：有序區(qū)和無(wú)序區(qū)。內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過(guò)程。使有序區(qū)中記錄的數(shù)目增加一個(gè)或幾個(gè)的操作稱為一趟排序。存放待排序數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)：typedefstruct{intkey;datatypeotheritem;//其他域}records;typedefstructrecordsList[n+1];內(nèi)排序插入類排序直接插入排序折半插入排序希爾排序交換類排序冒泡排序快速排序選擇類排序選擇排序堆排序歸并類排序歸并排序其他排序計(jì)數(shù)排序基數(shù)排序冒泡排序 基本思想：比較k1和k2,如果這些關(guān)鍵字的值不符合排序順序,就交換k1和k2；然后對(duì)記錄k2和k3,k3和k4等等進(jìn)行相同的工作。直到kn-1和kn為止,到此得到一個(gè)最大(或最小)關(guān)鍵字值存在kn的位置上(通常將此過(guò)程叫做一趟)。重復(fù)這個(gè)過(guò)程,就得到在位置kn-1,kn-2等處的適當(dāng)記錄,使得所有記錄最終被排好序。例如:將5個(gè)記錄的關(guān)鍵字7,4,8,3,9進(jìn)行冒泡排序。排序后k1≤k2≤…≤kn(n=5)。7443347344837773888899999①②③④

第四趟就沒(méi)有可交換的偶對(duì),排序結(jié)束。voidbubblesort(Listr,intn){for(m=1;m<=n;m++)scanf(“%d”,&r[m]);k=n;do{all=“T”;//all=T,標(biāo)志沒(méi)有交換的;all=F,標(biāo)志有交換的for(m=1;m<=k-1;m++){i=m+1;if(r[m]>r[i]){max=r[m];r[m]=r[i];r[j]=max;all=“F”;}}k--;}while((all==“T”)||(k==1))}算法時(shí)間分析:最好的情況（關(guān)鍵字在記錄序列中順序有序）：只需進(jìn)行一趟起泡“比較”的次數(shù)：“移動(dòng)”的次數(shù)：n-10

最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：需進(jìn)行n-1趟起泡“比較”的次數(shù)：快速排序 基本思想：設(shè)輸入文件有n個(gè)記錄R1,R2,…,Rn,它們對(duì)應(yīng)的關(guān)鍵字是k1,k2,…,kn。該方法先取序列中任一關(guān)鍵字K(通常取第一個(gè))，然后用K從兩頭到中間進(jìn)行交換，就能形成一個(gè)分劃：凡是小于等于K的被移到左邊，凡是大于K的被移到右邊。例:初始關(guān)鍵字[4655134294051770]將46→xij第一次交換后[

55134294051770]ji第二次交換后[17551342940570]ji第三次交換后[17

134294055570]j第四次交換后[1705134294

5570]jii1755059446第五趟排序后0513174246557094第一趟排序后[17051342]46[945570]第二趟排序后[1305]17[42]46[945570]第三趟排序后[05]1317[42]46[945570]第四趟排序后0513174246[7055]94

例:初始關(guān)鍵字[4655134294051770]算法voidqksort(Listr,intL,intP)//將r[L]至r[P]進(jìn)行排序{do{while((r[j].key>=x.key)&&(j>i))j--;//從表尾一端開(kāi)始比較if(i<j){r[i]=r[j];i++;while((r[i].key<=x.key)&&(i<j))i++;//再?gòu)谋淼氖级似疬M(jìn)行比較if(i<j){r[j]=r[i];j--;}}}while(i!=j);r[i]=x;i++;j--;//一趟快排結(jié)束，將x移至正確位置if(L<j)qksort(r,L,j);//反復(fù)排序前一部分if(i<P)qksort(r,i,P);//反復(fù)排序后一部分}//qksort時(shí)間分析:快速排序是目前內(nèi)部排序中最快的方法。若關(guān)鍵字的分布式均勻的，可以粗略的認(rèn)為每次劃分都把文件分成長(zhǎng)度相等的兩個(gè)文件。但如果原來(lái)的文件是有次序的，時(shí)間復(fù)雜性為O(n2)。因此，快速排序偏愛(ài)一個(gè)無(wú)次序的文件。令T(n)為分類n個(gè)記錄所需之比較次數(shù),設(shè)n=2k，則k=log2n，有：T(n)≤cn+2T(n/2)(其中cn為進(jìn)行一趟排序所需的時(shí)間)T(n)≤cn+2(cn/2+2T(n/4))≤2cn+4T(n/4)……≤kcn+2kT(1)=O(nlog2n)直接插入排序假設(shè)在排序過(guò)程中，記錄序列R[1..n]的狀態(tài)為：

則一趟插入排序的基本思想為：將記錄R[i]插入到有序子序列R[1..i-1]中，使記錄的有序序列從R[1..i-1]變?yōu)镽[1..i]。顯然，完成這個(gè)“插入”需分三步進(jìn)行：1．查找R[i]的插入位置j+1；2．將R[j+1..i-1]中的記錄后移一個(gè)位置；3．將R[i]復(fù)制到R[j+1]的位置上。算法voidinsort(Listr,intn){//r為給定的表，其記錄為r[i]，i=1，…，nfor(i=2;i<=n;i++){r[0]=r[i];//r[0]作為標(biāo)志位j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j--;}//j從i-1至0，r[j].key與r[i].key進(jìn)行比較r[j+1]=r[0];}}//insort時(shí)間分析：

實(shí)現(xiàn)排序的基本操作有兩個(gè)：（1）“比較”序列中兩個(gè)關(guān)鍵字的大??；（2）“移動(dòng)”記錄。對(duì)于直接插入排序：最好的情況（關(guān)鍵字在記錄序列中順序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：“移動(dòng)”的次數(shù)：

2(n-1)“比較”的次數(shù)：“移動(dòng)”的次數(shù)：

希爾排序 基本思想：對(duì)待排序記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。即：將記錄序列分成若干子序列，每個(gè)子序列分別進(jìn)行插入排序,待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。假設(shè)將n個(gè)記錄分成d個(gè)子序列，則這d個(gè)子序列分別為：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}其中，d稱為增量，它的值在排序過(guò)程中從大到小逐漸縮小，直至最后一趟排序減為1。例如：

第二趟希爾排序，設(shè)增量d=3

第三趟希爾排序，設(shè)增量d=1voidShellInsert(Listr,intd)//本算法對(duì)直接插入算法作了以下修改：//1.前后記錄位置的增量是d，而不是1；//2.r[0]只是暫存單元，不是哨兵。當(dāng)j<=0時(shí)，插入位置已找到。{for(i=d+1;i<=n;i++)if(r[i]<r[i-d])//需將r[i]插入有序增量子表{r[0]=r[i];//暫存在R[0]j=i-d;while((j>0)and(r[0]<r[j])){r[j+d]=r[j];//記錄后移，查找插入位置j=j-d;}r[j+d]=r[0];//插入}}算法例如,假設(shè)文件中8個(gè)記錄的關(guān)鍵字,我們不采用順序比較,而是先從第一個(gè)關(guān)鍵字開(kāi)始每隔4個(gè)關(guān)鍵字進(jìn)行比較;同理第二個(gè)也從隔4個(gè)關(guān)鍵字進(jìn)行比較,第三個(gè)…,第四個(gè)…,依次做下去.題中選d1=4,從小到大排序:例初始d1=44655134294170570

55與1713與05第一趟后結(jié)果4617054294551370

46與0594與1346與13第二趟后結(jié)果d2=20517134246559470

13,46分別交換兩次0513174246557094

第三趟后結(jié)果d3=113與1794與70簡(jiǎn)單選擇排序 基本思想：首先在n個(gè)記錄中選擇一個(gè)具有最小或最大關(guān)鍵字的記錄，將選出的記錄與記錄集合中的第一個(gè)記錄交換位置。然后在r[2]至r[n]中選擇一個(gè)最小或最大的值與r[2]交換位置，…，依此類推，直至r[n-1]和r[n]比較完畢。voidslsort(Listr,intn)//每次從r[j](j=i+1,…n)中選了最小值，與r[i](i=1,2,…,n-1)交換，進(jìn)行分類{for(i=1;i<=n-1;i++)//共進(jìn)行n-1趟排序{m=i;for(j=i+1;j<=n;j++)if(r[j].key<r[m].key)m=j;//m指示關(guān)鍵字最小的記錄的序號(hào)if(m!=i){x=r[i];r[i]=r[m];r[m]=x;}}}例：關(guān)鍵字序列{055，55，60，13，05，94，17，70},利用選擇排序算法進(jìn)行排序。關(guān)鍵字r[1]055r[2]55r[3]60r[4]13r[5]05r[6]94r[7]17r[8]70i=1,m=505556013055941770i=2,m=405136055055941770i=3,m=705131755055946070i=4,m=405131755055946070i=5,m=505131755055946070i=6,m=705131755055609470i=7,m=805131755055607094算法的復(fù)雜性分析：當(dāng)選擇第一個(gè)最小值時(shí)需進(jìn)行n-1次比較，選第二個(gè)最小值時(shí)需進(jìn)行n-2次比較，…，選n-1個(gè)最小值時(shí)需進(jìn)行n-(n-1)次比較，所以總的比較次數(shù)為(n-1)+(n-2)+…+2+1=n(n-1)/2故排序n個(gè)記錄需要時(shí)間為O(n2)。由于執(zhí)行一次交換，需三次移動(dòng)記錄，最多交換n-1次，故最多移動(dòng)次數(shù)為3(n-1)堆排序堆是由n個(gè)記錄的線性序列{R1,R2,…，Rn};其關(guān)鍵字序列{k1,k2,…，kn},滿足下列特性時(shí)，稱之為堆?；蛉魧⒋藬?shù)列看成是一棵完全二叉樹(shù)的順序存儲(chǔ)表示，則堆或是空樹(shù)或是滿足下列特性的完全二叉樹(shù)：其左、右子樹(shù)分別是堆，并且當(dāng)左、右子樹(shù)不空時(shí)，根結(jié)點(diǎn)的值小于(或大于)左、右子樹(shù)根結(jié)點(diǎn)的值。下列兩個(gè)序列為堆，對(duì)應(yīng)的完全二叉樹(shù)如下圖{96，83，27，38，11，09}9683273811091236248547305391ki≤k2iki≤k2i+1ki≥k2iki≥k2i+1大根堆小根堆{12，36，24，85，47，30，53，91}1)首先將一個(gè)關(guān)鍵字集合用完全二叉樹(shù)的形式排列; 如給定關(guān)鍵字集合為{46,55,13,42,94,17,5,70}組成的完全二叉樹(shù)如下：465513429417570建堆的過(guò)程2)開(kāi)始建堆：采用篩選法，逐步將大的關(guān)鍵字篩到堆底。篩選法的思想是這樣的：

?假設(shè)集合r有m個(gè)結(jié)點(diǎn)，從某個(gè)結(jié)點(diǎn)i（第一次i=[m/2]）開(kāi)始篩選;

?先看第i個(gè)結(jié)點(diǎn)的左右子樹(shù)，設(shè)第i個(gè)結(jié)點(diǎn)的左子樹(shù)為kj,右子樹(shù)為kj+1。若kj<kj+1則沿左分支篩，否則沿右分支篩選，即（j=j+1）。將ki與kj進(jìn)行比較，若ki>kj則對(duì)調(diào)，小的上來(lái)大的下去。

?

然后kj作為新的根結(jié)點(diǎn)，再對(duì)新的根結(jié)點(diǎn)的左右子樹(shù)進(jìn)行判斷。重復(fù)上述過(guò)程，直到某個(gè)結(jié)點(diǎn)的左或右子樹(shù)根結(jié)點(diǎn)的下標(biāo)大于m為止。第一次調(diào)用篩選法：m=8,i=[m/2]=4,從i=4開(kāi)始，看k4的左右子樹(shù)，僅有左子樹(shù)，因此42與70比較，42<70，所以不變。j=i*2=8，i=j，再向下看，此時(shí)的i無(wú)左右子樹(shù),所以返回，如右圖所示。4655134294170570第二次調(diào)用篩選法：i=3,k3=13,13的左右子樹(shù)為17和05，因17>05,故沿右子樹(shù)比較，13>05,進(jìn)行對(duì)調(diào)，此時(shí)13無(wú)左右子樹(shù)，所以返回。46551342941705700513{46,55,13,42,94,17,05,70}{46,55,05,42,94,17,13,70}

?先看第i個(gè)結(jié)點(diǎn)的左右子樹(shù)，設(shè)第i個(gè)結(jié)點(diǎn)的左子樹(shù)為kj,右子樹(shù)為kj+1。若kj<kj+1則沿左分支篩，否則沿右分支篩選，即（j=j+1）。將ki與kj進(jìn)行比較，若ki>kj則對(duì)調(diào)，小的上來(lái)大的下去。

?然后kj作為新的根結(jié)點(diǎn)，再對(duì)新的根結(jié)點(diǎn)的左右子樹(shù)進(jìn)行判斷。重復(fù)上述過(guò)程，直到某個(gè)結(jié)點(diǎn)的左或右子樹(shù)根結(jié)點(diǎn)的下標(biāo)大于m為止。第三次調(diào)用篩選法：i=2,k2=55,因?yàn)?2<94，所以沿左子樹(shù)篩選，42<55,進(jìn)行對(duì)調(diào)，此時(shí)55還有左子樹(shù)70，因55<70，所以不變，再向下70無(wú)左右子樹(shù)，所以返回，此時(shí)二叉樹(shù)如右圖所示。4655054294171370第四次調(diào)用篩選法：i=1,k1=46,因?yàn)?5<42，所以沿右子樹(shù)篩選，05<46,進(jìn)行對(duì)調(diào)，此時(shí)46還有左右子樹(shù)17,13，因13<17，所以再沿右子樹(shù)篩選，13<46,所以對(duì)調(diào)，46無(wú)左右子樹(shù)，所以返回，此時(shí)二叉樹(shù)如右圖所示。4642055594171370554246054613{46,42,05,55,94,17,13,70}{05,42,13,55,94,17,46,70}

?先看第i個(gè)結(jié)點(diǎn)的左右子樹(shù)，設(shè)第i個(gè)結(jié)點(diǎn)的左子樹(shù)為kj,右子樹(shù)為kj+1。若kj<kj+1則沿左分支篩，否則沿右分支篩選，即（j=j+1）。將ki與kj進(jìn)行比較，若ki>kj則對(duì)調(diào)，小的上來(lái)大的下去。