理學(xué)排序技術(shù)

第九章排序

排序的基本概念

三種簡(jiǎn)單排序方法

堆排序

快速排序

歸并排序(不做要求）

基數(shù)排序(不做要求）

什么是"排序"？簡(jiǎn)單說(shuō)，排序是將無(wú)序的記錄序列調(diào)整為有序記錄序列的一種操作。例如，將下列記錄序列

{5,4,8,3,1,5,6,2,9,7}

調(diào)整為序列

{1,2,3,4,5,5,6,7,8,9}

將一組雜亂無(wú)序的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)叫做排序(sort)。

本章討論的排序均為按非遞減順序排序，并假定要排序的記錄均已存儲(chǔ)在一個(gè)一維數(shù)組中。排序的基本概念對(duì)一批記錄的排序，應(yīng)該指定是根據(jù)記錄中哪個(gè)域的數(shù)據(jù)進(jìn)行排列。這個(gè)作為排序依據(jù)的數(shù)據(jù)域我們稱之為關(guān)鍵字(key)。大多數(shù)的排序方法數(shù)據(jù)是存儲(chǔ)在內(nèi)存中，并在內(nèi)存中加以處理的，這種排序方法叫內(nèi)部排序。如果在排序過(guò)程中，數(shù)據(jù)的主要部分存放在外存儲(chǔ)器中（如軟盤(pán)、硬盤(pán)、磁帶），借助內(nèi)存進(jìn)行內(nèi)、外存數(shù)據(jù)交換，逐步排列記錄之間的順序，則稱之為外部排序。一種排序方法，如果排序后具有相同關(guān)鍵字的記錄仍維持排序之前的相對(duì)次序，則稱之為穩(wěn)定的，否則稱為不穩(wěn)定的。9.1互換類排序

所謂互換排序是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。互換類排序方法有：

冒泡排序快速排序冒泡排序

首先，從表頭開(kāi)始往后掃描線性表，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個(gè)逆序。顯然，在掃描過(guò)程中，不斷地將兩相鄰元素中的大者往后移動(dòng)，最后就將線性表中的最大者換到了表的最后。

然后從后到前掃描剩下的線性表，同樣，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，后面的元素小于前面的元素，則將它們互換，這樣就又消去了一個(gè)逆序。顯然，在掃描過(guò)程中，不斷地將兩相鄰元素中的小者往前移動(dòng)，最后就將剩下線性表中的最小者換到了表的最前面。對(duì)剩下的線性表重復(fù)上述過(guò)程，直到剩下的線性表變空為止，此時(shí)的線性表已經(jīng)變?yōu)橛行颉Ｃ芭菖判蜻^(guò)程示意圖（從后往前）第一遍（從前往后）原序列：98結(jié)果：6476235119682476135196結(jié)果：8247613516824961371568249613715999999888888最后結(jié)果：第三遍（從前往后）結(jié)果：（從后往前）結(jié)果：第二遍（從前往后）766543211766543211766543211764652311764652311647623511對(duì)于有相同關(guān)鍵字記錄的情況，此算法是穩(wěn)定的。[算法9.1]冒泡排序輸入：無(wú)序序列P(1:n)輸出：有序序列P(1:n)

PROCEDUREBUBSORT（P，n）k=1;m=nWHILE(k<m)DO[子表未空]{j=m-1;m=0FORi=kTOjDO[從前往后掃描子表]IF(p(i)>p(i+1))THEN[發(fā)現(xiàn)逆序進(jìn)行交換]{d=p(i);p(i)=p(i+1);p(i+1)=d;m=i;}j=k+1;k=0FORi=mTOjBY-1DO[從后往前掃描子表]IF(p(i-1)>p(i))THEN[發(fā)現(xiàn)逆序進(jìn)行交換]{d=p(i);p(i)=p(i-1);p(i-1)=d;k=i;}}RETURN

m記住從前往后掃描中最后一次發(fā)生交換的位置，此位置之后肯定為有序的，因此往回掃描時(shí)只能從該處往前掃描即可。

k記住每次從后往前掃描時(shí)最后交換的位置冒泡排序算法的C語(yǔ)言描述：BUBSORT（ETP[]，intn）{intm,k,j,i;ETd;k=0;m=n-1;while(k<m)[子表未空]{j=m-1;m=0;for(i=k;i<=j;i++)[從前往后掃描子表]if(p[i]>p[i+1])[發(fā)現(xiàn)逆序進(jìn)行交換]{d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;}j=k+1;k=0for(i=m;i>=j;i--)[從后往前掃描子表]if(p[i-1]>p[i])[發(fā)現(xiàn)逆序進(jìn)行交換]{d=p[i];p[i]=p[i-1];p[i-1]=d;k=i;}}return;}冒泡排序的分析冒泡排序是一種最簡(jiǎn)單的互換類排序方法，它屬于穩(wěn)定的排序。

設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要經(jīng)過(guò)n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n-1)/2。但這個(gè)工作量不是必需的，一般要小于這個(gè)工作量快速排序

快速排序是由冒泡排序改進(jìn)而得到的，冒泡排序在掃描過(guò)程中只對(duì)相鄰兩個(gè)元素進(jìn)行比較，因此在互換兩個(gè)相鄰元素時(shí)只能消除一個(gè)逆序，而快速排序是通過(guò)一次交換而消除多個(gè)逆序?？焖倥判蛞彩且环N互換類排序，由于比冒泡排序速度快，因此稱為快速排序，又稱為分區(qū)交換排序，是目前內(nèi)部排序中速度較快的方法?？焖倥判虻乃枷?/p>

從線性表中選取一個(gè)元素，設(shè)為T(mén)。然后將線性表后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果就將線性表分成了兩部分（稱為兩個(gè)子表），T插入到其分界線的位置處。這個(gè)過(guò)程稱為線性表的分割。

通過(guò)線性表的一次分割，就以T為分界線，將線性表分成了前后兩個(gè)子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。對(duì)分割后的各子表再按上述原則進(jìn)行分割，一直做下去，直到所有子表為空為止，此時(shí)的線性表就變成了有序表。無(wú)序線性表分割T>=T<=T分割分割…………

快速排序的關(guān)鍵是對(duì)線性表的分割，以及對(duì)各分割出的子表再進(jìn)行分割快速排序的步驟

首先，在表的第一個(gè)、中間一個(gè)與最后一個(gè)元素中選取中項(xiàng)，設(shè)為P(k)，并將P(k)賦給T，再將表中的第一個(gè)元素移到P(k)的位置上。然后設(shè)置兩個(gè)指針i和j分別指向表的起始與最后的位置。反復(fù)作以下兩步：

(1)將j逐漸減小，并逐次比較P(j)與T，直到發(fā)現(xiàn)一個(gè)P(j)＜T為止，將P(j)移到P(i)的位置上。

(2)將i逐漸增大，并逐次比較P(i)與T，直到發(fā)現(xiàn)一個(gè)P(i)＞T為止，將P(i)移到P(j)的位置上。上述兩個(gè)操作交替進(jìn)行，直到指針i與j指向同一個(gè)位置（即i＝j(luò)）為止，此時(shí)將T移到P(i)的位置上?？焖倥判蚴纠蛄校?/p>

123456789101151731694286快速排序是不穩(wěn)定的，對(duì)于有相同關(guān)鍵字的記錄，排序以后次序可能會(huì)顛倒。[算法9.2]線性表的分割輸入：待分割的子表P(m:n)輸出：分割后的分界線位置iPROCEDURESPLIT（P,m,n,i）選取P(k)其中m≤k≤n[P(k)一般取第一項(xiàng)，中間項(xiàng)和最后一項(xiàng)的中間項(xiàng)]T=P(k);P(k)=P(m)i=m;j=nWHILE(i≠j)DO{WHILE(P(j)≥T）and(i<j)DOj=j-1IF(i<j)THEN{p(i)=p(j);i=i+1WHILE(p(i)≤T）and(i<j)DOi=i+1IF(i<j)THEN{p(j)=p(i);j=j-1}}}P(i)=TRETURN[算法9.3]快速排序的遞歸算法輸入：待排序的子表P(m:n)輸出：有序子表P(m:n)PROCEDUREQKSORT1（P,m,n）IF(n>m)THEN

[子表不空]{SPLIT（P,m,n,i);[分割]QKSORT1(P,m,i-1);[對(duì)前面子表進(jìn)行快速排序]QKSORT1(P,i+1,n);[對(duì)后面子表進(jìn)行快速排序]}RETURN快速排序的分析快速排序也是一種互換類排序方法，但它屬于不穩(wěn)定的排序。

設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，快速排序也需要n(n-1)/2次比較，但實(shí)際的排序效率要比冒泡排序高得多。

若系統(tǒng)不支持遞歸，則在快速排序過(guò)程中，隨著對(duì)各子表的不斷分割，劃分出的子表會(huì)越來(lái)越多，但一次只能對(duì)一個(gè)子表進(jìn)行再分割處理，因此需要將暫時(shí)不分割的子表保存起來(lái)，這可用一個(gè)棧來(lái)實(shí)現(xiàn)。9.2插入類排序

冒泡排序與快速排序本質(zhì)上都是通過(guò)數(shù)據(jù)元素的交換逐步消除線性表中的逆序，而插入類的排序方法是將無(wú)序表中的元素按照一定的算法插入到有序的線性表中，直到原始無(wú)序表中的所有元素全部插入完畢為止。插入類排序方法主要有：簡(jiǎn)單插入排序和希爾排序簡(jiǎn)單插入排序

在線性表中，只包含第1個(gè)元素的子表顯然可以是有序表，然后從線性表的第2個(gè)元素開(kāi)始直到最后一個(gè)元素，逐次將其中的每一個(gè)元素插入到前面已經(jīng)有序的子表中。插入思想：首先將第j個(gè)元素放到一個(gè)變量T中，然后從有序子表的最后一個(gè)元素（即線性表中的第j-1個(gè)元素）開(kāi)始，往前逐個(gè)與T進(jìn)行比較，將大于T的元素均依次向后移動(dòng)一個(gè)位置，直到發(fā)現(xiàn)一個(gè)元素不大于T為止，此時(shí)就將T（即原線性表中的第j個(gè)元素）插入到剛移出的空位置上，有序子表的長(zhǎng)度就變?yōu)閖了。簡(jiǎn)單插入排序6897654621168297654311682497653116824976531198766543211698765432116824967531168249617531682496137516824961375168249613715其中紅底黃字為當(dāng)前插入的元素，白底黑字為j指針的位置，即當(dāng)前要處理的元素對(duì)于有相同關(guān)鍵字記錄的情況，此算法是穩(wěn)定的。[算法9.5]簡(jiǎn)單插入排序輸入：待排序序列P(1:n)輸出：有序序列P(1:n)

PROCEDUREINSORT（P，n）FORj=2TOnDO{T=P(j)；k=j-1WHILE(k>0)and(P(k)>T)DO{P(k+1)=P(k);k=k-1}P(k+1)=T}RETURN簡(jiǎn)單插入排序算法的C語(yǔ)言描述：insort（ETP[]，intn）{intj,k;ETt;for(j=1;j<n;j++){t=p[j];k=j-1;while((k>=0)&&(p[k]>t)){p[k+1]=p[k];k=k-1;}p[k+1]=t;}return;}簡(jiǎn)單插入排序的分析簡(jiǎn)單插入排序是一種插入類排序方法，它屬于穩(wěn)定的排序。

在簡(jiǎn)單插入排序中，每一次比較后最多移掉一個(gè)逆序，因此，這種排序方法的效率與冒泡排序相同。在最壞情況下，簡(jiǎn)單插入排序需要n(n-1)/2次比較。希爾排序

將整個(gè)無(wú)序序列分割成若干小子序列分別進(jìn)行簡(jiǎn)單插入排序。子序列的分割方法如下：將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列。在排序過(guò)程中，逐次減小這個(gè)增量，最后當(dāng)h減到1時(shí)，進(jìn)行一次插入排序，排序就完成。

增量序列一般取ht＝n/2k(k＝1，2，…，[log2n])，其中n為待排序序列的長(zhǎng)度。在希爾排序過(guò)程中，雖然對(duì)于每一個(gè)子表采用的仍然是插入排序，但是在子表中每進(jìn)行一次比較就可能移去整個(gè)線性表中的多個(gè)逆序，從而改善整個(gè)排序過(guò)程的性能希爾排序示意圖7

19

24

13

31

8

82

18

44

63

5

297

18

24

13

5

8

82

19

44

63

31

297

5

8

13

18

24

63

19

29

82

31

44h=12/2=6h=12/4=3h=12/8=1最后結(jié)果5

7

8

13

18

19

24

29

31

44

63

821

2

3

4

5

6

7

8

9

10

1112[算法9.6]希爾排序輸入：待排序序列P(1:n)輸出：有序序列P(1:n)

PROCEDURESHLSORT（P，n）h=n/2WHILE(h>0)DO{FORj=h+1TOnDO{t=P(j);i=j-hWHILE(i>0)and(P(i)>t)DO{P(i+h)=P(i);i=i-h}P(i+h)=t}h=h/2}RETURN希爾排序是不穩(wěn)定的排序希爾排序算法的C語(yǔ)言描述：shlsort（ETP[]，intn）{inth,j,i;ETt;h=n/2;while(h>0){for(j=h;j<=n-1;j++){t=p[j];i=j-h;while((i>=0)&&(p[i]>t)){p[i+h]=p[i];i=i-h;}p[i+h]=t;}h=h/2;}return;}9.3選擇類排序選擇排序的基本思想是：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面，然后對(duì)剩下的子表采用同樣的方法，直到子表空為止。選擇類排序有簡(jiǎn)單選擇排序和堆排序，但都是不穩(wěn)定的排序簡(jiǎn)單選擇排序

簡(jiǎn)單選擇排序的作法是：第一趟掃描所有數(shù)據(jù)，選擇其中最小的一個(gè)與第一個(gè)數(shù)據(jù)互換；第二趟從第二個(gè)數(shù)據(jù)開(kāi)始向后掃描，選擇最小的與第二個(gè)數(shù)據(jù)互換；依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過(guò)程。簡(jiǎn)單選擇排序過(guò)程示意圖原序列8921564885161947第一遍選擇1621564885891947第二遍選擇1619564885892147第三遍選擇1619214885895647第四遍選擇1619214785895648第五遍選擇1619214748895685第六遍選擇1619214748568985第七遍選擇1619214748568589[算法9.7]簡(jiǎn)單選擇排序輸入：待排序序列P(1:n)輸出：有序序列P(1:n)

PROCEDURESELESORT（P，n）FORi=1TOn-1DO{k=iFORj=i+1TOnDOIFP(j)<P(k)THENk=jIF(k≠i)THEN{d=P(i);P(i)=P(k);P(k)=d}}RETURN簡(jiǎn)單選擇排序算法的C語(yǔ)言描述：insort（ETP[]，intn）{intj,k;ETd;for(i=0;i<=n-2;i++){k=i;for(j=i+1;j<=n-1;j++)if(p[j]<p[k])k=j;if(k!=i){d=p[i];p[i]=p[k];p[k]=d;}}return;}堆的定義：具有n個(gè)元素的序列(h1，h2，…，hn)，當(dāng)且僅當(dāng)滿足堆排序定義hi>=h2ihi>=h2i+1hi<=h2ihi<=h2i+1或(i＝1，2，…，n/2)時(shí)稱之為堆。

我們只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素(即第一個(gè)元素)必為最大項(xiàng)。堆排序（HeapSort）是利用二叉樹(shù)的一種排序方法。堆（Heap）是與二叉排序樹(shù)不同的一種二叉樹(shù)，它的定義為：一個(gè)完全二叉樹(shù)，它的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于原始數(shù)據(jù)的一個(gè)元素，且規(guī)定如果一個(gè)結(jié)點(diǎn)有兒子結(jié)點(diǎn)，此結(jié)點(diǎn)數(shù)據(jù)必須大于或等于其兒子結(jié)點(diǎn)數(shù)據(jù)。由于堆是完全二叉樹(shù)，采用將結(jié)點(diǎn)順序編號(hào)存入一維數(shù)組中的表示法比鏈接表示法節(jié)省存儲(chǔ)空間，也便于計(jì)算。堆排序?qū)儆谶x擇類的排序方法堆的示意圖（堆頂元素最大）序列（91，85，53，36，47，30，24，12）是一個(gè)堆，如圖：9185533647302412在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（用一維數(shù)組H(1:n)表示）中，假設(shè)結(jié)點(diǎn)H（m）的左右子樹(shù)均為堆，現(xiàn)要將H（m）為根結(jié)點(diǎn)的子樹(shù)也調(diào)整為堆，這就是調(diào)整建堆的過(guò)程。調(diào)整建堆示意圖

（ａ）（ｂ）（ｃ）479153853012243691475385301224369185534730122436調(diào)整建堆的過(guò)程總是將根結(jié)點(diǎn)值與左右子數(shù)的根結(jié)點(diǎn)值進(jìn)行比較，若不滿足堆的條件，則將左右子樹(shù)根結(jié)點(diǎn)值中的大者與根結(jié)點(diǎn)值交換，該過(guò)程一直到所有子樹(shù)均為堆為止。[算法9.8]調(diào)整建堆輸入：完全二叉樹(shù)數(shù)組H(1:n)。其中結(jié)點(diǎn)H(m)的左、右子樹(shù)均為堆。輸出：以H(m)為根結(jié)點(diǎn)的子樹(shù)為堆。PROCEDURESIFT（H，n，m）t=H(m);j=2mWHILE(j≤n)DO{IF(j<n)and(H(j)<H(j+1))THENj=j+1IF(t<H(j))THEN{H(m)=H(j);m=j;j=2m}elsej=n+1}H(m)=tRETURN完全二叉樹(shù)中的所有結(jié)點(diǎn)值是從根結(jié)點(diǎn)開(kāi)始一層一層地從左到右存儲(chǔ)在一維數(shù)組H中。而對(duì)于完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)來(lái)說(shuō)，結(jié)點(diǎn)k的左子樹(shù)根結(jié)點(diǎn)為2k，右子樹(shù)的根結(jié)點(diǎn)為2k+1。因此算法中沒(méi)有用到指針運(yùn)算，而只用到數(shù)組的下標(biāo)運(yùn)算。有了調(diào)整建堆的算法后，就可以將一個(gè)無(wú)序序列建成為堆。假設(shè)無(wú)序序列H(1:n)以完全二叉樹(shù)表示。從完全二叉樹(shù)的最后一個(gè)非葉子結(jié)點(diǎn)（即第n/2個(gè)元素）開(kāi)始，直到根結(jié)點(diǎn)（即第一個(gè)元素）為止，對(duì)每一個(gè)結(jié)點(diǎn)進(jìn)行調(diào)整建堆，最后就可以得到與該序列對(duì)應(yīng)的堆。堆排序(1)首先將一個(gè)無(wú)序序列建成堆。(2)然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換