第四講 查找及排序

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

根據(jù)某個給定的K值，在查找表中尋找一個鍵值等于K的元素，若找到這樣的元素，則稱查找成功，此時的運算結(jié)果為該數(shù)據(jù)元素在查找表中的位置，否則稱查找不成功，運算結(jié)果為一特殊標志。 查找是許多重要的計算機程序中最耗費時間的部分，查找算法的優(yōu)劣密切關(guān)系著查找操作的速度?！锊檎业姆椒? 查找某個數(shù)據(jù)元素依賴于該數(shù)據(jù)元素在一組數(shù)據(jù)中所處的位置，即該組數(shù)據(jù)的組織方式，故應(yīng)按照數(shù)據(jù)元素的組織方式?jīng)Q定采用的查找方法；反過來，為了提高查找方法的效率，要求數(shù)據(jù)元素采用某些特殊的組織方式?！锼惴ǖ脑u價 查找時通常只需要很少的輔助空間，因此更關(guān)心的是它的時間復(fù)雜度。在查找算法中，基本運算是給定值與關(guān)鍵字的比較，所以算法的主要時間是花費在“比較”上。 對于含有n個數(shù)據(jù)元素的查找表，查找成功時的平均查找長度為：ASL= 其中，Pi為查找第i個數(shù)據(jù)元素的概率；Ci為查到第i個數(shù)據(jù)元素時，需與關(guān)鍵字進行比較的次數(shù)。順序查找 基本思想：從表的一端開始，依次將每個元素的關(guān)鍵字同給定值K進行比較，若某個元素的關(guān)鍵字等于給定值K，則表明查找成功，返回該元素的下標；反之，若直到所有元素都比較完畢，仍找不到關(guān)鍵字為K的元素，則表明查找失敗，返回特定的值。#definemaxsize表長typedefstruct{keytypekey;//關(guān)鍵字………//其他域}rec;typedefstructrecsqtable[maxsize+1];intn;//最后一個數(shù)據(jù)元素的下標voidseqsrch(sqtabler，keytypek){//在長度為n的表r中查找關(guān)鍵字為k的元素，r[n]為表尾的擴充;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時表明查找不成功}算法在順序查找時，Ci取決于所查元素在表中的位置，Ci=i，設(shè)每個元素的查找概率相等，即Pi=1/n，則查找成功的平均查找長度為：ASL=查找不成功的查找長度為n+1。優(yōu)點： 算法簡單且適應(yīng)面廣，對表的結(jié)構(gòu)無任何要求，無論元素是否按關(guān)鍵字有序都可應(yīng)用缺點：平均查找長度比較大，特別是當(dāng)n較大時，查找效率較低。二分查找 基本思想：設(shè)三個指針low,high和mid分別指示待查有序表的表頭，表尾和中間元素，在開始查找時，三個指針的初值分別為：low=1；high=n；mid=(low+high)/2。折半查找是從表的中間元素開始，用待查元素的關(guān)鍵字k和r[mid].key比較，此時有三種情況(假設(shè)該查找表按關(guān)鍵字的非遞減次序排列)。1)若r[mid].key=k，則查找成功；2)若r[mid].key>k，則k必在較低標號的那一半表中，令high=mid-13)若r[mid].key<k，則k必在較高標號的那一半表中，令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因為r[mid].key>k，所以向左找，令high=mid-1=5(2)low=1;high=5;mid=(1+5)div2=30513192137566475808892lowmidhigh因為r[mid].key<k，所以向右找，令low=mid+1=4(3)low=4;high=5;mid=(4+5)div2=40513192137566475808892lowmidhigh因為r[mid].key=k，查找成功，所查元素在表中的序號為mid的值(1)low=1;high=11;mid=(1+11)div2=6因為r[mid].key<k，所以向右找，令low=mid+1=7(2)low=7;high=11;mid=(7+11)div2=90513192137566475808892lowmidhigh因為r[mid].key<k，所以向右找，令low=mid+1=10(3)low=10;high=11;mid=(10+11)div2=100513192137566475808892lowmidhigh因為r[mid].key>k，所以向左找，high=mid-1=92.查找關(guān)鍵字k=85的情況0513192137566475808892lowmidhigh因為low>high，所以查找失敗voidBinsrch(sqtabler，keytypek)//在長度為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個元素的查找表為例，找到第6個元素僅需比較1次；找到第3個和第9個元素需比較2次；找到第1,4,7和10個元素需比較3次；找到第2,5,8和11個元素需比較4次。上面的查找過程可以用下圖所示的一棵二叉樹來表示。6391471011258樹中每一個結(jié)點表示表中的一個數(shù)據(jù)元素，結(jié)點中的值為該元素在表中的位置 查找某一元素的比較次數(shù)最多等于樹的深度.即log2n找到元素的過程正好是從根節(jié)點一直走到某個葉子節(jié)點的路徑，因此所用的比較次數(shù)最多等于樹的深度。由此看來，無論元素找到或找不到，查找某一元素的比較次數(shù)最多等于樹的深度.即log2n。排序(Sorting)，是指將一個無序序列整理成按值非遞減（遞增）順序排列的有序序列。排序排序分為內(nèi)排序和外排序。內(nèi)排序的整個排序過程都在內(nèi)存進行。當(dāng)文件很大以至于內(nèi)存不足以存放全部記錄，在排序過程中需要對外存進行存取訪問，稱之為外排序。我們只討論內(nèi)排序，并且排序的對象一般認為是順序存儲的線性表（一維數(shù)組）。內(nèi)部排序的方法

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

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

最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：需進行n-1趟起泡“比較”的次數(shù)：快速排序 基本思想：設(shè)輸入文件有n個記錄R1,R2,…,Rn,它們對應(yīng)的關(guān)鍵字是k1,k2,…,kn。該方法先取序列中任一關(guān)鍵字K(通常取第一個)，然后用K從兩頭到中間進行交換，就能形成一個分劃：凡是小于等于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]進行排序{do{while((r[j].key>=x.key)&&(j>i))j--;//從表尾一端開始比較if(i<j){r[i]=r[j];i++;while((r[i].key<=x.key)&&(i<j))i++;//再從表的始端起進行比較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時間分析:快速排序是目前內(nèi)部排序中最快的方法。若關(guān)鍵字的分布式均勻的，可以粗略的認為每次劃分都把文件分成長度相等的兩個文件。但如果原來的文件是有次序的，時間復(fù)雜性為O(n2)。因此，快速排序偏愛一個無次序的文件。令T(n)為分類n個記錄所需之比較次數(shù),設(shè)n=2k，則k=log2n，有：T(n)≤cn+2T(n/2)(其中cn為進行一趟排序所需的時間)T(n)≤cn+2(cn/2+2T(n/4))≤2cn+4T(n/4)……≤kcn+2kT(1)=O(nlog2n)直接插入排序假設(shè)在排序過程中，記錄序列R[1..n]的狀態(tài)為：

則一趟插入排序的基本思想為：將記錄R[i]插入到有序子序列R[1..i-1]中，使記錄的有序序列從R[1..i-1]變?yōu)镽[1..i]。顯然，完成這個“插入”需分三步進行：1．查找R[i]的插入位置j+1；2．將R[j+1..i-1]中的記錄后移一個位置；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]作為標志位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進行比較r[j+1]=r[0];}}//insort時間分析：

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

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

希爾排序 基本思想：對待排序記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。即：將記錄序列分成若干子序列，每個子序列分別進行插入排序,待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。假設(shè)將n個記錄分成d個子序列，則這d個子序列分別為：{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稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為1。例如：

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

第三趟希爾排序，設(shè)增量d=1voidShellInsert(Listr,intd)//本算法對直接插入算法作了以下修改：//1.前后記錄位置的增量是d，而不是1；//2.r[0]只是暫存單元，不是哨兵。當(dāng)j<=0時，插入位置已找到。{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個記錄的關(guān)鍵字,我們不采用順序比較,而是先從第一個關(guān)鍵字開始每隔4個關(guān)鍵字進行比較;同理第二個也從隔4個關(guān)鍵字進行比較,第三個…,第四個…,依次做下去.題中選d1=4,從小到大排序:例初始d1=44655134294170570

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

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

13,46分別交換兩次0513174246557094

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

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

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

?

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

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

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

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