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

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

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

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

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

1.基本思想簡(jiǎn)單選擇排序又稱(chēng)直接選擇排序，是一種很簡(jiǎn)單的排序方法：首先在待排序序列的所有記錄中選出關(guān)鍵字最小的記錄，把它與第一個(gè)記錄互換；然后在其余的記錄中再選出關(guān)鍵字最小的記錄與第二個(gè)記錄互換；第i趟在后n-i+1(i=1,2,...,n-1）個(gè)記錄中選取鍵值最小的記錄與序列的第i個(gè)記錄互換；依此類(lèi)推，直至所有記錄排序完成。8.4選擇排序第8章排序?qū)W(xué)生記錄中的關(guān)鍵字序列（社會(huì)實(shí)踐成績(jī)）{11，10，16，13，2，10}進(jìn)行簡(jiǎn)單選擇排序，其過(guò)程如圖8-5所示。圖8-5簡(jiǎn)單選擇排序過(guò)程示意圖8.4選擇排序第8章排序2.算法實(shí)現(xiàn)簡(jiǎ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.性能分析對(duì)n個(gè)記錄序列進(jìn)行簡(jiǎn)單選擇排序，需進(jìn)行n-1趟排序，第i趟排序需進(jìn)行n-i-1次比較，每趟排序最多需要移動(dòng)3次記錄。所以總的比較次數(shù)為，記錄的最大移動(dòng)次數(shù)為3(n-1)。因此算法的時(shí)間復(fù)雜度為O(n2)。簡(jiǎn)單選擇排序的空間復(fù)雜度為O(1)。簡(jiǎn)單選擇排序會(huì)交換兩個(gè)不相鄰的記錄，所以是不穩(wěn)定的排序方法。8.4選擇排序第8章排序8.4.2堆排序

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