第四章排序12.1排序的基本概念所謂排序，就是整理文件中的記錄，將它們按照關鍵字值的遞增或遞減的順序排列起來。假定文件中含有n個記錄{R1,R2,…,Rn-}，它們的關鍵字值分別是k1,k2,…,kn，我們將這n個記錄重排為Ri1,Ri2,…,Rin，使得ki1≤ki2≤…≤kin（或ki1≥ki2≥…≥kin），這就是排序。12.1排序的基本概念每一種內部排序方法均可在不同的存儲結構上實現。通常，文件可有下列三種存儲結構：(1)以一維數組作為存儲結構，排序過程是對記錄本身進行物理重排，即通過比較和判定，把記錄移到合適的位置。(2)以鏈表作為存儲結構，排序過程中無須移動記錄，僅需修改指針即可，通常把這類排序稱為表排序。(3)有的排序方法難以在鏈表上實現，此時，若仍需要避免排序過程記錄的移動，可以為文件建立一個輔助表（如索引表），這樣，排序過程中只需對這個輔助的表目進行物理重排，而不移動記錄本身。12.2插入排序12.2.1直接插入排序直接插入排序是一種最簡單的排序方法。具體做法是在插入第i個記錄時，R1,R2,…,Ri-1已排好序，這時將關鍵字ki依次與關鍵字ki-1,ki-2,…,k1進行比較，從而找到應該插入的位置，然后將ki插入。12.2插入排序12.2.1直接插入排序圖12.1直接插入排序示例12.2插入排序12.2.1直接插入排序整個排序過程只有兩種運算，即比較關鍵字和移動記錄。算法中的外循環表示要進行n

1趟插入排序，內循環則表明每一趟排序所需進行的關鍵字的比較和記錄的后移。在文件正序（即關鍵字遞增有序）時，每趟排序的關鍵字比較次數為1，記錄移動次數是2次，即總的比較次數Cmin=n

1，總的移動次數Mmin=2(n

1)；當文件逆序時，關鍵字的比較次數和記錄移動次數均取最大值。對于要插入的第i個記錄，均要與前i

1個記錄及“監視哨”的關鍵字進行比較，即每趟要進行i次比較；從移動記錄的次數來說，每趟排序中除了上面提到的兩次移動外，還需將關鍵字大于R[i]的記錄后移一個位置。12.2插入排序12.2.1直接插入排序因此，總的比較次數和記錄的移動次數為：12.2插入排序12.2.2希爾排序希爾排序（Shell’smethod）又稱為“縮小增量排序”（DiminishingIncrementSort）。其基本思想是：先取一個小于n的整數d1并作為第一個增量，將文件的全部記錄分成d1個組，所有距離為d1倍數的記錄放在同一個組中，在各組內進行直接插入排序；然后取第二個增量d2<d1，重復上述的分組和排序，直至所取的增量dt=1(dt<dt

1<…<d2<d1)為止，此時，所有的記錄放在同一組中進行直接插入排序。12.2插入排序12.2.2希爾排序圖12.2希爾排序示例12.2插入排序12.2.2希爾排序希爾排序實質上還是一種插入排序，其主要特點是：每一趟以不同的增量進行排序。例如第一趟增量為5，第二趟增量為3，第三趟增量為1。在前兩趟的插入排序中，記錄的關鍵字是和同一組中的前一個關鍵字進行比較，由于此時增量取值較大，所以關鍵字較小的記錄在排序過程中就不是一步一步地向前移動，而是作跳躍式的移動。另外，由于開始時增量的取值較大，每組中記錄較少，故排序比較快，隨著增量值的逐步變小，每組中的記錄逐漸變多，但由于此時記錄已基本有序了，因次在進行最后一趟增量為1的插入排序時，只需作少量的比較和移動便可完成排序，從而提高了排序速度。12.3選擇排序選擇排序（SelectSort）的基本思想是：每一趟在待排序的記錄中選出關鍵字最小的記錄，依次放在已排序的記錄序列的最后，直至全部記錄排完為止。直接選擇排序和堆排序都歸屬于此類排序。本節主要介紹直接選擇排序。12.3選擇排序直接選擇排序的基本思想是：第一趟排序是在無序區R[0]～R[n

1]中選出最小的記錄，將它與R[0]交換；第二趟排序是在無序區R[1]～R[n

1]中選關鍵字最小的記錄，將它與R[1]交換；而第i趟排序時R[0]～R[i

2]已是有序區，在當前的無序區R[i

1]～R[n

1]中選出關鍵字最小的記錄R[k]，將它與無序區中第1個記錄R[i

1]交換，使R[1]～R[i

1]變為新的有序區。因為每趟排序都使有序區中增加了一個記錄，且有序區中的記錄關鍵字均不大于無序區中記錄的關鍵字，所以，進行n

1趟排序后，整個文件就是遞增有序的。其排序過程如圖12.3所示。12.3選擇排序圖12.3直接選擇排序示例12.4交換排序12.4.1起泡排序起泡排序（Bubblemethod）也是一種簡單的排序方法。它的基本思想是：通過對相鄰關鍵字的比較和交換，使全部記錄排列有序。起泡排序的過程是這樣的：將關鍵字按縱向排列，然后自下而上地對每兩個相鄰的關鍵字進行比較，若為逆序（即kj

1>kj），則將兩個記錄交換位置，這樣的操作反復進行，直至全部記錄都比較、交換完為止。如此一趟排序后，就將關鍵字最小的記錄安排在第一個記錄的位置上。然后，對后n

1個記錄重復同樣操作，再將次小關鍵字記錄安排在第二個記錄的位置上。重復上述過程，直至沒有記錄需要交換為止。至此，整個文件的記錄按關鍵字由小到大的順序排列完畢。由于在排序過程中，關鍵字小的記錄像氣泡一樣逐趟向上飄，而大的記錄則逐漸下沉，故形象的稱為“起泡排序”。起泡排序的過程如圖12.4所示。12.4交換排序12.4.1起泡排序圖12.4起泡排序示例12.4交換排序12.4.1起泡排序若文件按關鍵字遞增有序，則只需進行一趟排序，比較次數為n

1，記錄移動次數為0，即比較次數和記錄移動次數均為最小值；若文件按關鍵字遞減有序，則需進行n

1趟排序，比較次數和記錄移動次數均為最大值，分別為：12.4交換排序12.4.2快速排序在起泡排序中，比較和交換是在相鄰兩元素之間進行的，每次交換只能前移或后移一個位置，這樣總的比較和移動次數就會增多。快速排序是對起泡排序的一種改進。此時，比較和交換是從兩端向中間進行，關鍵字值較大的元素一次就能交換到后面的位置上，而關鍵字值較小的元素也能一次就交換到前面位置，即元素移動的距離較大。因此，總的比較和移動的次數就減少了。12.4交換排序12.4.2快速排序快速排序（QuickSort）的基本思想就是通過一趟排序將原有記錄分成兩部分，然后分別對這兩部分進行排序以達到最后所有記錄有序。即在當前工作無序區R[1]～R[h]中任取一個記錄作為比較的“基準”（不妨記為temp），用此基準將當前無序區劃分為左右兩個較小的無序子區：R[1]～R[i

1]和R[i+1]～R[h]，且左邊的無序子區記錄的關鍵字均小于或等于基準temp的關鍵字，右邊的無序子區中記錄的關鍵字均大于或等于基準temp的關鍵字，而基準則位于最終排序的位置上，即：R[1]～R[i

1].key≤temp.key≤R[i+1]～R[h].key(1≤i≤h)當R[1]～R[i

1]和R[i+1]～R[h]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區中記錄均已排好序為止。12.4交換排序12.4.2快速排序要完成對當前無序區R[1]～R[h]的劃分，具體做法是：可設置兩個指針i和j，它們的初值分別為i=1和j=h。設基準為無序區中的第一個記錄R[i]（即R[1]），并將它保存在變量temp中。令j自h起向左掃描，直到找到第一個關鍵字小于temp.key的記錄R[j]，將R[j]移至i所指的位置上（這相當于交換了R[j]和基準R[i](即temp)的位置，使關鍵字小于基準關鍵字的記錄移到了基準的左邊）；然后，令i自i+1起向右掃描，直至找到第一個關鍵字大于temp.key的記錄R[i]，將R[i]移至j指的位置上（這相當于交換了R[i]和基準R[j](即temp)的位置，使關鍵字大于基準關鍵字的記錄移到了基準的右邊）；接著令j自j

1起向左掃描，如此交替改變掃描方向，從兩端各自往中間靠攏，直至i=j時，i便是基準x的最終位置，將x放在此位置上就完成了一次劃分。12.4交換排序12.4交換排序圖12.5展示了一次劃分的過程及整個快速排序的過程。一般來說，快速排序有非常好的時間復雜度，它優于各種排序算法。可以證明，對n個記錄進行快速排序的平均時間復雜度為O(nlog2n)。但是，當待排序文件的記錄已按關鍵字有序或基本有序時，情況反而惡化了，原因是在第一趟快速排序中，經過n

1次比較之后，將第一個記錄仍定位在它原來的位置上，并得到一個包括n

1個記錄的子文件；第二次遞歸調用，經過n

2次比較，將第二個記錄仍定位在它原來的位置上，從而得到一個包括n

2個記錄的子文件；依次類推，最后，得到總比較次數為：12.4交換排序這使快速排序蛻變為起泡排序，其時間復雜度為O(n2)。在這種情況下，通常采用“三者取中”的規則加以改進。即在進行一趟快速排序之前，對R[l].key、R[h].key和R[

(l+h)/2

].key進行比較，再將三者中取中值的記錄和R[l]交換，就可以改善快速排序在最壞情況下的性能。12.4交換排序在最好情況下，每次劃分所取的基準都是無序區的“中值”記錄，劃分的結果是基準的左、右兩個無序子區的長度大致相等。設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)=n(log2n)+nC(1)=O(nlog2n)12.4交換排序因為快速排序的記錄移動次數不大于比較的次數，所以，快速排序的最壞時間復雜度應為O(n2)，最好時間復雜度為O(nlog2n)。可以證明：快速排序的平均時間復雜度也是O(nlog2n)，它是目前基于比較的內部排序方法中速度最快的，因而稱為快速排序。12.5歸并排序歸并排序（MergeSort）是一種不同于前面已經介紹過的排序方法。“歸并”的含義是將兩個或兩個以上的有序表合成一個新的有序表。假設初始表含有n個記錄，則可看成是n個有序的子表，每個子表的長度為1，然后兩兩歸并，得到

n/2

個長度為2或1的有序子表，再兩兩歸并，如此重復，直至得到一個長度為n的有序子表為止，這種方法稱為“二路歸并排序”。12.5歸并排序圖12.6二路歸并排序示例12.5歸并排序12.5歸并排序人們之所以熱衷于研究多種排序方法，不僅是由于排序在計算機中所處的重要地位，而且還因為不同的方法各有其優缺點，可根據需要應用于不同的場合。選取排序方法時考慮的因素有：①待排序的記錄個數n；②記錄本身的大小；③關鍵字的分布情況；④對排序穩定性的要求；⑤語言工具的條件，輔助空間的大小等。依據這些因素，可得出以下幾點結論：(1)若待排序的一組記錄數目n較小（如n≤50）時，可采用插入排序和選擇排序。由于直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。12.5歸并排序(2)若n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。快速排序被認為是目前內部排序中是最好的方法，當待排序的關鍵字隨機分布時，快速排序的平均運行時間最短；然而堆排序只需一個