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

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

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

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

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

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

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

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

2]已是有序區(qū)，在當(dāng)前的無序區(qū)R[i

1]～R[n

1]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)中第1個記錄R[i

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

1]變?yōu)樾碌挠行騾^(qū)。因為每趟排序都使有序區(qū)中增加了一個記錄，且有序區(qū)中的記錄關(guān)鍵字均不大于無序區(qū)中記錄的關(guān)鍵字，所以，進行n

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

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

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

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

1趟排序，比較次數(shù)和記錄移動次數(shù)均為最大值，分別為：12.4交換排序12.4.2快速排序在起泡排序中，比較和交換是在相鄰兩元素之間進行的，每次交換只能前移或后移一個位置，這樣總的比較和移動次數(shù)就會增多?？焖倥判蚴菍ζ鹋菖判虻囊环N改進。此時，比較和交換是從兩端向中間進行，關(guān)鍵字值較大的元素一次就能交換到后面的位置上，而關(guān)鍵字值較小的元素也能一次就交換到前面位置，即元素移動的距離較大。因此，總的比較和移動的次數(shù)就減少了。12.4交換排序12.4.2快速排序快速排序（QuickSort）的基本思想就是通過一趟排序?qū)⒃杏涗浄殖蓛刹糠郑缓蠓謩e對這兩部分進行排序以達到最后所有記錄有序。即在當(dāng)前工作無序區(qū)R[1]～R[h]中任取一個記錄作為比較的“基準”（不妨記為temp），用此基準將當(dāng)前無序區(qū)劃分為左右兩個較小的無序子區(qū)：R[1]～R[i

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

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

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

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

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

1個記錄的子文件；第二次遞歸調(diào)用，經(jīng)過n

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

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

(l+h)/2

].key進行比較，再將三者中取中值的記錄和R[l]交換，就可以改善快速排序在最壞情況下的性能。12.4交換排序在最好情況下，每次劃分所取的基準都是無序區(qū)的“中值”記錄，劃分的結(jié)果是基準的左、右兩個無序子區(qū)的長度大致相等。設(shè)C(n)表示對長度為n的文件進行快速排序所需的比較次數(shù)，顯然它應(yīng)該等于對長度為n的無序區(qū)進行劃分所需的比較次數(shù)n

1，加上遞歸地對劃分所得的左、右兩個無序子區(qū)（長度≤n/2）進行快速排序所需的比較次數(shù)。假設(shè)文件長度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)=n(log2n)+nC(1)=O(nlog2n)12.4交換排序因為快速排序的記錄移動次數(shù)不大于比較的次數(shù)，所以，快速排序的最壞時間復(fù)雜度應(yīng)為O(n2)，最好時間復(fù)雜度為O(nlog2n)?？梢宰C明：快速排序的平均時間復(fù)雜度也是O(nlog2n)，它是目前基于比較的內(nèi)部排序方法中速度最快的，因而稱為快速排序。12.5歸并排序歸并排序（MergeSort）是一種不同于前面已經(jīng)介紹過的排序方法。“歸并”的含義是將兩個或兩個以上的有序表合成一個新的有序表。假設(shè)初始表含有n個記錄，則可看成是n個有序的子表，每個子表的長度為1，然后兩兩歸并，得到

n/2

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