查找與排序課件

查找與排序

順序查找是一種最基本和最簡(jiǎn)單的查找方法。它的思路是，從表中的第一個(gè)元素開始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒(méi)有要找的元素，查找不成功。對(duì)于表中記錄的關(guān)鍵字是無(wú)序的表，只能采用這種方法。描述順序查找的算法見(jiàn)框圖8-1。其中n是表r的長(zhǎng)度，k是要查的元素的關(guān)鍵字，i查到的元素的序號(hào)。

上一章下一章返回目錄折半查找又稱二分查找，是針對(duì)有序表進(jìn)行查找的簡(jiǎn)單、有效而又較常用的方法。所謂有序表，即要求表中的各元素按關(guān)鍵字的值有序（升序或降序）存放。折半查找不像順序查找那樣，從第一個(gè)記錄開始逐個(gè)順序搜索，其基本思想是：首先選取表中間位置的記錄，將其關(guān)鍵字與給定關(guān)鍵字k進(jìn)行比較，若相等，則查找成功；否則，若k值比該關(guān)鍵字值大，則要找的元素一定在表的后半部分（或稱右子表），則繼續(xù)對(duì)右子表進(jìn)行折半查找；若k值比該關(guān)鍵字值小，則要找的元素一定在表的前半部分（左子表），同樣應(yīng)繼續(xù)對(duì)左子表進(jìn)行折半查找。每進(jìn)行一次比較，要么找到要查找的元素，要么將查找的范圍縮小一半。如此遞推，直到查找成功或把要查找的范圍縮小為空（查找失?。?。設(shè)表的長(zhǎng)度為n，表的被查找部分的頭為low，尾為high，初始時(shí)，low=1,high=n,k為關(guān)鍵字的值。（2）若k=r[mid].key,成功，否則：若k<r[mid].key,則high=mid―1,重復(fù)（1）；若k>r[mid].key,則low=mid+1,重復(fù)（1）；直到成功或不成功（此時(shí)low>high）。具體算法如下：Voidbinsrch(structnoder[],intn,intk){intmid,low,high,find;low=1;high=n;find=0; /*置區(qū)間初值*/

while((low<=high)&&(!find)){mid=(low+high)/2; /*求中點(diǎn)*/

if(k==r[mid].key)find=1; /*已查到*/

elseif(k>r[mid].key)low=mid+1; /*在后半?yún)^(qū)間查找*/

elsehigh=mid-1; /*在前半?yún)^(qū)間查找*/}if(find)return(mid); /*查找成功，返回找到元素的位置*/elsereturn(0); /*查找不成功，返回0標(biāo)記*/}采用折半查找，當(dāng)查找成功時(shí)，最少比較次數(shù)為一次，如在上例中查找關(guān)鍵字值為18的結(jié)點(diǎn)，只需一次比較。最多經(jīng)過(guò)log2n次比較之后，待查找子表要么為空，要么只剩下一個(gè)結(jié)點(diǎn)，所以要確定查找失敗需要log2n次或log2n+1次比較?？梢宰C明，折半查找的平均查找長(zhǎng)度是：從折半查找的平均查找長(zhǎng)度ASL來(lái)看，當(dāng)表的長(zhǎng)度n很大時(shí)，該方法尤其能顯示出其時(shí)間效率。但由于折半查找的表仍是線性表，若經(jīng)常要進(jìn)行插入、刪除操作，則元素排列費(fèi)時(shí)太多，因此折半查找比較適合于一經(jīng)建立就很少改動(dòng)而又需要經(jīng)常查找的線性表，較少查找而又經(jīng)常需要改動(dòng)的線性表可以采用鏈接存儲(chǔ)，使用順序查找。分塊查找在處理線性表時(shí)，如果既希望能夠快速查找，又要經(jīng)常動(dòng)態(tài)變化，則可以采用分塊查找方法。分塊查找又稱索引順序查找，要求將待查的元素均勻的分成塊，塊間按大小排序，塊內(nèi)不排序。因此需要建立一個(gè)塊的最大（或最?。╆P(guān)鍵字表，稱之為“索引表”。具體而言，假設(shè)我們按結(jié)點(diǎn)元素關(guān)鍵字升序方式組織表中各塊，則要求第一塊中任一結(jié)點(diǎn)的關(guān)鍵字值都小于第二塊中所有結(jié)點(diǎn)的關(guān)鍵字值；第二塊中任一結(jié)點(diǎn)的關(guān)鍵字值都小于第三塊中所有結(jié)點(diǎn)的關(guān)鍵字值；如此類推。然后選擇每塊中的最大（或最?。╆P(guān)鍵字值組成索引表。換言之，索引表中的結(jié)點(diǎn)個(gè)數(shù)等于線性表被分割的塊數(shù)。例如要找關(guān)鍵字為k的元素，則先用折半查找法由索引表查出k所在的塊，再用順序查找法在對(duì)應(yīng)的塊中找出k。在圖8-2中若要找關(guān)鍵字值為41的元素，則先由索引表查出41在第二塊中（29<41<64），再在第二塊中找到41。由此我們可以總結(jié)：分塊查找分兩步進(jìn)行，第一步確定要查找結(jié)點(diǎn)在表中的哪一塊，第二步在確定的塊中找到該結(jié)點(diǎn)。分塊查找的平均查找長(zhǎng)度為：

ASL=ASLb+ASLe其中ASLb是折半查找的平均查找長(zhǎng)度，ASLe是用順序查找法查塊內(nèi)元素的平均查找長(zhǎng)度。設(shè)每塊中有s個(gè)元素，可以近似的得到：可以看出分塊查找的平均查找長(zhǎng)度位于順序查找和折半查找之間。下面我們簡(jiǎn)單的對(duì)以上幾種查找方法做出比較：（1）平均查找長(zhǎng)度：折半查找最小，分塊查找次之，順序查找最大；（2）表的結(jié)構(gòu)：順序查找對(duì)有序表、無(wú)序表均適用；折半查找僅適用于有序表；分塊查找要求表中元素是逐段有序的，就是塊與塊之間的記錄按關(guān)鍵字有序；（3）存儲(chǔ)結(jié)構(gòu)：順序查找和分塊查找對(duì)向量和線性鏈表結(jié)構(gòu)均適用；折半查找只適用于向量存儲(chǔ)結(jié)構(gòu)的表，因而要求表中元素基本不變，而在需要插入或刪除運(yùn)算時(shí)，要移動(dòng)元素，才能保持表的有序性，所以影響了查找效率。哈希法哈希法又名散列法,因其英文單詞Hash而得名,是一種完全不同的查找方法。前面我們所介紹的三種查找方法的共同特點(diǎn)在于：通過(guò)對(duì)關(guān)鍵字的一系列比較，逐步縮小查找范圍，直到確定結(jié)點(diǎn)的存儲(chǔ)位置或確定查找失敗。而哈希法則希望不經(jīng)過(guò)任何比較，一次存取就能得到所查元素，因此必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系，使得每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)，這樣查找時(shí)只需對(duì)結(jié)點(diǎn)的關(guān)鍵字進(jìn)行某種運(yùn)算就能確定結(jié)點(diǎn)在表中的位置。因此哈希法的平均比較次數(shù)和表中所含結(jié)點(diǎn)的個(gè)數(shù)無(wú)關(guān)。打個(gè)比方讓我們更清楚的認(rèn)識(shí)哈希法的不同。假定某教室有35個(gè)座位，如果不加限定讓學(xué)生任意就座，則要找某個(gè)學(xué)生時(shí)就要將待找學(xué)生與當(dāng)前座位上的學(xué)生一一做比較，這就是我們前面所介紹的查找方法的大致思路。而哈希法則要限定學(xué)生所坐的位置，比如可規(guī)定學(xué)生座位的編號(hào)應(yīng)與其學(xué)號(hào)的末兩位相同，則學(xué)號(hào)為993605的學(xué)生應(yīng)坐編號(hào)為5的座位。這樣我們要找某個(gè)學(xué)生時(shí)只需根據(jù)其學(xué)號(hào)的末兩位到相應(yīng)座位上去找即可，不必一一比較了。在這個(gè)例子里，學(xué)生好比記錄，學(xué)號(hào)則為關(guān)鍵字，對(duì)關(guān)鍵字進(jìn)行的操作則是取其末兩位，用以確定記錄的位置。哈希函數(shù)的構(gòu)造方法一個(gè)好的哈希函數(shù)應(yīng)使函數(shù)值均勻的分布在存儲(chǔ)空間的有效地址范圍內(nèi)，以盡可能減少?zèng)_突。但鑒于實(shí)際問(wèn)題中關(guān)鍵字的不同，沒(méi)法構(gòu)造出統(tǒng)一的哈希函數(shù)。從而構(gòu)造哈希函數(shù)的方法多種多樣，這里只介紹一些比較常用的、計(jì)算較為簡(jiǎn)便的方法。1．自身函數(shù)關(guān)鍵字自身作為哈希函數(shù)，即H（k）=k，也可自身加上一個(gè)常數(shù)作為哈希函數(shù)，即H(k)=k+c。例如上例中建立的哈希函數(shù)H(學(xué)號(hào))=學(xué)號(hào)-9900采用的就是這樣的方法。但這種函數(shù)只適用于給定的一組關(guān)鍵字為關(guān)鍵字集合中的全體元素的情況，故不常用。2．除余法選擇一個(gè)適當(dāng)?shù)恼麛?shù)m，用m去除關(guān)鍵字，取其余數(shù)作為散列地址，即H（key）=key%m。上例中后來(lái)所設(shè)定的函數(shù)H(學(xué)號(hào))=學(xué)號(hào)%10采用的就是除余法。但是在這種方法中，m的選擇是值得研究的。如果選擇關(guān)鍵字內(nèi)部代碼基數(shù)的冪次來(lái)除關(guān)鍵字，其結(jié)果必定是關(guān)鍵字的低位數(shù)字均勻性較差。若取m為任意偶數(shù)，則當(dāng)關(guān)鍵字內(nèi)部代碼為偶數(shù)時(shí)，得到的哈希函數(shù)值為偶數(shù)；若關(guān)鍵字內(nèi)部代碼為奇數(shù)，則哈希函數(shù)值為奇數(shù)。因此，m為偶數(shù)也是不好的。理論分析和試驗(yàn)結(jié)果均證明m應(yīng)取小于存儲(chǔ)區(qū)容量的素?cái)?shù)。查找：根據(jù)給定的某個(gè)值，在表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。關(guān)鍵字(Keyword)：一個(gè)或一組能唯一標(biāo)識(shí)該記錄的數(shù)據(jù)項(xiàng)稱為該記錄的關(guān)鍵字。平均查找長(zhǎng)度（AverageSearchLength）：為確定記錄在表中的位置所進(jìn)行的和關(guān)鍵字的比較的次數(shù)的期望值稱之為查找算法的平均查找長(zhǎng)度，簡(jiǎn)稱ASL。有序表：表中的各元素按關(guān)鍵字的值有序（升序或降序）存放。哈希表：將結(jié)點(diǎn)的關(guān)鍵字key作為自變量，通過(guò)一個(gè)確定的函數(shù)關(guān)系H，計(jì)算出相應(yīng)的函數(shù)值H(key)，然后以H(key)作為該結(jié)點(diǎn)的存儲(chǔ)單元地址。用這種方式建立起來(lái)的線性表稱為哈希表或叫散列表哈希函數(shù)：把結(jié)點(diǎn)關(guān)鍵字轉(zhuǎn)換為該結(jié)點(diǎn)存儲(chǔ)單元地址的函數(shù)H稱為哈希函數(shù)或叫散列函數(shù)。在學(xué)習(xí)這些概念的基礎(chǔ)上，我們先后學(xué)習(xí)了三種基于將待查元素的關(guān)鍵字和表中元素的關(guān)鍵字進(jìn)行比較的查找算法，即順序查找、折半查找和分塊查找，并對(duì)它們做出比較。我們也學(xué)習(xí)了一種不同的查找算法，即哈希法，它的基本思路是：在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系，使得每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)，這樣查找時(shí)只需對(duì)結(jié)點(diǎn)的關(guān)鍵字進(jìn)行某種運(yùn)算就能確定結(jié)點(diǎn)在表中的位置，其間我們知道了如何構(gòu)造哈希函數(shù)和如何解決沖突問(wèn)題。讀者應(yīng)熟悉各種查找算法的思路、算法及性能分析，以靈活應(yīng)用于各種實(shí)際問(wèn)題中。

排序排序（sorting）是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。由于待排序的記錄數(shù)量不同，使得排序過(guò)程中涉及的存儲(chǔ)器不同，可將排序方法分為兩大類：一類是內(nèi)部排序，指的是待排序記錄存放在計(jì)算機(jī)存儲(chǔ)器中進(jìn)行的排序過(guò)程；另一類是外部排序，指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過(guò)程中對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。插入排序

線性插入排序的基本思想是：第1遍，將初始文件中的記錄R1看作有序子文件，將R2插入這個(gè)子文件中。若R2的關(guān)鍵字小于R1的關(guān)鍵字，則R2插在R1的前面，否則R2插在R1的后面。第2遍，將R3插入前面的兩個(gè)記錄的有序子文件中，得到3個(gè)記錄的有序子文件。依此類推，繼續(xù)進(jìn)行下去，直到將Rn插入到前面的n-1個(gè)記錄的有序子文件中，最后得到n個(gè)記錄的有序文件。線性插入排序的基本思想是：第1遍，將初始文件中的記錄R1看作有序子文件，將R2插入這個(gè)子文件中。若R2的關(guān)鍵字小于R1的關(guān)鍵字，則R2插在R1的前面，否則R2插在R1的后面。第2遍，將R3插入前面的兩個(gè)記錄的有序子文件中，得到3個(gè)記錄的有序子文件。依此類推，繼續(xù)進(jìn)行下去，直到將Rn插入到前面的n-1個(gè)記錄的有序子文件中，最后得到n個(gè)記錄的有序文件。圖9-1所示為線性插入排序的例子。為了避免檢測(cè)是否應(yīng)插在R1的前面，在R1的前面設(shè)立記錄R0，它既是中間變量，又是監(jiān)視哨。設(shè)（R1，R2，…，Ri-1）是已排序的有序子文件，則插入Ri的步驟是：首先將Ri存放到Ro中，然后將Ko（即原Ri的關(guān)鍵字Ki）依次與Ki-1，Ki-2，…比較，若Ko<Kj（j=i-1，i-2，…，1），則Rj后移一個(gè)位置，否則停止比較和移動(dòng)；最后，將Ro（即原來(lái)待插入的記錄Ri）移到j(luò)+1的位置上。由于Ri的前面有監(jiān)視哨Ro，因此不必每次判斷下標(biāo)j是否出界。算法描述如下：voidinsertsort(structnoder[n+1],intn)/*r[n+1]為一維數(shù)組，其中r[0]為監(jiān)視哨，r[1]到r[n]為待排序的n個(gè)記錄，排序好的記錄仍放在r中*/{for(i=2;i<=n;i++) /*共進(jìn)行n-1趟*/{r[0]=r[i]; /*r[0]為監(jiān)視哨，也可做下邊循環(huán)結(jié)束標(biāo)志*/

j=i-1;while(r[j].key>r[0].key){r[j+1]=r[j];j--;}r[j+1]=r[0];}}

折半插入排序

在線性插入排序中，我們采用順序查找法來(lái)確定記錄的插入位置。由于（R1，R2，…，Ri-1）是有序子文件，我們可以采用折半查找法來(lái)確定R1的插入位置，這種排序稱為折半插入排序。其算法可寫出如下：voidbinarysort(structnoder[n+1],intn)/*按關(guān)鍵字遞增的次序?qū)τ涗況[1],r[2],……,r[n]進(jìn)行折半插入排序*/{for(i=2;i<=n;i++){r[0]=r[i];l=1;h=i-1;while(l<=h){mid=(l+h)/2;if(r[0].key<r[mid].key)h=mid-1;elsel=mid+1;}for(j=i-1;j>=l;j--)r[j+1]=r[j];r[l]=r[0];}}在上面的算法中，每插入一個(gè)R1，平均比較次數(shù)為log2i。希爾排序

希爾排序（Shell’sMethod）又稱“縮小增量排序”（DiminishingIncrementSort），是由D.L.Shell在1959年提出來(lái)的。它的作法是：先取定一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組，所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中，在各組內(nèi)進(jìn)行直接插入排序；然后，到第二個(gè)增量d2<d1重復(fù)上述分組和排序，直至所取的增量dt=1（dt<dt-1<…<d2<d1），即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。先從一個(gè)具體的例子來(lái)看希爾排序。假設(shè)待排序文件有10個(gè)記錄，其關(guān)鍵字分別是：49，38，65，97，76，13，27，49/，55，04。增量序列取值依次為：5，3，1。第一趟排序時(shí)，d1=5，整個(gè)文件被分成5組：（R1，R6），（R2，R7），…，（R5，R10）各組中的第1個(gè)記錄都自成一個(gè)有序區(qū)，我們依次將各組的第2個(gè)記錄R6，R7，…R10分別插入到各組的有序區(qū)中，使文件的各組均是有序的，其結(jié)果見(jiàn)圖9-2的第七行。第二趟排序時(shí)，d2=3，整個(gè)文件分成三組：（R1，R4，R7，R10），（R2，R5，R8），（R3，R6，R9），各組的第1個(gè)記錄仍自成一個(gè)有序區(qū)，然后依次將各組的第2個(gè)記錄R4，R5，R6分別插入到該組的當(dāng)前有序區(qū)中，使得（R1，R4），（R2，R5），（R3，R6）均變?yōu)樾碌挠行騾^(qū)，接著依次將各組的第3個(gè)記錄R7，R8，R9分別插入到該組當(dāng)前的有序區(qū)中，又使得（R1，R4，R7），（R2，R5，R8），（R3，R6，R9）均變?yōu)樾碌挠行騾^(qū)，最后將R10插入到有序區(qū)（R1，R4，R7）中就得到第二趟排序結(jié)果。最后一趟排序時(shí)，d3=1，即是對(duì)整個(gè)文件做直接插入排序，其結(jié)果即為有序文件。若不設(shè)置監(jiān)視哨，根據(jù)上例的分析不難寫出希爾排序算法，請(qǐng)讀者自行完成之。下面我們先分析如何設(shè)置監(jiān)視哨，然后給出具體算法。設(shè)某一趟希爾排序的增量為h，則整個(gè)文件被分成h組：（R1，Rh+1，R2h+1，…），（R2，Rh+2，R2h+2，…），…（Rh，R2h，R3h，…），因?yàn)楦鹘M中記錄之間的距離均為是h，故第1組至第h組的哨兵位置依次為1-h，2-h，…，0。如果象直接插入排序算法那樣，將待插入記錄Ri（h+1≤i≤N）在查找插入位置之前保存到監(jiān)視哨中，那么必須先計(jì)Ri屬于哪一組，才能決定使用哪個(gè)監(jiān)視哨來(lái)保存Ri。為了避免這種計(jì)算，我們可以將Ri保存到另一個(gè)輔肋記錄X中，而將所有監(jiān)視哨R1-h，R2-h，…，R0的關(guān)鍵字，設(shè)置為小于文件中的任何關(guān)鍵字即可。因?yàn)樵隽渴亲兓模?，各趟排序中所需的監(jiān)視哨數(shù)目也不相同，但是我們可以按最大增量d1來(lái)設(shè)置監(jiān)視哨。rectypeR[n+d1]； /*R[d1-1]為d1個(gè)監(jiān)視哨*/intd[t]； /*d[0]到d[t-1]為增量序列*/SHELLSORT(R,d)RectypeR[]；intd[]；{inti，j，k，h；

rectypetemp;intmaxint=32767； /*機(jī)器中最大整數(shù)*/

for(i=0；i<d[0]；i++)R[i].key=-maxint； /*設(shè)置哨兵*/

K=0；

Do{H=d[k]； /*取本趟增量*/

For(i=h+di；i<n+d1；i++) /*R[h+d1]到R[n+d1-1]插入當(dāng)前有序區(qū)*/{temp=R[i]}； /*保存待插入記錄R[i]*/j=i-h；

while(temp.key<R[j].key) /*查找正確的插入位置*/{R[j+h]=R[j]}； /*后移記錄*/

j=j-h； /*得到前一記錄位置*/}

R[j+h]=temp； /*插入R[i]*/} /*本趟排序完成*/

k++；

}while(h！=1)； /*增量為1排序后終止算法*/} /*SHELLSORT*/讀者可能看出，當(dāng)增量h=1時(shí)，SHELLSORT算法與INSERTSORT基本一致。對(duì)希爾排序的分析提出了許多困難的數(shù)學(xué)問(wèn)題，特別是如何選擇增量序列才能產(chǎn)生最好的排序效果，至今沒(méi)有得到解決。希爾本為最初提出取d1=┗n/2┛，di+1=┗di/2┛，dt=1，t=┗log2n┛。后來(lái)又有人提出其它選擇增量序列的方法，如di+1=┗(di-1)/3┛，dt=1，t=┗log3n-1┛；以及di+1=┗(di-1)/2┛，dt=1，t=┗log2n-1┛。為什么希爾排序的時(shí)間性能優(yōu)于直接插入排序呢？我們知道直接插入排序在文件初態(tài)為正序時(shí)所需要時(shí)間最少，實(shí)際上，當(dāng)文件初基本有序時(shí)直接插入排序所需的比較和移動(dòng)次數(shù)均較少。另一面，當(dāng)n值較小時(shí)，n和n2的差別也較小，即直接插入排序的最好時(shí)間復(fù)雜度O(n)和最壞時(shí)間復(fù)雜度O(n2)差別不大。在希爾排序時(shí)增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來(lái)增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過(guò)序，使文件較近于有序狀態(tài)，所以新的國(guó)趟排序過(guò)程也較快。因此，希爾排序在較率上較直接接入排序有較大的改進(jìn)。希爾排序是不穩(wěn)定的。參見(jiàn)圖9-2的例子，該例中兩個(gè)相同關(guān)鍵字49在排序前后的相對(duì)次序發(fā)生了變化。選擇排序

選擇排序（selectionsort）也是一種簡(jiǎn)單排序法。一個(gè)記錄最多只需進(jìn)行一次交換就可以直接到達(dá)它的排序位置。設(shè)待排序的文件為（R1，R2，…，Rn），進(jìn)行選擇排序的基本步驟如下：（1）置i為1；（2）當(dāng)i<n時(shí)，重復(fù)下列步驟；1）當(dāng)(Ri，…，Rn)中選出一個(gè)關(guān)鍵字最小的記錄Rmin，若Rmin不是Ri，即Rmin≠i則交換Ri和Rmin的位置；否則，不進(jìn)行交換。2）i的值加1。第1遍掃描時(shí)，在n個(gè)記錄中為了選出最小關(guān)鍵字的記錄，需要進(jìn)行n-1次比較，第2掃描時(shí)，在余下的n-1記錄中，再選出具有最小關(guān)鍵字的記錄需要比較n-2次，……第n-1掃描時(shí)，在最后的2個(gè)記錄中，比較1次選出最小關(guān)鍵字的記錄。堆排序

堆排序(heapsort)是在選擇排序的基礎(chǔ)上發(fā)展起來(lái)的。它比選擇排序的效率要高。在堆排序中，把待排序的文件邏輯上看作是一棵順序二叉樹，并用到堆的概念。在介紹堆排序之前，先引入堆的概念。我們回憶一下，一棵有n個(gè)結(jié)點(diǎn)的順序二叉樹可以用一個(gè)長(zhǎng)度為n的向量(一維數(shù)組)來(lái)表示；反過(guò)來(lái)，一個(gè)有n個(gè)記錄的順序表示的文件，在概念上可以看作是一棵有n個(gè)結(jié)點(diǎn)(即記錄)的順序二叉樹。例如，一個(gè)順序表示的文件(R1，R2，……，R9)，可以看作為圖9-4所示的順序二叉樹。當(dāng)我們把順序表示的文件(R1，R2，…，Rn)看作為順序二叉樹時(shí)，由順序二叉樹的性質(zhì)可知：記錄Ri(1<i≤n)的雙親是記錄R[i2]；R1的左孩子是記錄R2i(2i≤n)，但若2i>n，則Ri的左孩子不存在；Ri的右孩子是記錄R2i+1(2i+1≤n)，但若2i+1>n，則Ri的右孩子不存在。什么是堆呢?堆是一個(gè)具有這樣性質(zhì)的順序二叉樹，每個(gè)非終端結(jié)點(diǎn)(記錄)的關(guān)鍵字大于等于它的孩子結(jié)點(diǎn)的關(guān)鍵字。例如，圖9-5所示的順序二叉樹就是一個(gè)堆。顯然，在一個(gè)堆中，根結(jié)點(diǎn)具有最大值(指關(guān)鍵字，下同)，而且堆中任何一個(gè)結(jié)點(diǎn)的非空左、右子樹都是一個(gè)堆，它的根結(jié)點(diǎn)到任一葉子的每條路徑上的結(jié)點(diǎn)都是遞減有序的。堆排序的基本思想是：首先把待排序的順序表示(一維數(shù)組)的文件(R1，R2，…，Rn)在概念上看作一棵順序二叉樹，并將它轉(zhuǎn)換成一個(gè)堆。這時(shí)，根結(jié)點(diǎn)具有最大值，刪去根結(jié)點(diǎn)，然后將剩下的結(jié)點(diǎn)重新調(diào)整為一個(gè)堆。反復(fù)進(jìn)行下去，直到只剩下一個(gè)結(jié)點(diǎn)為止。堆排序的關(guān)鍵步驟是如何把一棵順序二叉樹調(diào)整為一個(gè)堆。初始狀態(tài)時(shí)，結(jié)點(diǎn)是隨機(jī)排列的，需要經(jīng)過(guò)多次調(diào)整才能把它轉(zhuǎn)換成一個(gè)堆，這個(gè)堆叫做初始堆。建成堆之后，交換根結(jié)點(diǎn)和堆的最后一個(gè)結(jié)點(diǎn)的位置，相當(dāng)于刪去了根結(jié)點(diǎn)。同時(shí)，剩下的結(jié)點(diǎn)(除原堆中的根結(jié)點(diǎn))又構(gòu)成一棵順序二叉樹。這時(shí)，根結(jié)點(diǎn)的左、右子樹顯然仍都是一個(gè)堆，它們的根結(jié)點(diǎn)具有最大值(除上面刪去的原堆中的根結(jié)點(diǎn))。把這樣一棵左、右子樹均是堆的順序二叉樹調(diào)整為新堆，是很容易實(shí)現(xiàn)的。例如，對(duì)于圖7-7所示的堆，交換根結(jié)點(diǎn)63和最后的結(jié)點(diǎn)30之后，便得到圖9-6(a)所示的順序二叉樹(除63之外)。現(xiàn)在，新的根結(jié)點(diǎn)是30，其左、右子樹仍然都是堆。下面討論如何把這棵二叉樹調(diào)整為一個(gè)新堆。由于堆的根結(jié)點(diǎn)應(yīng)該是具有最大值的結(jié)點(diǎn)，且已知左、右子樹是堆，因此，新堆的根結(jié)點(diǎn)應(yīng)該是這棵二叉樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)的左孩子，根結(jié)點(diǎn)的右孩子(若存在的話)中最大的那個(gè)結(jié)點(diǎn)。于是，先找出根結(jié)點(diǎn)的左、右孩子，比較它們的大小。將其中較大的孩子再與根結(jié)點(diǎn)比較大小。如果這個(gè)孩子大于根結(jié)點(diǎn)，則將這個(gè)孩子上移到根結(jié)點(diǎn)的位置，而根結(jié)點(diǎn)下沉到這個(gè)孩子的位置，即交換它們的位置。在圖9-6(a)中，根結(jié)點(diǎn)30的左、右孩子分別是60、59，由于60>59，并且60>30，于是應(yīng)交換根結(jié)點(diǎn)30和左孩子60的位置。這時(shí)，新的根結(jié)點(diǎn)60的右子樹沒(méi)有改變，仍然是一個(gè)堆。但是，由于結(jié)點(diǎn)30下沉到左子樹的根上，使得左子樹有可能不再是堆了。按照上面所用的辦法，把這棵子樹調(diào)整為一個(gè)堆，顯然，結(jié)點(diǎn)30的左、右子樹原來(lái)都是堆，30的左、右子樹分別是40，45。由于40<45，并且45>30，于是應(yīng)交換結(jié)點(diǎn)30和右孩子45的位置。voidadjust(structnoder[m+1],intm)/*將文件(r[1],r[2],…,r[m])解釋為一棵順序二叉樹,將其中以r[i]為根結(jié)點(diǎn)的二叉樹調(diào)整為一個(gè)堆,設(shè)以r[i]為根的二叉樹的左,右子樹已是堆,1≤i≤1[m/2]*/{x=r[i];j=2*i; /*求出r[i]的左孩子r[2*i]，即r[j]*/while(j<=m)/*有左孩子*/{if((j<m)&&(r[j].key<r[j+1].key)) /*比較左、右孩子*/

j=j+1;/*左孩子<右孩子*/

if(x.key<r[j].key) /*比較根結(jié)點(diǎn)和它的大孩子*/{r[i]=r[j]; /*大孩子上移到它的雙親位置*/

i=j;/*今r[j]為根結(jié)點(diǎn)*/

j=2*i; /*求出左孩子*/}

elsej=m+1 /*根不小于它的任一孩子時(shí)，強(qiáng)迫退出while循環(huán)*/}r[i]:=x; /*將存放在x中的根結(jié)點(diǎn)放到r[i]中*/}

快速排序

快速排序(QuickSort)稱劃分交換排序。其基本思想是：在當(dāng)前無(wú)序區(qū)R[1]到R[h]到中任取一個(gè)記錄作為比較的“基準(zhǔn)”（不妨記為temp），用此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序子區(qū)：R[1]到R[i-1]和R[i+1]到R[h]，且左邊的無(wú)序子區(qū)中記錄的關(guān)鍵字均小于或等于基準(zhǔn)temp的關(guān)鍵字，右邊的無(wú)序子區(qū)中記錄的關(guān)鍵字均大于或等于基準(zhǔn)temp的關(guān)鍵字，而基準(zhǔn)temp則位于最終排序的位置上R[1]到R[i-1]中關(guān)鍵字≤temp.key=R[i+1]到R[h]的關(guān)鍵字（1≤i≤h）當(dāng)R[1]到R[I-1]和R[I+1]到R[h]均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過(guò)程，直至所有無(wú)序子區(qū)中記錄均已排好序?yàn)橹?。要完成?duì)當(dāng)前無(wú)序區(qū)R[1]到R[h]的劃分，具體做法是：設(shè)置兩個(gè)指針i和j，它們的初值分別為i=1和j=h。不妨取基準(zhǔn)為無(wú)序區(qū)的第1個(gè)記錄R[i]（即R[1]），并將它保存在變量temp中。令j自h起向左掃描，直到找到第1個(gè)關(guān)鍵字小于temp.key的記錄R[j]，將R[j]移至i所指的位置上（這相當(dāng)于交換了R[j]和基準(zhǔn)R[i]（即temp）的位置，使關(guān)鍵字小于基準(zhǔn)關(guān)鍵字的記錄移到了基準(zhǔn)的左邊）；然后，令i自i+1起向右掃描，直至找到第1個(gè)關(guān)鍵字大于temp.key的記錄R[i]，將R[i]移至j指的位置上（這相當(dāng)于交換了R[j]和基準(zhǔn)R[i]（即temp）的位置，使關(guān)鍵字大于基準(zhǔn)關(guān)鍵字的記錄移到了基準(zhǔn)的右邊）；接著，令j自j+1起向右掃描，如此交替改變掃描方向，從兩端各自往中間靠攏，直至i=j時(shí)，i便是基準(zhǔn)x的最終位置，將x放在此位置上就完成了一次劃分。綜合上面的敘述，下面分別給出一次劃分及其排序的算法。intpartition(r,1,h) /*返回劃分后被定們的基準(zhǔn)記錄的位置*/rectypeR[]; /*對(duì)無(wú)序區(qū)R[1]到R[h]做劃分*/int1,h;{inti,j;rectypetemp;i=1;j=htemp=R[i]; /*初始化，temp為基準(zhǔn)*/

Do{While((R[j].key>=temp.key)&&(i<j))j--; /*從右向左掃描，查找第1個(gè)關(guān)鍵字小于temp.key的記錄*/

if(i<j)R[i++]=R[j]; /*交換R[i]和R[j]*/while((R[i].key<=temp.key)&&(i<j))i++; /*從左向左掃描，查找第1個(gè)關(guān)鍵字大于temp.key的記錄*/

if(i<j)R[j--]=R[i]; /*交換R[i]和R[j]*/}

quicksort(R,s1,t1) /*對(duì)R[s1]到R[t1]*/rectypeR[];ints1,t1;{inti;if(s1<t1) /*只有一個(gè)記錄或無(wú)記錄須排序*/

{i=partition(R,s1,t1); /*對(duì)R[s1]到R[t1]做劃分*/

quicksort(R,s1,i-1); /*遞歸處理左區(qū)間*/

quicksort(R,i+1,t1); /*遞歸處理右區(qū)間*/}}圖9-7展示了一次劃分的過(guò)程及整個(gè)快速排序的過(guò)程。圖中方括號(hào)表示無(wú)序區(qū)，方框表示基準(zhǔn)temp的關(guān)鍵字，它未參加真正的交換，只是在劃分完成時(shí)才將它放入正確的位置上。初始關(guān)鍵字 [[49]38659776132749`]

ijj向左掃描 [[49]38659776132749`]

ij第一次交換后 [273865977613[]49`]

iji向右掃描 [273865977613[]49`]

ij第二次交換后 [2738[]9776136549`]

ijj向左掃描，位置不變 第三次交換后 [2738139776[]6549]`]

i向左掃描，位置不變，ij第四次交換后 [273813[]76976549`]

ijj向左掃描 [273813[49]76976549`]

ij初始關(guān)鍵字：[4938659776132749`]一趟排序之后：[273813]49[76976549`]二趟排序之后：[13]27[38]49[49`65]76[97]三趟排序之后：1327384949`[65]7697最后的排序結(jié)果：1327387979`657697(b)各趟排序之后的狀態(tài)最壞情況是第次劃分選取的基準(zhǔn)都是當(dāng)前無(wú)序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?，劃分的基準(zhǔn)左邊的無(wú)序子區(qū)為空（或右邊的無(wú)序子區(qū)為空），而劃分所得的另一個(gè)非空的無(wú)序子區(qū)中記錄數(shù)目，僅僅比劃分前的無(wú)序區(qū)中記錄個(gè)數(shù)減少一個(gè)。因此，快速排序必須做n-1趟，每一趟中需進(jìn)行n-i次比較，故總手工藝比數(shù)次數(shù)達(dá)到最大值：

Cmax=∑(n-i)=n(n-1)/2=O(n2)顯然，如果按上面給出的劃分算法，每次取當(dāng)前無(wú)序區(qū)的第1個(gè)記錄為基準(zhǔn)，那么當(dāng)文件的記錄已按遞增序（或遞減序）排列時(shí)，每次劃分所取的基準(zhǔn)就是當(dāng)前無(wú)序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗洠瑒t快速排序所需的比較次數(shù)反而最多。在最好情況下，每次劃分所取的基準(zhǔn)都是當(dāng)前無(wú)序區(qū)的“中值”記錄，劃分的結(jié)果是基準(zhǔn)的左、右兩個(gè)無(wú)序子區(qū)的長(zhǎng)度大致相等地。設(shè)C（n）表示對(duì)長(zhǎng)度為n的文件進(jìn)行快速排序所需的比較次數(shù)，顯然，它應(yīng)該等于對(duì)長(zhǎng)度為n的無(wú)序區(qū)進(jìn)行劃分所需的比較次數(shù)n-1。加上遞歸地對(duì)劃分所得的左、右兩個(gè)無(wú)序子區(qū)（長(zhǎng)度≤n/2）進(jìn)行快速排序所需的比較總?cè)藬?shù)。假設(shè)文件長(zhǎng)度n=2k，那么總的比較次數(shù)為：C(n)≤n+2C(n/2)≤n+2[n/2+2C(n/22)]=2n+4C(n/22)≤2n+4[n/4+2C(n/23)]=3n+8C(n/23)≤……≤kn+2kC(n/2k)=nlog2n+nC(1)=O(nlog2n)注意：式中C（1）為一常數(shù)，k=log2n。，因?yàn)榭焖倥判虻挠涗浺苿?dòng)次數(shù)不大于比較的次數(shù)，所以，快速排序的最壞時(shí)間復(fù)雜度應(yīng)為O（n2），最好時(shí)間復(fù)雜雅興O(log2n)。為了改善最壞情況下的時(shí)間性能，可采用三者取中的規(guī)則，即在每一趟劃分開始前，首先比較R[1].key，R[h].key和R[[(1+h)/2]].key，令三者中取中值的記錄和R[1]交換之?？梢宰C明：快速排序的平均時(shí)間復(fù)雜度也是O(nlog2n)，它是目前基于比較的內(nèi)部排序方法中速度最快的，快速排序亦因此而得名?？焖倥判蛐枰粋€(gè)棧空間來(lái)實(shí)現(xiàn)遞歸。若每次劃分均能將文件均勻分割為兩部分，則棧的最大深度為[log2n]+1，所需棧空間為O（log2n）。最壞情況下，遞歸深度為n，所需?？臻g為O（n)?？焖倥判蚴遣环€(wěn)定的，請(qǐng)讀者自行檢驗(yàn)。

歸并排序

歸并排序(MergeSort)是利用“歸并”技術(shù)來(lái)進(jìn)行排序，所謂歸并是指將若干個(gè)已排序的子文件合并成一個(gè)有序的文件。簡(jiǎn)單的歸并是將兩個(gè)有序的子文件合并成一個(gè)有序的文件。假設(shè)R(low)到R[m]和R[m+1]到R[high]是存儲(chǔ)在同一個(gè)數(shù)組中且相鄰的兩個(gè)有序的子文件，要將它們合并為一個(gè)有序文件R1[low]到R1[high]，只要設(shè)置三個(gè)指示器i，j和k，其初值分別是這三個(gè)記錄區(qū)的起始位置。合并時(shí)依次比較R[i]和R[j]的關(guān)鍵字，取關(guān)鍵字較小的記錄復(fù)制到R1[k]中，然后，將指向被復(fù)制記錄的指示器加1和指向復(fù)制位置的指示器K加1，重復(fù)這一過(guò)程，直至全部記錄被復(fù)制到R1[low]到R1[high]中為止。

基數(shù)排序

前介紹的排序方法都是根據(jù)關(guān)鍵字值的大小來(lái)進(jìn)行排序的。本節(jié)介紹的方法是按組成關(guān)鍵字的各個(gè)位的值來(lái)實(shí)現(xiàn)的排序的，這種方法稱為基數(shù)排序（radixsort）。采用基數(shù)排序法需要使用一批桶（或箱子），故這種方法又稱為桶排序列。下面以十進(jìn)制數(shù)為例來(lái)說(shuō)明基數(shù)排充的過(guò)程。假定待排序文件中所有記錄的關(guān)鍵字為不超過(guò)d位的非負(fù)整數(shù)，從最高位到最低位（個(gè)位）的編號(hào)依次為1，2，…，d。設(shè)置10個(gè)隊(duì)列（即上面所說(shuō)的桶），它們的編號(hào)分別為0，1，2，…，9。當(dāng)?shù)谝槐閽呙栉淖謺r(shí)，將記錄按關(guān)鍵字的個(gè)位（即第d位）數(shù)分別放到相應(yīng)的隊(duì)列中：個(gè)位數(shù)為0的關(guān)鍵字，其記錄依次放入0號(hào)隊(duì)列中i個(gè)位數(shù)為1的關(guān)鍵字，其記錄放入1號(hào)隊(duì)列中…；個(gè)位數(shù)為9的關(guān)鍵字，其記錄放入9號(hào)隊(duì)列中。這一過(guò)程叫做按個(gè)位數(shù)分配?，F(xiàn)在把這10個(gè)隊(duì)列中的記錄，按0號(hào)，1號(hào)，9號(hào)隊(duì)列的順序收集和排列起來(lái)，同一隊(duì)列中的記錄按先進(jìn)先出的次序排列。這是第1遍。第2遍排序使用同樣的辦法，將第1遍排序后的記錄按其關(guān)鍵字的十位數(shù)（第d—1位）分配到相應(yīng)的隊(duì)列中，再把隊(duì)列中的記錄收集和排列起來(lái)。繼續(xù)進(jìn)行下去。第d遍排序時(shí)，按第d—1遍排序后記錄的關(guān)鍵字的最高位（第1位）進(jìn)行分配，再收集和排列各隊(duì)列中的記錄，醫(yī)得到了原文件的有序文件，這就是以10為基的關(guān)鍵字的基數(shù)排序法。例如，給出關(guān)鍵字序列（02，77，70，54，64，21，55，11，38，21），其中關(guān)鍵字02用1個(gè)0在2的前面補(bǔ)足到2位，余關(guān)鍵字均為2位的正整數(shù)。進(jìn)行基數(shù)排序的過(guò)程如圖9-9所示。在這個(gè)例子中，文件和所有的隊(duì)列都表示成向量（一維數(shù)組）。顯然，關(guān)鍵字的某一位有可能均為同一個(gè)數(shù)字（例如，個(gè)數(shù)都為0），這時(shí)所有的記錄都同時(shí)裝入同一個(gè)隊(duì)列中（例如，同時(shí)裝入0號(hào)隊(duì)列中）。因此，如果每個(gè)隊(duì)列的大小和文件大小相同，則需要一個(gè)10倍于文件大小的附加空間。此外，排序時(shí)需要進(jìn)行反復(fù)的分配和收集記錄。所以，采用順序表示是不方便的?；鶖?shù)排序所需的計(jì)算時(shí)間不僅與文件的大小n有關(guān)，而且還與關(guān)鍵字的位數(shù)、關(guān)鍵字的基有關(guān)。設(shè)關(guān)鍵字的基為r（十進(jìn)制數(shù)的基為10，二進(jìn)制數(shù)的基為2），為建立r個(gè)空隊(duì)列所需的時(shí)間為O（r）。把n個(gè)記錄分放到各個(gè)隊(duì)列中并重新收集起來(lái)所需的時(shí)間為O（n），因此一遍排序所需的時(shí)間為O（n+r）。若每個(gè)關(guān)鍵字有d位，則總共要進(jìn)行d遍排，所以基數(shù)排序的時(shí)間復(fù)雜度為O（d（n+r））。由于關(guān)鍵字的位數(shù)d直接與基數(shù)r以及最大關(guān)鍵字的值有關(guān)，因此不同的r和關(guān)鍵字將需要不同的時(shí)間。在已介紹的上述各種內(nèi)部排序方法中，就所需要的計(jì)算時(shí)間來(lái)看，快速排序、歸并排序、堆排序是很好的方法。但是，歸并排序需要大小為n的輔助空間，快速排序需要一個(gè)棧空。除了快速排序、堆排序、選擇排序不穩(wěn)定外，基它排序方法都是穩(wěn)定的。評(píng)價(jià)一個(gè)排序算法性能好壞的主要標(biāo)準(zhǔn)是它所需的計(jì)算時(shí)間和存儲(chǔ)空間。影響計(jì)算時(shí)間的兩個(gè)景要因素是比較關(guān)鍵字的次數(shù)和記錄的移動(dòng)次數(shù)。在實(shí)際應(yīng)用中，究竟應(yīng)該選用何種排序方法，取決于具體的應(yīng)用和機(jī)器條件。外部排序

外部排序基本上由兩個(gè)相對(duì)獨(dú)立的階段組成。首先，按可用內(nèi)存大小，將外存上含n個(gè)記錄的文件分成若干長(zhǎng)度為l的子文件或段（segment），依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對(duì)它們進(jìn)行排序，并將排序后得到的有序子文件重新寫入外存，通常稱這些有序子文件為歸并段或順串（run）；然后，對(duì)這些歸并段進(jìn)行逐趟歸并，使歸并段（有序的子文件）逐漸由小至大，直至得到整個(gè)有序文件為止。顯然，第一階段的工作是上一章已經(jīng)討論過(guò)的內(nèi)容。本章主要討論第二階段即歸并的過(guò)程。先從一個(gè)具體例子來(lái)看外排中的歸并是如何進(jìn)行的？假設(shè)有一個(gè)含10000個(gè)記錄的文件，首先通過(guò)10次內(nèi)部排序得到10個(gè)初始?xì)w并段R1~R10，其中每一段都含1000個(gè)記錄。然后對(duì)它們作如下圖所示的兩兩歸并，直至得到一個(gè)有序文件為止。將兩個(gè)有序段歸并成一個(gè)有序段的過(guò)程，若在內(nèi)存進(jìn)行，則很簡(jiǎn)單，上一章中的merge過(guò)程便可實(shí)現(xiàn)此歸并。但是，在外部排序中實(shí)現(xiàn)兩兩歸并時(shí)，不僅要調(diào)用merge過(guò)程，而且要進(jìn)行外存的讀/寫，這是由于我們不可能將兩個(gè)有序段及歸并結(jié)果段同時(shí)存放在內(nèi)存中的緣故。在11.1節(jié)中已經(jīng)提到，對(duì)外存上信息的讀/寫是以“物理塊”為單位的。假設(shè)在上例中每個(gè)物理塊可以容納200個(gè)記錄，則每一趟歸并需進(jìn)行50次“讀”和50次“寫”，四趟歸并加上內(nèi)部排序時(shí)所需進(jìn)行的讀/寫使得在外排中總共需進(jìn)行500次的讀/寫。一般情況下，外部排序所需總的時(shí)間=內(nèi)部排序（產(chǎn)生初始?xì)w并段）所需的時(shí)間

m*tIS+外部信息讀寫的時(shí)間