數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計（第二版）課件 第9章 排序

第九章排序西安科技大學(xué)計算機學(xué)院張小艷數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計排序簡單排序方法簡單選擇排序直接插入排序

希爾排序

起泡排序先進排序方法快速排序歸并排序堆排序多關(guān)鍵字排序方法基數(shù)排序（了解）排序方法的時間、空間復(fù)雜度、排序的穩(wěn)定性最好、最壞時間復(fù)雜度9.1排序的基礎(chǔ)知識9.1.1排序的基本概念

排序定義：將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列叫排序排序的目的：便于查找從第八章的討論可以看出，在有序表中，可以采用查找效率較高的折半查找。二叉排序樹或B樹建表的過程本身就是一個排序過程。

為了討論方便，下面給出排序確切的定義。假設(shè)含有n個記錄的序列為

{r1，r2，…，rn}(9-1)

它們的關(guān)鍵字相應(yīng)為{k1，k2，…，kn}。對式(9-1)的記錄序列進行排序就是要確定序號1，2，…，n的一種排列：

{p1，p2，…，pn}使其相應(yīng)的關(guān)鍵字滿足如下的非遞減(或非遞增)的關(guān)系：

kp1≤kp2≤…≤kpn(9-2)也就是使式(9-1)的記錄序列重新排列成一個按關(guān)鍵字有序的序列：

{rp1≤rp2≤…≤rpn}(9-3)

排序穩(wěn)定性：若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。排序不僅僅針對主關(guān)鍵字，也會對次關(guān)鍵字進行排序。當待排序記錄中的關(guān)鍵字ki(i?=?1，2，…，n)是主關(guān)鍵字，則任何一個記錄的無序序列經(jīng)排序后得到的結(jié)果是唯一的；反之，若待排序的記錄的關(guān)鍵字是次關(guān)鍵字，則排序所得到的記錄序列的結(jié)果不唯一。假設(shè)ki=kj?(1≤i≤n，1≤j≤n，i≠j)，且在排序前的序列中ri領(lǐng)先于rj?(即i<j)。若在排序后的序列中ri仍領(lǐng)先于rj，則稱所用的排序方法是穩(wěn)定的；反之，若使排序后的序列中rj領(lǐng)先于ri，則稱所用的排序方法是不穩(wěn)定的。9.1.2排序的分類按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過程中需對外存進行訪問的排序注：外部排序時，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果應(yīng)及時放入外存，顯然外部排序要復(fù)雜得多按排序依據(jù)原則插入排序：直接插入排序、折半插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排序：簡單選擇排序、堆排序歸并排序：2-路歸并排序基數(shù)排序

按排序算法的時間復(fù)雜度來區(qū)分，則可分為三類：簡單的排序方法，其時間復(fù)雜度為O(n2)；先進的排序方法，其時間復(fù)雜度為O(nlbn)；基數(shù)排序，其時間復(fù)雜度為O(d×n)。我們學(xué)習(xí)這些算法，并不是為了編程實現(xiàn)，而是通過學(xué)習(xí)來提高算法設(shè)計能力，以便能夠靈活運用基本的算法去解決更復(fù)雜的問題。對內(nèi)部排序來說，排序算法的性能主要考慮以下三個方面：

(1)時間性能。在排序過程中，一般進行兩種基本操作：①比較兩個關(guān)鍵字的大?。虎趯⒂涗洀囊粋€位置移動到另一個位置。其中操作①對于大多數(shù)排序方法來說是必要的，而操作②則可以通過采用適當?shù)拇鎯Ψ绞接枰员苊??？傊咝实膬?nèi)部排序算法應(yīng)該是具有盡可能少的關(guān)鍵字比較次數(shù)和盡可能少的記錄移動次數(shù)。(2)輔助空間。評價排序算法性能的另一個指標就是算法執(zhí)行過程中需要的輔助存儲空間。輔助存儲空間是除了存放待排序序列所占存儲空間之外，執(zhí)行算法所需的額外空間。

(3)算法的復(fù)雜度。這里是指算法本身的復(fù)雜度，而不是指算法的時間復(fù)雜度。9.1.3存儲結(jié)構(gòu)對于待排序的記錄序列，有三種常見的存儲表示方法：

(1)向量結(jié)構(gòu)：將待排序的記錄存放在一組地址連續(xù)的存儲單元中。由于在這種存儲方式中，記錄之間的次序關(guān)系由其存儲位置來決定，所以排序過程中一定要移動記錄才行。

(2)鏈表結(jié)構(gòu)：采用鏈表結(jié)構(gòu)時，記錄之間邏輯上的相鄰性是靠指針來維持的，這樣在排序時，就不用移動記錄元素，而只需要修改指針。這種排序方式被稱為鏈表排序。

(3)記錄向量與地址向量結(jié)合：將待排序記錄存放在一組地址連續(xù)的存儲單元中，同時另設(shè)一個指示各個記錄位置的地址向量。這樣在排序過程中不移動記錄本身，而修改地址向量中記錄的“地址”，排序結(jié)束后，再按照地址向量中的值調(diào)整記錄的存儲位置。這種排序方式被稱為地址排序。本章討論的排序算法大部分采用順序存儲。為了討論方便，假設(shè)待排記錄的關(guān)鍵字均為整數(shù)，均從數(shù)組中下標為1的位置開始存儲，下標為0的位置存儲監(jiān)視哨，或空閑不用。

#defineMAXSIZE20/*一個用作示例的小順序表的最大長度*/

typedefintKeyType;

typedefstruct

{

KeyTypekey;

OtherTypeotherdata;

}RecordType;

typedefstruct

{

RecordTyper[MAXSIZE];

intlength; /*順序表長度*/

}SqList; /*順序表類型*/9.2簡單排序方法

簡單選擇排序、直接插入排序、希爾排序和起泡排序。

9.2.1簡單選擇排序首先，在待排序序列中選擇出最小的記錄，然后將這個最小的數(shù)據(jù)元素與第一個記錄交換，第一個記錄到位，這叫做第一趟排序；第二趟，就是從第二個記錄到最后一個記錄中選擇最小的記錄，之后將最小的記錄與第二個記錄交換，第二個記錄到位；以此類推，進行n-1趟，序列就有序了。即第i趟簡單選擇，就是在n-i+1(i?=?1,2,…,n-1)個記錄中選擇關(guān)鍵字最小的記錄作為有序序列中第i個記錄。經(jīng)過n-1趟比較，直到數(shù)據(jù)表有序為止。例初始：[49386597761327]kjjjjjjkki=11349一趟：13[386597764927]i=2kkjjjjj2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：1327384965

76[97]排序結(jié)束：132738496576971voidSelectSort(SqList*L)2{/*對順序表L作簡單選擇排序*/3RecordTypetemp;4for(i=1;i<L->length;++i)5{/*選擇第i個小的記錄，并交換到位*/6j=i; /*j用于記錄最小元素的位置*/7for(k=i+1;k<=L->length;k++)8if(L->r[k].key<L->r[j].key)j=k;9if(i!=j)/*第i個小的記錄L->r[j]與第i個記錄交換*/10{temp=L->r[j];11L->r[j]=L->r[i];12L->r[i]=temp;13}14}15}/*SelectSort在第i趟選擇排序過程中，需進行n-i次關(guān)鍵字間的“比較”，至多3次“移動”記錄操作一個額外空間

在簡單選擇排序過程中，所需移動記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動記錄，但是記錄比較次數(shù)沒有變化。

(132738491492526576)

最壞情況下，即待排序記錄初始狀態(tài)是按逆序排列的，則需要移動記錄的次數(shù)最多為3(n-1)。簡單選擇排序過程中需要進行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無關(guān)。當i=1時，需進行n-1次比較；當i=2時，需進行n-2次比較；依此類推，共需要進行的比較次數(shù)是空間復(fù)雜度：S(n)=O(1)

初始關(guān)鍵字：

491386549276132752i=1(13)3865492764912752i=2(1327)6549276491

3852i=3(132738)49276491

6552i=4(132738492)764916552i=5(132738492491)

766552i=6(13273849249152)6576i=7(1327384924915265)

76穩(wěn)定性：不穩(wěn)定1.基本思想在一個已排好序的記錄子集的基礎(chǔ)上，每一步將下一個待排序的記錄有序地插入到已排好序的記錄子集中，直到將所有待排記錄全部插入為止。打撲克牌時的抓牌就是插入排序一個很好的例子，每抓一張牌，插入到合適位置，直到抓完牌為止，即可得到一個有序序列。9.2.2直接插入排序例如，已知待排序的一組記錄的初始排列為：

{491,38,65,492,76,13,27,52}

假設(shè)在排序過程中，前3個記錄按關(guān)鍵字遞增的次序重新排列，構(gòu)成了一個含有3個記錄的有序序列：

{38,491,65}

現(xiàn)在要將第四個記錄492插入上述序列，得到有序序列：

{38,491,492,65}。再講76插入到上述序列

{38,491,492,65,76}。

一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列r[1..i-1]中插入一個記錄r[i]

后，變成含有i個記錄的有序子序列r[1..i]。和順序查找類似，為了在查找插入位置的過程中避免下標出界，將r[i]

記入r[0]

中，將第i個記錄的關(guān)鍵字ki順次與其前面記錄的關(guān)鍵字ki-1,ki-2,…,k1進行比較，將所有關(guān)鍵字大于ki的記錄依次向后移動一個位置，直到遇見一個關(guān)鍵字小于或者等于ki的記錄kj，此時kj后面必為空位置，將第i個記錄插入空位置即可。關(guān)鍵字序列T=（21，25，49，25*，16，08），直接插入排序的具體實現(xiàn)過程。i=121254925*16080123456暫存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假設(shè)該序列已存入一維數(shù)組R[7]中，將R[0]作為緩沖或暫存單元（Temp）。則程序執(zhí)行過程為：21254925*21初態(tài)：164925*25211608完成!從上面的演示可以得到其具體算法

穩(wěn)定!1voidInsertSort(SqList*L)2{/*對順序表L作插入排序*/3for(i=2;i<=L->length;++i)4if(L->r[i].key<L->r[i-1].key)5{/*當“<”時，才需將L->r[i]插入有序表*/6L->r[0]=L->r[i];/*將待插入記錄復(fù)制為哨兵*/7j=i-1;8while(L->r[0].key<L->r[j].key)9{L->r[j+1]=L->r[j]; /*記錄后移*/10j--;11}12L->r[j+1]=L->r[0];/*插入到正確位置*/13}/*if*/14}/*InsertPass*/只需要一個輔助空間L->r[0]主要時間耗費在關(guān)鍵字比較和移動元素上

對于一趟插入排序，假如是第i趟插入排序，算法中的循環(huán)的次數(shù)主要取決于待插記錄與前i-1個記錄的關(guān)鍵字的關(guān)系上。最好情況為(順序)：L->r[i].key>L->r[i-1].key，關(guān)鍵字比較1次，且不移動記錄。{13,27,38,49,52,65,76}{(13),27,38,49,52,65,76}{(13,27),38,49,52,65,76}{(13,27,38),49,52,65,76}{(13,27,38,49),52,65,76}{(13,27,38,49,52),65,76}{(13,27,38,49,52,65),76}{(13,27,38,49,52,65,76)}

對于一趟插入排序，假如是第i趟插入排序，算法中的循環(huán)的次數(shù)主要取決于待插記錄與前i-1個記錄的關(guān)鍵字的關(guān)系上。最壞情況為(逆序)：L->r[i].key<L->r[i-1].key，

關(guān)鍵字比較i次，移動記錄的次數(shù)為i+1。{76,65,52,49,38,27,13}

對整個排序過程而言，最好情況是待排序記錄本身已按關(guān)鍵字有序排列，此時總的比較次數(shù)為n-1次，不移動記錄；最壞情況是待排序記錄按關(guān)鍵字逆序排列，此時總的比較次數(shù)達到最大值為記錄移動的次數(shù)也達到最大值

直接插入排序方法是穩(wěn)定的排序方法。在直接插入排序算法中，由于待插入元素的比較是從后向前進行的，循環(huán)while(L->r[0].key<L->.r[j].key)的判斷條件就保證了后面出現(xiàn)的關(guān)鍵字不可能插入到與前面相同的關(guān)鍵字之前。直接插入排序算法簡便，比較適用于待排序記錄數(shù)目較少且基本有序的情況。當待排序數(shù)目較大時，直接插入排序的性能就不好，為此我們可以對直接插入排序做進一步的改進。在直接插入排序法的基礎(chǔ)上，從減少“比較關(guān)鍵字”和“移動記錄”兩種操作的次數(shù)著手來進行改進。

折半插入排序直接插入排序的基本操作是向有序表中插入一個記錄，插入位置的確定是通過對有序表中記錄按關(guān)鍵字逐個比較得到的。既然是在有序表中確定插入位置，可以采用折半查找在有序表確定插入位置，即在有序表r[1..i-1]?中用折半查找確定第i個元素的插入位置。

在已形成的有序表中折半查找，并在適當位置插入，把原來位置上的元素向后順移。新元素插入到哪里？14364952805861123456781voidBinSort(RecordTyper[],intlength)2{3for(i=2;i<=length;++i)4{x=r[i];5low=1;high=i-1;6while(low<=high)/*確定插入位置*/7{mid=(low+high)/2;8if(x.key<r[mid].key)9high=mid-1;10else11low=mid+1;12}13for(j=i-1;j>=low;--j)14r[j+1]=r[j]; /*記錄依次向后移動*/15r[low]=x; /*插入記錄*/16}17}1436495280586112345678

采用折半插入排序法可減少關(guān)鍵字的比較次數(shù)。每插入一個元素，需要比較的次數(shù)最大為折半查找判定樹的深度，如插入第i個元素時，設(shè)i=2j，則需進行l(wèi)b?i次比較，因此插入n-1個元素的平均關(guān)鍵字的比較次數(shù)為O(nlbn)。雖然折半插入排序法與直接插入排序法相比較，改善了算法中比較次數(shù)的數(shù)量級，但其并未改變移動元素的時間耗費，所以折半插入排序的總的時間復(fù)雜度仍然是O(n2)。9.2.4起泡排序冒泡（起泡）排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點：每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。前提：順序存儲結(jié)構(gòu)例3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟132730第六趟4938659776132730初始關(guān)鍵字n=8384976971397279730971376767627301365276530651313494930492738273830381327第七趟最壞情況下每一趟起泡排序需進行n-i次比較，3i次移動。最好情況下，待排序列已有序，只進行一趟起泡排序，關(guān)鍵字需要n-1次比較，不需移動記錄。經(jīng)過n-1趟起泡排序后，總的比較次數(shù)為：總的移動次數(shù)為:3n(n-1)/2次在算法中設(shè)置一個交換標識change進行控制。1voidBubbleSort(SqList*L)2{/*對記錄數(shù)組L->r做起泡排序*/3RecordTypetemp;4n=L->length;5change=TRUE;/*設(shè)置交換標識為TRUE，便于進入循環(huán)*/6for(i=1;i<=n-1&&change;++i)7{change=FALSE; /*在第i趟中先設(shè)置記錄交換標識為FALSE*/8for(j=1;j<=n-i;++j)9if(L->r[j].key>L->r[j+1].key)/*若相鄰兩記錄逆序，交換*/10{temp=L->r[j];11L->r[j]=L->r[j+1];12L->r[j+1]=temp;13change=TRUE;14}15}16}/*BubbleSort*/算法的時間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)抓核心問題對內(nèi)部排序來說，排序算法的性能主要考慮以下三個方面：

(1)時間性能。在排序過程中，一般進行兩種基本操作：①比較兩個關(guān)鍵字的大小；②將記錄從一個位置移動到另一個位置。其中操作①對于大多數(shù)排序方法來說是必要的，而操作②則可以通過采用適當?shù)拇鎯Ψ绞接枰员苊狻？傊?，高效率的?nèi)部排序算法應(yīng)該是具有盡可能少的關(guān)鍵字比較次數(shù)和盡可能少的記錄移動次數(shù)。9.2.3希爾排序問題：直接插入排序的優(yōu)點？關(guān)鍵字序列T=（21，25，49，25*，16，08），直接插入排序的具體實現(xiàn)過程。假設(shè)該序列已存入一維數(shù)組R[7]中，將R[0]作為緩沖或暫存單元（Temp）。i=121254925*16080123456暫存21i=2i=3i=5i=4i=625252549494925*25*49161625*08084921254925*21初態(tài)：164925*25211608穩(wěn)定!在基本有序的情況下效率比較好!最好情況是有序時，僅僅進行N-1次比較

9.2.3希爾排序

基本思想：先將整個待排記錄序列分割成若干子序列,分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。技巧：子序列的構(gòu)成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。優(yōu)點：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。問題：直接插入排序的優(yōu)點？在基本有序的情況下效率比較好!最好情況是有序時，僅僅進行N-1次比較

表長比較短時，效率比較好

充分發(fā)揮直接插入排序的優(yōu)勢，引入希爾排序尺有所長,寸有所短38

關(guān)鍵字序列T=(49，38，65，97,76,13,27,49*，55,04)0123456789104938659776132749*5504初態(tài)：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*9755760427386549*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697r[i]算法分析：開始時dk的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，dk

值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。增量dk的設(shè)置是經(jīng)驗值站在巨人的肩上，打好基礎(chǔ)，才能創(chuàng)造未來希爾排序算法如下：1voidShellInsert(SqList*L,intdelta)2{/*對L->r[]做一趟希爾插入排序，delta為增量*/for(i=1+delta;i<=L->length;i++)

/*1+delta為第一個子序列的第二個元素的下標*/4if(L->r[i].key<L->r[i-delta].key)5{L->r[0]=L->r[i]; /*備份r[i]*/6for(j=i-delta;j>0&&L->r[0].key<L->r[j].key;j-=delta)7L->r[j+delta]=L->r[j];8L->r[j+delta]=L->r[0];9}10}delta為每趟排序的增量

希爾排序時效分析是一個復(fù)雜的問題，關(guān)鍵字的比較次數(shù)與記錄移動次數(shù)依賴于增量因子序列的選取，特定情況下可以準確估算出關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)。目前還沒有人給出最好的選取增量因子序列的方法。增量因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：最后一個增量因子必須為1。voidShellSort(SqList*L)

{for(i=0;i<t;++i)

ShellInsert(L，delta[i]);

}9.3先進排序方法9.3.1快速排序快速排序采用了一種分治的策略?；舅枷胧牵?/p>

(1)先從數(shù)列中取出一個數(shù)作為基準數(shù)(該記錄稱為樞軸)。

(2)將比基準數(shù)大的數(shù)全放到它的右邊，小于或等于基準數(shù)的全放到它的左邊。

(3)再對左右兩部分重復(fù)第(2)步，直到各區(qū)間只有一個數(shù)，達到整個序列有序。快速排序是從起泡排序改進而得的一種“交換”排序方法。通過一趟排序?qū)⒂涗浄指畛瑟毩⒌膬刹糠帧?/p>

快速排序最早是由圖靈獎獲得者Tony.Hoare于1962年提出的Tony.Hoare致力于編程語言的研究，對計算機科學(xué)做出了許多重要貢獻。Tony.Hoare領(lǐng)導(dǎo)團隊生產(chǎn)了ALGOL60編譯器，在編程語言ALGOL60的課程中，他發(fā)現(xiàn)遞歸的概念是快速排序清晰表達的關(guān)鍵。

假設(shè)待排序的原始記錄序列為

(Rs，Rs+1，…，Rt-1，Rt)

則一趟快速排序的基本操作是：任選一個記錄(通常選記錄Rs)，以它的關(guān)鍵字作為“樞軸”，凡序列中關(guān)鍵字小于樞軸的記錄均移動至該記錄之前；反之，凡序列中關(guān)鍵字大于樞軸的記錄均移動至該記錄之后.

(Ri1，Ri2，…，Rs,…,

Rit-1，Rit)……<=Rs.key<=…….分而治之的策略學(xué)會提煉核心問題，找到巧妙的解決方法stlowhigh設(shè)L.r[s]=52為樞軸high23lowhighlowL.r[0]52lowhighhighhighlow521)將L.r[high].key和樞軸的關(guān)鍵字進行比較，要求L.r[high].key≥樞軸的關(guān)鍵字否則與樞軸元素互換522)將L.r[low].key和樞軸的關(guān)鍵字進行比較，要求L.r[low].key≤樞軸的關(guān)鍵字否則與樞軸元素互換80521452可見：經(jīng)過“一次劃分”將關(guān)鍵字序列:

52,49,80,36,14,58,61,97,23,75調(diào)整為:23,49,14,36,(52)58,61,97,80,75

在調(diào)整過程中，設(shè)立了兩個指針：

low和high，它們的初值分別為：s和t

之后逐漸減小

high，增加

low，并保證

L.r[high].key≥52，和L.r[low].key≤52,

否則進行記錄的“交換”。一趟快速排序算法如下：1intPartition(RecordTypeR[],intlow,inthigh)2{R[0]=R[low];

/*將樞軸記錄移至數(shù)組的閑置分量*/3Pivotkey=R[low].key; /*樞軸記錄關(guān)鍵字*/4while(low<high) /*從表的兩端交替地向中間掃描*/5{while(low<high&&R[high].key>=pivotkey)/*從右向左掃描*/6--high;7R[low++]=R[high];

/*將比樞軸記錄小的記錄移到低端*/8while(low<high&&R[low].key<=pivotkey)/*從左向右掃描*/9++low;10R[high--]=R[low]; /*將比樞軸記錄大的記錄移到高端*/11}/*while12R[low]=R[0];

/*樞軸記錄移到正確位置*/13returnlow; /*返回樞軸位置*/14}/*Partition細節(jié)決定成?。。?！基礎(chǔ)?。。】焖倥判虻乃惴ㄈ缦拢?voidQSort(RecordTypeR[],ints,intt)2{/*對記錄序列R[s..t]進行快速排序*/3if(s<t-1)/*長度大于1*/4{pivotloc=Partition(R,s,t);5QSort(R,s,pivotloc-1);/*對低端子序列遞歸排序*/6QSort(R,pivotloc+1,t);/*對高端子序列遞歸排序*/7}//if8}//Qsort

樞軸元素通常選擇序列中的第一個元素，為了改善最壞情況下的時間性能，可以在樞軸的選擇上進行改變。一般來說，在序列R[s]～R[t]中，樞軸通?？蛇x：

(1)首元素R[s]或者尾元素R[t]。

(2)中值元素。這里，中值的意思是取首元素R[s]、尾元素R[t]和中間位置的元素三者中“中間大小”的那個元素。

(3)隨機元素R[i]，i是s～t之間的一個隨機整數(shù)。為了便于編程，如果選擇的樞軸元素不是首元素，則可以先將其與首元素交換，再進行劃分。所以，除增加選擇劃分元素的操作和交換操作外，算法沒有其他改變。用快速排序算法對數(shù)據(jù)表從小到大進行排序

A=(12,5,4,19,25,1,34,7,10,23,8,5)快速排序?qū)嵗?125419251347102385)x=12用快速排序算法對數(shù)據(jù)表從小到大進行排序

(1,4,5,7,10,12,19,25,34)快速排序?qū)嵗?1,4,5,7,10,12,19,25,34)x=1算法評價時間復(fù)雜度最好情況（每次總是選到中間值作樞軸,）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n2)空間復(fù)雜度：需?？臻g以實現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(logn)穩(wěn)定性：不穩(wěn)定9.3.2歸并排序?qū)蓚€或兩個以上的有序表組合成一個新的有序表.2-路歸并排序過程設(shè)初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列長度為1兩兩合并，得到

n/2個長度為2或1的有序子序列再兩兩合并，……如此重復(fù)，直至得到一個長度為n的有序序列為止算法評價時間復(fù)雜度：T(n)=O(nlogn)空間復(fù)雜度：S(n)=O(n)穩(wěn)定性:穩(wěn)定每一種排序算法都有其各自的優(yōu)勢！([15][18][25][60][18][75][100][23][64][8][150])([1518][2560][1875][23100][864][150])([15182560][182375100][864150])([1518

1823

256075100][864150])([81518

1823

25606475100150])二路歸并示例48將下屬兩個已排序的順序表合并成一個有序表：順序比較兩者的相應(yīng)元素，小者移入另一表中，反復(fù)如此，直至其中任一表都移入另一表為止。0123 44913659776780AB0123 4567Cijk490123 44913659776780AB0123 4567Cijk7500123 44913659776780AB0123 4567Cijk7510123 44913659776780AB0123 4567Cijk713520123 44913659776780AB0123 4567Cijk71349530123 44913659776780AB0123 4567Cijk71349540123 44913659776780AB0123 4567Cijk7134965550123 44913659776780AB0123 4567Cijk7134965560123 44913659776780AB0123 4567Cijk713496576570123 44913659776780AB0123 4567Cijk713496576580123 44913659776780AB0123 4567Cijk71349657680590123 44913659776780AB0123 4567Cijk71349657680600123 44913659776780AB0123 4567Cijk71349657680至此B表的元素都已移入C表，只需將A表的剩余部分移入C表即可。610123 44913659776780AB0123 4567Cijk71349657680至此B表的元素都已移入C表，只需將A表的剩余部分移入C表即可。97合并兩個有序序列的算法如下：1voidMerge(RecordTypeSR[],RcdTypeTR[],inti,intm,intn){/*將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]*/2for(j=m+1,k=i;k<=m&&j<=n;++k)/*將SR中記錄并入TR*/3{4if(SR[i].key<=SR[j].key)TR[k]=SR[i++];5elseTR[k]=SR[j++];6}7while(i<=m)TR[k++]=SR[i++];/*將剩余的SR[i..m]復(fù)制到TR*/8while(j<=n)TR[k++]=SR[j++];/*將剩余的SR[j..n]復(fù)制到TR*/}//Merge

基礎(chǔ)！??！

在待排序的原始記錄序列R[s..t]?中取一個中間位置(s+t)/2，先分別對子序列R[s..(s+t)/2]?和R[(s+t)/2+1..t]?進行歸并排序，然后調(diào)用合并算法實現(xiàn)整個序列R[s..t]?排序。10voidMsort(RecordTypeSR[],RecordTypeTR1[],ints,intt){/*對SR[s..t]進行歸并排序，排序后的記錄存入TR1[s..t]*/11RecordTypeTR2[t-s+1];/*開設(shè)存放歸并排序中間結(jié)果的輔助空間*/12if(s==t)TR1[s]=SR[s];13else14{m=(s+t)/2;/*將SR[s..t]平分為SR[s..m]和SR[m+1..t]*/15Msort(SR,TR2,s,m);/*遞歸地將SR[s..m]歸并為有序的TR2[s..m]*/16Msort(SR,TR2,m+1,t); /*將SR[m+1..t]歸并為有序的TR2[m+1..t]*/17Merge(TR2,TR1,s,m,t);/*將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]*/18}//else19}//Msort

非遞歸實現(xiàn)歸并排序遞歸合并排序盡管在代碼上比較清晰，容易理解，但這會造成時間和空間上的性能耗損，我們可以用非遞歸來實現(xiàn)合并排序。非遞歸過程可以從最小的序列開始歸并直至完成。1voidmergesort(SqList*L)2{3intTR[MAXL];4intk=1;5while(k<L->length)6{7mergepass(L->r,TR,k,L->length);/*合并到數(shù)組TR*/8k=2*k; /*子序列長度加倍*/9mergepass(TR,L->r,k,L->length);/*合并到數(shù)組L->r*/10k=2*k; /*子序列長度加倍*/11}12}合并兩個相鄰有序序列的算法如下：13voidmergepass(intSR[],intTR[],ints,intn)14{/*合并大小為s的相鄰子數(shù)組*/15inti=1,j;16while(i<=n-2*s+1)17{18Merge(SR,TR,i,i+s-1,i+2*s-1); /*兩相鄰有序序列合并*/19i=i+2*s;20}21if(i<n-s+1) /*歸并最后兩個序列*/22Merge(SR,TR,i,i+s-1,n);23else /*若最后只剩下單個子序列*/24for(intj=i;j<=n;j++)25TR[j]=SR[j];26}

遞歸合并排序中，一趟歸并需要將SR[1]～SR[n]?中相鄰的長度為h的有序序列兩兩歸并，并將結(jié)果放入TR[1]～TR[n]中，這需要將待排序序列中的記錄掃描一遍，耗時O(n)。具有n個記錄的序列進行歸并排序的遞歸的深度就是具有n結(jié)點完全二叉樹的深度，可以看出整個歸并排序需要進行l(wèi)bn次，因此，總的歸并排序的時間復(fù)雜度為O(nlbn)，而且，這是歸并排序算法最好、最壞、平均的時間復(fù)雜度。

由于歸并排序在歸并過程中需要與原始記錄序列同樣數(shù)量的存儲空間存放歸并結(jié)果以及遞歸時深度為lb?n的?？臻g，因此，空間復(fù)雜度為O(n+lbn)。

非遞歸的合并排序避免了遞歸時深度為lb?n的?？臻g，空間只是用到申請歸并臨時用的TR數(shù)組，因此，空間復(fù)雜度為O(n)。在時間上也有一定的提升，省去了遞歸拆分，但是總體時間復(fù)雜度還是O(nlbn)。應(yīng)該說，使用歸并排序時，盡量考慮非遞歸方法。9.3.3堆排序樹形選擇排序先把待排序的n個記錄的關(guān)鍵字兩兩進行比較，取出較小的，然后再在個較小的記錄中，采用同樣的方法進行比較，選出每兩個中較小的，如此反復(fù)，直到選出最小關(guān)鍵字記錄為止?？梢杂靡豢糜衝個結(jié)點的樹來表示，選出的最小記錄就是這棵樹的根結(jié)點。在輸出最小記錄后，為再次選出次小記錄，將根結(jié)點即最小記錄所對應(yīng)的葉子結(jié)點的關(guān)鍵字的值置為∞，再進行上述的過程，直到所有的記錄全部輸出為止。乒乓球比賽變換形式學(xué)會變通回憶：二叉樹性質(zhì)5

若對含n個結(jié)點的完全二叉樹從上到下且從左至右進行1

至n

的編號，則對完全二叉樹中任意一個編號為i

的結(jié)點：(1)若i=1，則該結(jié)點是二叉樹的根，無雙親，否則，編號為

i/2

的結(jié)點為其雙親結(jié)點；(2)若2i>n，則該結(jié)點無左孩子，

否則，編號為2i的結(jié)點為其左孩子結(jié)點；(3)若2i+1>n，則該結(jié)點無右孩子結(jié)點，

否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。2.堆排序(heapsort)（90,70,80,60,10,40,50,30,20）（10，20，70，30，50，90，80，60，40）觀察規(guī)律，提煉特點2.堆排序(heapsort)

堆排序是對樹形選擇排序的進一步改進。在堆排序中，把待排序的文件邏輯上看做是一棵完全二叉樹，并用到堆的概念。在介紹堆排序之前，先引入堆的概念：設(shè)有n個元素的序列k1，k2，…，kn，當且僅當滿足下述關(guān)系之一時，稱之為堆

若某數(shù)列是堆，則k1必是數(shù)列中的最小值或最大值，則分別稱滿足上式所示關(guān)系的序列為小頂堆或大頂堆。rir2i

r2i+1

若將該數(shù)列視作完全二叉樹，則r2i

是ri

的左孩子；r2i+1

是ri

的右孩子。1236276549817355403498例如:是堆14不

將此序列對應(yīng)到編號的完全二叉樹，則堆的定義可用完全二叉樹中的有關(guān)術(shù)語解釋為：每一結(jié)點均不大于(或不小于）其左右孩子結(jié)點的值。若序列(a1,a2,…,an)是堆，則堆頂(完全二叉樹的根)必為序列中的最小或最大值。將根最大的堆稱為大根堆，根最小的堆稱為小根堆.

是利用堆的特性對記錄序列進行排序的一種排序方法。堆排序（若進行增排序，則采用大根堆）如果初始序列是堆，則可通過反復(fù)執(zhí)行如下操作而最終得到一個有序序列：輸出根：即將根（第一個元素）與當前子序列中的最后一個元素交換。調(diào)整堆：將輸出根之后的子序列調(diào)整為堆。如果初始序列不是堆，則首先要將其先建成堆，然后再按（1）的方式來實現(xiàn)。

實現(xiàn)堆排序需解決兩個問題：①如何將n個元素的序列按關(guān)鍵字建成堆。②輸出堆頂元素后，怎樣調(diào)整剩余n-1個元素，使其按關(guān)鍵字成為一個新堆。首先，討論②，輸出堆頂元素后，對剩余元素重新建成堆的調(diào)整過程。例如：升序輸出13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13273849502765769713輸出：13276549502738769713輸出：1327384965502738769713輸出：1327387665502738499713輸出：132738495065762738499713輸出：132738499765762738495013輸出：13273849506597762738495013輸出：13273849509765762738495013輸出：1327384950657665972738495013輸出：1327384950659765762738495013輸出：132738495065769765762738495013輸出：1327384950657697調(diào)整剩余n-1個元素，使其按關(guān)鍵字成為一個新堆。假設(shè)r[k..m]?是以r[k]?為根的完全二叉樹，且分別以r[2k]?和r[2k+1]?為根的左、右子樹為小頂堆，調(diào)整r[k]，使整個序列r[k..m]?滿足堆的性質(zhì)。篩選如下：1voidsift(RecordTyper[],intk,intm)2{t=r[k]; /*暫存“根”記錄r[k]*/3x=r[k].key;4i=k;5j=2*i; /*左孩子結(jié)點*/6finished=FALSE;7while(j<=m&&!finished)8{if(j<m&&r[j].key>r[j+1].key)/*若存在右子樹，且右子樹根的關(guān)鍵字小，則沿右分支篩選*/9j=j+1; 10if(x<=r[j].key)11finished=TRUE; /*篩選完畢*/12else /*否則，r[j]計入r[i]，繼續(xù)篩選*/13{r[i]=r[j];14i=j;15j=2*i;16} /*繼續(xù)篩選*/17}18r[i]=t; /*r[k]填入到恰當?shù)奈恢?/19}/*sift*/

再來討論①的實現(xiàn)，即對n個元素初始建堆的過程。建堆方法：對初始序列建堆的過程，就是一個反復(fù)進行篩選的過程。若將n個結(jié)點序列看成一棵完全二叉樹，則最后一個結(jié)點是第n/2個結(jié)點的孩子結(jié)點。建堆算法如下：

voidcrt-heap(RecordTyper[],intlength)

/*對記錄數(shù)組r建堆，length為數(shù)組的長度*/{n=length;for(i=n/2;i>=1;--i)/*自第個記錄開始進行篩選建堆*/sift(r,i,n);}堆排序的算法如下：1voidHeapSort(RecordTyper[],intlength)/*對r[1..n]進行堆排序，執(zhí)行本算法后，r中記錄按關(guān)鍵字由大到小有序排列*/2{crt-heap(r,length);3n=length;4for(i=n;i>=2;--i)5{6b=r[1];/*將堆頂記錄和堆中的最后一個記錄互換*/7r[1]=r[i]8r[i]=b;9sift(r,1,i-1);/*進行調(diào)整，使r[1..i-1]變成堆*/10}11}/*HeapSort*/

堆排序的時間主要耗費在建初始堆和調(diào)整建新堆時進行的反復(fù)篩選上。在構(gòu)建堆的過程中，是從完全二叉樹最下層最右邊的非終端結(jié)點開始構(gòu)建，將它與其孩子進行比較和有必要的互換，對于每個非終端結(jié)點來說，其實最多進行兩次比較和互換操作，因此整個構(gòu)建堆的時間復(fù)雜度為O(n)。堆排序過程中，第i次取堆頂記錄后重新建堆的時間復(fù)雜度為O(lbi)，這是因為完全二叉樹的某個結(jié)點到根結(jié)點的距離為?

lb?i

+1，需要取n-1次堆頂記錄，因此重新建堆的時間復(fù)雜度為O(nlbn)。

堆排序在最壞情況下，其時間復(fù)雜度也為O(nlbn)，這是堆排序的最大優(yōu)點。堆排序與樹形排序相比較，排序中只需要存放一個記錄的輔助空間，因此也將堆排序稱做原地排序。

堆排序是一種不穩(wěn)定的排序方法。堆排序方法對記錄較少的文件并不值得提倡，但對n較大的文件還是很有效的。

排序方法有很多，希望大家能掌握每一種方法的特點，靈活運用例如：對52張撲克牌按以下次序排序：

2<3<……<A<

2<

3<……<

A<

2<

3<……<

A<2<3<……<A兩個關(guān)鍵字：花色（<

<

<）面值（2<3<……<A）并且“花色”地位高于“面值”9.3.4基數(shù)排序**

基數(shù)排序是一種借助于多關(guān)鍵字排序的思想，是將單關(guān)鍵字按基數(shù)分成“多關(guān)鍵字”進行排序的方法。1.多關(guān)鍵字排序

討論兩種排序方法。

方法1：先對花色排序，將其分為4個組，即梅花組、方塊組、紅心組、黑桃組。再對每個組分別按面值進行排序，最后，將4個組連接起來即可。

2345678910JQKA

方法2：先按13個面值給出13個編號組，將牌按面值依次放入對應(yīng)的編號組，分成13堆。再按花色給出4個編號組(梅花、方塊、紅心、黑桃)，將2號組中牌取出分別放入對應(yīng)花色組，再將3號組中牌取出分別放入對應(yīng)花色組……這樣，4個花色組中均按面值有序，然后，將4個花色組依次連接起來即可。2345678910JQKA22223333

K

KKKAAAA

一般情況下，設(shè)n個元素的待排序列{R1，R2，…，Rn}，且每個記錄包含d個關(guān)鍵字{k1，k2，…，kd}，則稱序列對關(guān)鍵字{k1，k2，…，kd}有序，即對于序列中任意兩個記錄R[i]和R[j](1≤i≤j≤n)都滿足下列有序關(guān)系：其中，k1稱為最主位關(guān)鍵字，kd稱為最次位關(guān)鍵字。多關(guān)鍵字排序按照從最高位關(guān)鍵字到最低位關(guān)鍵字或從最低位關(guān)鍵字到最高位關(guān)鍵字的順序逐次排序，分兩種方法：(1)最高位優(yōu)先(mostsignificantdigitfirst)法，簡稱MSD法(2)最低位優(yōu)先(leastsignificantdigitfirst)法，簡稱LSD法：2.鏈式基數(shù)排序?qū)㈥P(guān)鍵字抽象為數(shù)字，且其值都在0～999范圍內(nèi)，可把每一個十進制數(shù)字看成一個關(guān)鍵字，認為k由3個關(guān)鍵字(k2,k1,k0)組成，其中k2是百位數(shù)，k1是十位數(shù)，k0是個位數(shù)；又若關(guān)鍵字k是由5個字母組成的單詞，則可看成是由5個關(guān)鍵字(k4,k3,k2,k1,k0)組成，其中每個字母kj都是一個關(guān)鍵字，k0是最低位，k4是最高位。由于如此分解而得的每個關(guān)鍵字kj都在相同的取值范圍內(nèi)，靈活變通，轉(zhuǎn)變思路。

假設(shè)記錄的邏輯關(guān)鍵字由d個關(guān)鍵字構(gòu)成，每個關(guān)鍵字可能取RADIX個值，則只要從最低位關(guān)鍵字起，按關(guān)鍵字的不同值將記錄分配到RADIX個隊列之后再收集在一起，如此重復(fù)d趟，最終完成整個記錄序列的排序。按這種方法實現(xiàn)的排序稱為基數(shù)排序，其中，基數(shù)指的是RADIX的取值范圍。

以鏈表存儲n個待排記錄，從最低位關(guān)鍵字起，按關(guān)鍵字的不同值將序列中的記錄分配到RADIX個隊列中，然后再收集之，如此重復(fù)d次即可。鏈式基數(shù)排序是用RADIX個鏈隊列作為分配隊列，關(guān)鍵字相同的記錄存入同一個鏈隊列中，收集則是將各鏈隊列按關(guān)鍵字大小順序連接起來。27810906393058