數(shù)據(jù)結(jié)構(gòu)-第8章-排序

8.1排序的基本概念第8章排序排序(sorting)，簡單來講，是指把一組任意順序的數(shù)據(jù)序列重新排列成有序的序列。如某班的學(xué)生成績，如表8-1所示，其中的聲樂成績本為一組任意排列的數(shù)據(jù)（62，66，70，58，58，75），經(jīng)過一定的操作后得到一組有序的序列（58，58，62，66，70，75或75，70，66，62，58，58），此即為排序。所謂排序就是把序列中的記錄按關(guān)鍵字非遞減(或非遞增)的順序重新排列起來。假設(shè)含有n個記錄的序列為｛R1，R2，…，Rn｝，其相應(yīng)的關(guān)鍵字序列為｛K1，K2，…，Kn｝，對其進(jìn)行排序是指將這n個記錄按照K1，K2，…，Kn的大小順序來重新排列。對表8-1中的記錄而言，按照不同的科目來排序，可得到不同的有序序列。8.1排序的基本概念第8章排序內(nèi)部排序的方法有很多，按策略可以分為五類：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。這些排序方法各有優(yōu)缺點(diǎn)，用于不同的場合，很難概括的來講一種方法比另一種方法好，一定要根據(jù)待排序序列的初始狀態(tài)、具體要求來選擇合適的排序方法。通常評價排序方法好壞的標(biāo)準(zhǔn)主要有兩條：時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度主要是分析記錄關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)；空間復(fù)雜度為算法中使用的內(nèi)存輔助空間的多少。另外穩(wěn)定性也是評價排序性能的一方面。大多數(shù)排序算法都有兩個基本的操作：比較兩個關(guān)鍵字的大??；移動記錄。其中移動記錄的操作依賴于待排序記錄的存儲方式，不同的存儲方式，移動記錄操作的實(shí)現(xiàn)也不同。8.1排序的基本概念第8章排序待排序記錄的存儲結(jié)構(gòu)和移動記錄的實(shí)現(xiàn)方式主要有以下幾種：以順序表作為存儲結(jié)構(gòu)：對記錄本身進(jìn)行物理重排（將記錄移到合適的位置）。以鏈表作為存儲結(jié)構(gòu)：無需移動記錄，只要修改指針即可。用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關(guān)鍵字和指向記錄位置的指針組成的索引表)：這時只需對輔助表的表目進(jìn)行物理重排（即只移動輔助表的表目），而不移動記錄本身。適用于難于在鏈表上實(shí)現(xiàn)，仍需避免排序過程中移動記錄的排序方法。8.2插入排序第8章排序插入排序的基本思想是：將記錄分成兩部分，一部分是有序序列，第二部分是待排序序列；初始時有序序列僅有第一個記錄，依次將待排序序列中的記錄取出、并插入到有序序列中的合適位置，使插入后的序列仍保持有序，直至全部待排序記錄都插入到有序序列為止。常用的插入排序有直接插入排序和折半插入排序。8.2插入排序第8章排序8.2.1直接插入排序1．基本思想直接插入排序的基本操作是將一個記錄插入到一個長度為m(假設(shè))的有序序列中，使之仍保持有序，從而得到一個新的長度為m＋1的有序序列。假設(shè)待排序的記錄存放在順序表L[1..n]中，其中L[0]為哨兵。初始時，L[1]自成1個有序序列，L[2..n]為待排序序列。依次將L[i]（2≤i≤n）插入當(dāng)前的有序序列L[1..i-1]中，生成含n個記錄的有序序列。每個記錄的一次插入成為一趟直接插入排序。我們用8.1節(jié)中學(xué)生記錄的例子來說明直接插入排序的過程。其關(guān)鍵字序列（社會實(shí)踐成績）為{11，10，16，13，2，10}（用下劃線對兩個相同的關(guān)鍵字加以區(qū)分），按照上述思想，其直接插入排序的過程如圖8-1所示。其中[]中的序列為已排好序的部分。8.2插入排序第8章排序8.2插入排序第8章排序2．算法實(shí)現(xiàn)直接插入排序的實(shí)現(xiàn)算法如下：void InsertSort(SortItemL[],intn){ inti,j;for(i=2;i<=n;i++) /*共進(jìn)行n-1趟插入*/{L[0].key=L[i].key; /*L[0]為監(jiān)視哨兵，也可做下面for循環(huán)結(jié)束的標(biāo)志*/for(j=i–1;L[j].key>L[0].key;j--) /*移動記錄、定位插入位置*/ L[j+1].key=L[j].key;L[j+1].key=L[0].key; /*將L[0]即原L[i]記錄內(nèi)容，插到L[j]后一位置*/}}其中L為待排序的順序表，n為順序表中記錄的個數(shù)。8.2插入排序第8章排序3.性能分析算法的主要操作是比較關(guān)鍵字和移動記錄（定位插入位置），由兩個嵌套的for循環(huán)來實(shí)現(xiàn)。其中第一個for用于循環(huán)順序表中的每個記錄；對不同的順序表，定位插入位置時需要移動記錄的次數(shù)也不同。因此，算法的執(zhí)行時間同記錄的個數(shù)以及順序表中記錄的順序有關(guān)。以下分析在極端情況下的時間復(fù)雜度并就一般情況作出評價。（1）最好情況下的時間復(fù)雜度從算法可以看出，當(dāng)順序表中的記錄本身已經(jīng)是非遞減順序時：對每趟插入，只做一次比較（L[j].key>L[0].key不成立，退出循環(huán)）；定位插入位置時不需要移動記錄，只需對L[i]做兩次移動操作。因此對n-1趟插入操作，總的比較次數(shù)為n-1，移動記錄的次數(shù)為2(n-1)，所以算法的時間復(fù)雜度為O(n)。8.2插入排序第8章排序（2）最壞情況下的時間復(fù)雜度當(dāng)順序表中記錄為非遞增順序時：第i趟插入要做i-1次比較，定位第i（2≤i≤n）個記錄的插入位置需要移動記錄的次數(shù)為i-1+2。所以i-1趟插入的比較次數(shù)為，插入次數(shù)為，所以總的時間復(fù)雜度為O(n2)。（3）平均時間復(fù)雜度若順序表中記錄順序隨機(jī)，關(guān)鍵字之間的比較次數(shù)約為n2/4，即時間復(fù)雜度為O(n2)。從所需的附加存儲空間來看，直接插入排序只需一個監(jiān)視哨兵，所以其空間復(fù)雜度為O(1)。直接插入排序只涉及到相鄰兩個記錄之間的比較和移動位置，兩個關(guān)鍵字相同的記錄比較時不會交換位置，所以直接插入排序是穩(wěn)定的。 8.3交換排序第8章排序8.3.1冒泡順序1.基本思想冒泡排序是一種簡單的排序方法，關(guān)鍵字較小的記錄經(jīng)過與其他記錄的對比交換，一步步前移，其排序過程就像氣泡從水底逐漸往上冒一樣。假設(shè)有n個記錄的待排序序列存放在順序表L[1..n]中，首先將第n個記錄的關(guān)鍵字和第n-1個記錄的關(guān)鍵字相比較，如果為逆序（即L[n-1].key>L[n].key），則將兩個記錄相互交換，然后比較第n-1個記錄和第n個記錄的關(guān)鍵字。依次類推，直到第2個記錄的關(guān)鍵字和第1個記錄的關(guān)鍵字相比為止，這個過程稱作一趟冒泡排序，其結(jié)果使得關(guān)鍵字最小的記錄移到了最前面（存入L[1]中）。然后進(jìn)行第二趟排序，對后n-1個記錄進(jìn)行排序，其結(jié)果使得關(guān)鍵字次大的記錄交換到了L[2]中（后n-1個記錄的最前面）。8.3交換排序第8章排序第i趟排序是從第n個記錄開始，兩兩比較記錄的關(guān)鍵字，若為逆序則交換兩記錄的位置，直到比較第i+1個記錄和第i個記錄的關(guān)鍵字位置。第i趟排序的結(jié)果使得關(guān)鍵字第i小的記錄交換到了順序表的第i個位置上（后n-i+1個記錄的最前面）。整個排序過程需進(jìn)行n-1冒泡趟排序。如果在一趟排序過程中沒有交換記錄，則說明序列的關(guān)鍵字已經(jīng)有序，此時可以提前結(jié)束排序。8.3交換排序第8章排序同樣以8.1節(jié)中的學(xué)生記錄為例。對其關(guān)鍵字序列（社會實(shí)踐成績）{11，10，16，13，2，10}，圖8-2給出了每一趟冒泡排序的過程，其中[]中的序列為已排好序的部分。第四趟排序并沒有交換記錄，說明整個序列都已有序，可以提前結(jié)束排序。8.3交換排序第8章排序2.算法實(shí)現(xiàn)冒泡排序的實(shí)現(xiàn)算法如下：voidBubbleSort(SortItemL[],intn){ inti,j,isChange;for(i=1;i<n;i++) /*共進(jìn)行n-1趟冒泡*/{

isChange=0;

for(j=n;j>i;j--) /*對第i趟的后n-i+1個記錄排序*/if(L[j-1].key>L[j].key) /*如果逆序，交換記錄*/{L[0].key=L[j].key;

L[j].key=L[j-1].key;L[j-1].key=L[0].key; isChange=1; /*交換記錄的標(biāo)識置為1*/}

if(isChange==0) /*第i趟如果沒有交換記錄則退出循環(huán)*/

break;}}其中L為待排序的順序表，n為順序表中記錄的個數(shù)。8.3交換排序第8章排序3.性能分析從冒泡排序的算法可以看出若待排序的序列本身就是非遞減順序，則只需進(jìn)行一趟排序，這一趟排序中共進(jìn)行n-1次關(guān)鍵字的比較，并且不需要交換記錄。因此，最好情況下的時間復(fù)雜度為O(n)。若待排序的序列為逆序，則需進(jìn)行n-1趟排序，共需的比較次數(shù)為=(n2-n)/2，記錄的交換次數(shù)為

=3(n2-n)/2。則最壞情況下的時間復(fù)雜度為O(n2)。通常情況下，可以認(rèn)為冒泡排序的時間復(fù)雜度為O(n2)。整個序列越接近有序，需要的排序趟數(shù)越少。冒泡排序只在交換記錄時需要一個臨時記錄空間，所以其空間復(fù)雜度為O(1)。另外，冒泡排序是穩(wěn)定的排序方法。8.3交換排序第8章排序8.3.2快速排序 1.基本思想快速排序是一種基于分治法的排序方法。首先選取一個記錄（通常可選第一個記錄）作為樞軸，通過一趟排序?qū)⒋判蛴涗浄指畛蓛勺有蛄校渲袠休S左面記錄的關(guān)鍵字都不大于樞軸的關(guān)鍵字，樞軸右面記錄的關(guān)鍵字都不小于樞軸的關(guān)鍵字。對樞軸的左右兩個子序列遞歸實(shí)施這一過程，將待排序的序列劃分成更小的子序列，直至每個子序列只包含一個記錄為止。最終使得整個序列都有序。8.3交換排序第8章排序2.算法實(shí)現(xiàn)8.3交換排序第8章排序2.算法實(shí)現(xiàn)8.3交換排序第8章排序3.性能分析從快速排序的算法可以看出，記錄的移動次數(shù)通常小于記錄的比較次數(shù)，因此討論快速排序算法的時間復(fù)雜度只要按記錄的比較次數(shù)來討論即可。對長度為k的序列進(jìn)行一趟排序，需要的比較次數(shù)為k-1。最壞情況下，當(dāng)每次選取的樞軸都為其（子）序列中的最大（或最?。┯涗洉r，劃分出來的兩個子序列一個為空，另一個僅比原序列少一個樞軸記錄。此時對包含n個記錄的序列需要進(jìn)行n-1趟快速排序，第i趟快速排序的比較次數(shù)為n-i，則總的比較次數(shù)為。此時算法的時間復(fù)雜度為O(n2)。8.3交換排序第8章排序4.樞軸的選取對于隨機(jī)序列，選取第一個記錄作為樞軸是一種簡單有效的方法。但是若初始記錄序列按關(guān)鍵字有序或基本有序時，用第一個記錄作為樞軸，將會使大部分記錄都劃分到一個子區(qū)間中，快速排序?qū)⑼懟癁槊芭菖判?。另一種改進(jìn)的方法是依三者取中的原則來選取樞軸。即比較第一個、中間一個和最后一個記錄的關(guān)鍵字，取關(guān)鍵字居中的記錄作為樞軸。經(jīng)驗(yàn)證明，采用三者取中的規(guī)則可大大改善快速排序中最壞情況下的性能。8.4選擇排序第8章排序8.4.1簡單選擇排序

1.基本思想簡單選擇排序又稱直接選擇排序，是一種很簡單的排序方法：首先在待排序序列的所有記錄中選出關(guān)鍵字最小的記錄，把它與第一個記錄互換；然后在其余的記錄中再選出關(guān)鍵字最小的記錄與第二個記錄互換；第i趟在后n-i+1(i=1,2,...,n-1）個記錄中選取鍵值最小的記錄與序列的第i個記錄互換；依此類推，直至所有記錄排序完成。8.4選擇排序第8章排序?qū)W(xué)生記錄中的關(guān)鍵字序列（社會實(shí)踐成績）{11，10，16，13，2，10}進(jìn)行簡單選擇排序，其過程如圖8-5所示。圖8-5簡單選擇排序過程示意圖8.4選擇排序第8章排序2.算法實(shí)現(xiàn)簡單選擇排序的算法如下：voidSelectSort(SortItemL[],intn){inti,j,k;for(i=1;i<n;i++) /*需進(jìn)行n-1趟選擇和交換*/{

k=i; /*用k記錄當(dāng)前最小記錄的下標(biāo)*/

for(j=i+1;j<=n;j++) if(L[j].key<L[k].key) /*查到關(guān)鍵字更小的記錄*/k=j;

if(k!=i) /*L[i]和L[k]互換*/{L[0].key=L[i].key;L[i].key=L[k].key;L[k].key=L[0].key;}} }8.4選擇排序第8章排序3.性能分析對n個記錄序列進(jìn)行簡單選擇排序，需進(jìn)行n-1趟排序，第i趟排序需進(jìn)行n-i-1次比較，每趟排序最多需要移動3次記錄。所以總的比較次數(shù)為，記錄的最大移動次數(shù)為3(n-1)。因此算法的時間復(fù)雜度為O(n2)。簡單選擇排序的空間復(fù)雜度為O(1)。簡單選擇排序會交換兩個不相鄰的記錄，所以是不穩(wěn)定的排序方法。8.4選擇排序第8章排序8.4.2堆排序

1.算法描述堆排序的思想是：把待排序的序列存于順序表中，此時關(guān)鍵字序列不一定符合堆的條件。首先建成一個初始堆（大根堆），然后輸出堆頂記錄，讓堆中最后一個記錄上移到原堆頂位置，再恢復(fù)堆。重復(fù)輸出堆頂記錄、堆尾記錄上移、恢復(fù)堆的操作，直到堆中只有一個記錄為止。由于每次都是從當(dāng)前堆中輸出關(guān)鍵字最大的記錄，所以整個輸出過程就完成了對序列的排序。堆頂定義如下：n個記錄的序列{k1,k2,..ki,ki+1,..kn}，當(dāng)且僅當(dāng)其關(guān)鍵字滿足條件如下條件時，才稱之為堆。8.4選擇排序第8章排序堆排序的關(guān)鍵操作為：初始化堆，每趟排序時的輸出堆頂記錄和恢復(fù)堆。堆頂記錄是當(dāng)前堆中關(guān)鍵字最大的記錄，并且輸出的堆頂記錄，被依次從后往前存入順序表中，所以如果要對序列進(jìn)行非遞減排序，則需對原序列建立一個大根堆。（1）初始化堆設(shè)待排序的n個記錄存放在順序表L[1..n]中，L中的n個記錄可以對應(yīng)一棵完全二叉樹，但該完全二叉樹并不一定滿足大根堆的定義，因此要對完全二叉樹中的每個結(jié)點(diǎn)進(jìn)行調(diào)整。完全二叉樹中的葉子節(jié)點(diǎn)都滿足大根堆的定義，因此只需從最后一個非葉子結(jié)點(diǎn)（編號為n/2的結(jié)點(diǎn)）依次往前調(diào)整，直到調(diào)整到根結(jié)點(diǎn)。8.4選擇排序第8章排序（2）堆排序堆排序的過程就是循環(huán)輸出堆頂記錄（關(guān)鍵字最大的記錄）、并調(diào)整堆的過程，直到堆中僅有一個記錄。具體步驟如下：① 首先利用上述HeapAdjust算法將待排序的序列調(diào)整為一個初始堆。② 將堆頂記錄（L[1]）和堆尾記錄（L[n]）相互交換，即輸出堆頂記錄。輸出之后，堆中記錄的個數(shù)減一，即n=n-1，新的堆尾記錄的邏輯位置也前移一個位置。③ 交換后，新的堆頂記錄可能不符合大根堆的定義；而其它所有結(jié)點(diǎn)均滿足大根堆頂定義，因此只需對堆頂記錄調(diào)用HeapAdjust算法重新調(diào)整。④ 重復(fù)步驟②、③，直至堆中只有一個記錄位置。8.4選擇排序第8章排序2.性能分析8.4選擇排序第8章排序2.性能分析8.4選擇排序第8章排序2.性能分析8.4選擇排序第8章排序2.性能分析8.4選擇排序第8章排序2.性能分析8.5歸并排序第8章排序1.基本思想二路歸并排序的基本思路：（1）把待排序序列中的n個記錄看成n個長度length為1的有序子序列。（2）對這n個有序子序列進(jìn)行兩兩歸并使記錄關(guān)鍵字有序，得到n/2個長度為2*length或?yàn)閘ength（最后一個）的有序子序列。這一過程稱為一趟二路歸并。（3）重復(fù)步驟（2）直到所有待排序記錄歸并成一個長度為n的有序序列為止。8.5歸并排序第8章排序?qū)W(xué)生記錄中的關(guān)鍵字序列（社會實(shí)踐成績）{11，10，16，13，2，10}，二路歸并排序的過程如圖8-9所示。8.5歸并排序第8章排序2.算法實(shí)現(xiàn)（1）兩兩歸并假定待歸并的兩個有序子序列分別存于順序表L中下標(biāo)low到下標(biāo)mid的單元，和下標(biāo)mid+1到下標(biāo)up的單元，結(jié)果有序序列存于順序表R中從下標(biāo)low到下標(biāo)up的單元。8.5歸并排序第8章排序2.算法實(shí)現(xiàn)8.5歸并排序第8章排序（2）一趟二路歸并每一趟二路歸并排序都是依次從前往后將相鄰的兩個子序列進(jìn)行歸并，并且每個子序列的長度都相等，設(shè)為len（最后一個子序列長度可能小于len），歸并的結(jié)果存入順序表R中。則一趟排序的過程為：① 從第一個子序列的第一個記錄（i=