查找与排序课件

查找與排序

順序查找是一種最基本和最簡單的查找方法。它的思路是，從表中的第一個元素開始，將給定的值與表中逐個元素的關鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。對於表中記錄的關鍵字是無序的表，只能採用這種方法。描述順序查找的演算法見框圖8-1。其中n是表r的長度，k是要查的元素的關鍵字，i查到的元素的序號。

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

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

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

elseif(k>r[mid].key)low=mid+1; /*在後半區間查找*/

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

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

排序排序（sorting）是電腦程式設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個按關鍵字有序的序列。由於待排序的記錄數量不同，使得排序過程中涉及的記憶體不同，可將排序方法分為兩大類：一類是內部排序，指的是待排序記錄存放在電腦記憶體中進行的排序過程；另一類是外部排序，指的是待排序記錄的數量很大，以致記憶體一次不能容納全部記錄，在排序過程中對外存進行訪問的排序過程。插入排序

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

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

折半插入排序

線上性插入排序中，我們採用順序查找法來確定記錄的插入位置。由於（R1，R2，…，Ri-1）是有序子檔，我們可以採用折半查找法來確定R1的插入位置，這種排序稱為折半插入排序。其演算法可寫出如下：voidbinarysort(structnoder[n+1],intn)/*按關鍵字遞增的次序對記錄r[1],r[2],……,r[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];}}在上面的演算法中，每插入一個R1，平均比較次數為log2i。希爾排序

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

rectypetemp;intmaxint=32767； /*機器中最大整數*/

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

K=0；

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

For(i=h+di；i<n+d1；i++) /*R[h+d1]到R[n+d1-1]插入當前有序區*/{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*/讀者可能看出，當增量h=1時，SHELLSORT演算法與INSERTSORT基本一致。對希爾排序的分析提出了許多困難的數學問題，特別是如何選擇增量序列才能產生最好的排序效果，至今沒有得到解決。希爾本為最初提出取d1=┗n/2┛，di+1=┗di/2┛，dt=1，t=┗log2n┛。後來又有人提出其他選擇增量序列的方法，如di+1=┗(di-1)/3┛，dt=1，t=┗log3n-1┛；以及di+1=┗(di-1)/2┛，dt=1，t=┗log2n-1┛。為什麼希爾排序的時間性能優於直接插入排序呢？我們知道直接插入排序在檔初態為正序時所需要時間最少，實際上，當檔初基本有序時直接插入排序所需的比較和移動次數均較少。另一面，當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間複雜度O(n)和最壞時間複雜度O(n2)差別不大。在希爾排序時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由於已經按di-1作為距離排過序，使檔較近於有序狀態，所以新的國趟排序過程也較快。因此，希爾排序在較率上較直接接入排序有較大的改進。希爾排序是不穩定的。參見圖9-2的例子，該例中兩個相同關鍵字49在排序前後的相對次序發生了變化。選擇排序

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

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

i=j;/*今r[j]為根結點*/

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

elsej=m+1 /*根不小於它的任一孩子時，強迫退出while迴圈*/}r[i]:=x; /*將存放在x中的根結點放到r[i]中*/}

快速排序

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

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

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

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

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

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

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

quicksort(R,i+1,t1); /*遞歸處理右區間*/}}圖9-7展示了一次劃分的過程及整個快速排序的過程。圖中方括弧表示無序區，方框表示基準temp的關鍵字，它未參加真正的交換，只是在劃分完成時才將它放入正確的位置上。初始關鍵字 [[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初始關鍵字：[4938659776132749`]一趟排序之後：[273813]49[76976549`]二趟排序之後：[13]27[38]49[49`65]76[97]三趟排序之後：1327384949`[65]7697最後的排序結果：1327387979`657697(b)各趟排序之後的狀態最壞情況是第次劃分選取的基準都是當前無序區中關鍵字最小（或最大）的記錄，劃分的基準左邊的無序子區為空（或右邊的無序子區為空），而劃分所得的另一個非空的無序子區中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。因此，快速排序必須做n-1趟，每一趟中需進行n-i次比較，故總手工藝比數次數達到最大值：

Cmax=∑(n-i)=n(n-1)/2=O(n2)顯然，如果按上面給出的劃分演算法，每次取當前無序區的第1個記錄為基準，那麼當檔的記錄已按遞增序（或遞減序）排列時，每次劃分所取的基準就是當前無序區中關鍵字最小（或最大）的記錄，則快速排序所需的比較次數反而最多。在最好情況下，每次劃分所取的基準都是當前無序區的“中值”記錄，劃分的結果是基準的左、右兩個無序子區的長度大致相等地。設C（n）表示對長度為n的檔進行快速排序所需的比較次數，顯然，它應該等於對長度為n的無序區進行劃分所需的比較次數n-1。加上遞歸地對劃分所得的左、右兩個無序子區（長度≤n/2）進行快速排序所需的比較總人數。假設檔長度n=2k，那麼總的比較次數為：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）為一常數，k=log2n。，因為快速排序的記錄移動次數不大於比較的次數，所以，快速排序的最壞時間複雜度應為O（n2），最好時間複雜雅興O(log2n)。為了改善最壞情況下的時間性能，可採用三者取中的規則，即在每一趟劃分開始前，首先比較R[1].key，R[h].key和R[[(1+h)/2]].key，令三者中取中值的記錄和R[1]交換之。可以證明：快速排序的平均時間複雜度也是O(nlog2n)，它是目前基於比較的內部排序方法中速度最快的，快速排序亦因此而得名。快速排序需要一個棧空間來實現遞歸。若每次劃分均能將檔均勻分割為兩部分，則棧的最大深度為[log2n]+1，所需棧空間為O（log2n）。最壞情況下，遞歸深度為n，所需棧空間為O（n)。快速排序是不穩定的，請讀者自行檢驗。

歸併排序

歸併排序(MergeSort)是利用“歸併”技術來進行排序，所謂歸併是指將若干個已排序的子檔合併成一個有序的檔。簡單的歸併是將兩個有序的子檔合併成一個有序的檔。假設R(low)到R[m]和R[m+1]到R[high]是存儲在同一個數組中且相鄰的兩個有序的子檔，要將它們合併為一個有序文件R1[low]到R1[high]，只要設置三個指示器i，j和k，其初值分別是這三個記錄區的起始位置。合併時依次比較R[i]和R[j]的關鍵字，取關鍵字較小的記錄複製到R1[k]中，然後，將指向被複製記錄的指示器加1和指向複製位置的指示器K加1，重複這一過程，直至全部記錄被複製到R1[low]到R1[high]中為止。

基數排序

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

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

m*tIS+外部資訊讀寫的時間