數(shù)據(jù)結(jié)構(gòu)十一章

1第十(一)章排序2※

教學內(nèi)容：

插入排序；交換排序(起泡排序,快速排序)；選擇排序(簡單選擇,堆)；歸并排序；基數(shù)排序；各種排序方法的特點并靈活應用；各種方法的排序過程；各種排序方法的時間復雜度分析※

教學難點：

各種排序方法的特點及時間復雜度的分析※

教學重點：

310.1概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種排序方法的綜合比較10.8 外部排序410.1概述一、排序的定義二、內(nèi)部排序和外部排序三、內(nèi)部排序方法的分類5一、什么是排序？排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將下列關(guān)鍵字序列52,49,80,36,14,58,61,23,97,75調(diào)整為14,23,36,49,52,58,61,75,80,976一般情況下，假設含n個記錄的序列為{R1,R2,…，Rn}其相應的關(guān)鍵字序列為

{K1,K2,…，Kn}這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系：

Kp1≤Kp2≤…≤Kpn按此固有關(guān)系將上式記錄序列重新排列為

{Rp1,Rp2,

…，Rpn}的操作稱作排序。7排序算法的穩(wěn)定性：

如果待排序的序列中，存在多個具有相同關(guān)鍵字的記錄，若經(jīng)過排序這些記錄的相對次序保持不變，則稱這種排序算法是穩(wěn)定的；經(jīng)過排序這些記錄的相對次序發(fā)生了改變，則稱這種排序算法是不穩(wěn)定的。8二、內(nèi)部排序和外部排序待排序記錄存放在計算機隨機存儲器(內(nèi)存）中進行的排序過程，為內(nèi)部排序；

若待排序記錄的數(shù)量很大，以至內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程，為外部排序。9三、內(nèi)部排序的方法內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程.經(jīng)過一趟排序有序序列區(qū)無序序列區(qū)有序序列區(qū)無序序列區(qū)10按排序過程中依據(jù)的不同原則插入排序交換排序選擇排序歸并排序基數(shù)排序按排序過程所需的工作量簡單的排序方法，其時間復雜度為O(n2)先進的排序方法，其時間復雜度為O(nlogn)基數(shù)排序，其時間復雜度為O(d.n)111.插入類

將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。122.交換類通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。133.選擇類從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。144.歸并類通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。5.其它方法15待排記錄的數(shù)據(jù)類型定義如下:#defineMAXSIZE1000

//待排順序表最大長度typedefintKeyType;

//關(guān)鍵字類型為整數(shù)類型typedefstruct{KeyTypekey;//關(guān)鍵字項

InfoTypeotherinfo;//其它數(shù)據(jù)項}RcdType;//記錄類型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]閑置

intlength;//順序表長度}SqList;//順序表類型16

10.2插入排序17一趟直接插入排序的基本思想：

把n個記錄的序列劃分為已排序部分和未排序部分，即在涉及第i個記錄Ri時,（R1,...,Ri-1）是已排好的有序部分，（Ri,Ri+1,...,Rn）屬于未排序部分。找出Ri在此有序序列中應插入的位置，將Ri插入。原位置上的記錄至Ri均順序后移一位。18有序序列R[1..i-1]R[i]無序序列R[i..n]有序序列R[1..i]無序序列R[i+1..n]19實現(xiàn)“一趟插入排序”可分三步進行：3．將R[i]插入(復制)到R[j+1]的位置上。2．將R[j+1..i-1]中的所有記錄均后移一個位置；1．在R[1..i-1]中查找R[i]的插入位置，

R[1..j].key

R[i].key<R[j+1..i-1].key；20直接插入排序（基于順序查找）表插入排序（基于鏈表存儲）不同的具體實現(xiàn)方法導致不同的算法描述折半插入排序（基于折半查找）希爾排序（基于逐趟縮小增量）21一、直接插入排序

利用“順序查找”實現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”算法的實現(xiàn)要點：22從R[i-1]起向前進行順序查找，監(jiān)視哨設置在R[0]；R[0]=R[i];//設置“哨兵”循環(huán)結(jié)束表明R[i]的插入位置為j+1R[0]jR[i]for(j=i-1;R[0].key<R[j].key;--j);

//從后往前找j=i-1插入位置23

對于在查找過程中找到的那些關(guān)鍵字不小于R[i].key的記錄，并在查找的同時實現(xiàn)記錄向后移動；for(j=i-1;R[0].key<R[j].key;--j);

R[j+1]=R[j]R[0]jR[i]j=i-1上述循環(huán)結(jié)束后可以直接進行“插入”插入位置24令i=2，3，…,n,實現(xiàn)整個序列的排序。for(i=2;i<=n;++i)

if(R[i].key<R[i-1].key)

{在

R[1..i-1]中查找R[i]的插入位置;

插入R[i];

}25直接插入排序示例

初始狀態(tài)[18]1210123016

第1趟（i=2）(12)[1218]10123016

第2趟（i=3）(10)[101218]

123016

第3趟（i=4）(12)[10121218]3016

第4趟（i=5）(30)[1012121830]16

第5趟（i=6）(16)[101212161830]待排序記錄序列為(18，12，10，12，30，16）簡單插入排序每一趟執(zhí)行后的序列狀態(tài):監(jiān)視哨26voidInsertionSort(SqList&L){

//對順序表L作直接插入排序

for(i=2;i<=L.length;++i)if(L.r[i].key<L.r[i-1].key){}//InsertSortL.r[0]=L.r[i];//復制為監(jiān)視哨for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];

//記錄后移L.r[j+1]=L.r[0];｝//插入到正確位置27對于直接插入排序：最好的情況“比較”的次數(shù)：最壞的情況“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：（關(guān)鍵字在記錄序列中遞增有序）：（關(guān)鍵字在記錄序列中遞減有序）：28對于直接插入排序：其時間復雜度為O(n2)適用于當待排序記錄的數(shù)量很小時

一般情況下，待排序記錄是隨機的，即待排序列中的記錄可能出現(xiàn)的各種排列的概率相同，則可取最小值和最大值的平均值，作為直接插入排序時所需進行關(guān)鍵字的比較次數(shù)和移動記錄的次數(shù)，約為n2／4.29

因為R[1..i-1]是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。二、折半插入排序30voidBiInsertionSort(SqList&L){

//對順序表L作折半插入排序}//BInsertSort在L.r[1..i-1]中折半查找插入位置(high+1)；for(i=2;i<=L.length;++i){}//forL.r[0]=L.r[i];

//將L.r[i]暫存到L.r[0]for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];

//記錄后移L.r[high+1]=L.r[0];

//插入31low=1;high=i-1;while

(low<=high)

{}m=(low+high)/2;//折半if

(L.r[0].key<L.r[m].key)

high=m-1;

//插入點在低半?yún)^(qū)else

low=m+1;

//插入點在高半?yún)^(qū)//在L.r[1..i-1]中折半查找插入位置(high+1)3214364952805861239775ilowhighmmlowlowmhigh14364952586180239775ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r33對于折半插入排序，其時間復雜度為O(n2)折半插入排序適用于當待排序記錄的數(shù)量很大時，可大幅度降低關(guān)鍵字的比較次數(shù)。34三、表插入排序

為了減少在排序過程中進行的“移動”記錄的操作，必須改變排序過程中采用的存儲結(jié)構(gòu)。利用靜態(tài)鏈表進行排序，并在排序完成之后，一次性地調(diào)整各個記錄相互之間的位置，即將每個記錄都調(diào)整到它們所應該在的位置上。35MAXINT4938659776132752

1

0-------

012345678初始狀態(tài)Key域Next域MAXINT4938659776132752

20

1------MAXINT49386597761327522

31

0-----MAXINT4938659776132752231

4

0----i=2i=3i=436MAXINT4938659776132752231

50

4

---012345678MAXINT4938659776132752

6315042--MAXINT4938659776132752631504

7

2-MAXINT49386597761327526

8150472

3i=5i=6i=7i=837voidLInsertionSort(ElemSL[]，intn){?

//對記錄序列SL[1..n]作表插入排序

SL[0].key=MAXINT;//0分量為表頭結(jié)點

SL[0].next=1;SL[1].next=0;

for(i=2;i<=n;++i)for(j=0,k=SL[0].next;SL[k].key<

SL[i].key

;j=k,k=SL[k].next);SL[j].next=i;SL[i].next=k;

//結(jié)點i插入在結(jié)點j和結(jié)點k之間}//LinsertionSort38算法中使用了三個指針：其中：p指示第i個記錄的當前位置

i指示第i個記錄應在的位置

q指示第i+1個記錄的當前位置如何在排序之后調(diào)整記錄序列？

表插入排序的結(jié)果求得一個有序鏈表，只能進行順序查找，不能進行隨機查找，必須對記錄進行重新排序，才能實現(xiàn)有序表的折半查找。39MAXINT4938659776132752681504723

012345678初始狀態(tài)Key域Next域MAXINT1338659776492752661504823MAXINT1327659776493852667504813MAXINT1327389776496552667704853i=1p=6q=7i=2p=7q=2i=3p=(2)p=7q=140MAXINT1327384976976552667764053012345678MAXINT1327384952976576667768054MAXINT1327384952659776667768704MAXINT1327384952657697667768780i=4p=(1)p=6q=8i=5p=8q=3i=6p=(3)p=7q=5i=7p=(5)p=8q=441voidArrange(ElemSL[],intn){p=SL[0].next;//p指示第一個記錄的當前位置

for(i=1;i<n;++i){

while(p<i)p=SL[p].next;//小于i的分量都已有序

q=SL[p].next;

//q指示尚未調(diào)整的表尾

if(p!=i){

SL[p]←→SL[i];

//交換記錄，使第i個記錄到位

SL[i].next=p;

//指向被移走的記錄

}

p=q;

//p指示尚未調(diào)整的表尾，

//為找第i+1個記錄作準備

}}//Arrange42

四、希爾排序(又稱縮小增量排序)

基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。

所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。即先將整個待排記錄序列分割成若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。

43具體做法為：將記錄序列分成若干子序列，分別對每個子序列進行插入排序。其中，d

稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為1。例如：將n個記錄分成d個子序列：

{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}44初始關(guān)鍵字49386597761327495504

49133827654997557604

二趟排序結(jié)果13044938274955659776設增量

d=5設增量

d=3設增量

d=1一趟排序結(jié)果13274955044938659776

13553876270465

494997三趟排序結(jié)果0413273849495565769745

從上述排序過程可見，希爾排序中子序列的構(gòu)成不是簡單地“逐段分割”，而是將相隔某個“增量”的記錄組成一個子序列。關(guān)鍵字較小的記錄不是一步一步地往前挪動，而是跳躍式地往前移，從而使得在進行最后一趟增量為1的插入排序時，序列已基本有序，只要作記錄的少量比較和移動即可完成排序，因而希爾排序的時間復雜度較直接插入排序低。它的時間是所取“增量”序列的函數(shù)。46voidShellInsert(SqList&L,intdk){//對順序表L作一趟增量為dk的希爾排序

for(i=dk+1;i<=n;++i)

if(L.r[i].key<L.r[i-dk].key)

{L.r[0]=L.r[i];//暫存在R[0]

for(j=i-dk;j>0&&(L.r[0].key<L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//記錄后移，查找插入位置

L.r[j+dk]=L.r[0];//插入

}//if}//ShellInsert47voidShellSort(SqList&L,intdlta[],intt){//對順序表L作希爾排序,其中dlta[0..t-1]存放增量序列，

//如5、3、2、1

for(k=0;k<t;++k)ShellInsert(L,dlta[k]);

//一趟增量為dlta[k]的插入排序}//ShellSort4810.3交換排序一、起泡排序二、一趟快速排序三、快速排序四、快速排序的時間分析49一、起泡排序基本思想：從R[1]開始，兩兩比較R[i]和R[i+1]的關(guān)鍵字的大小，若R[i].key>R[i+1].key,則交換R[i]和R[i+1]的位置。第一趟全部比較完畢后R[n]是序列中最大的記錄。再從R[1]開始兩兩比較R[i]和R[i+1](i=1,2,...,n-2)，若R[i].key>R[i+1].key則交換R[i]和R[i+1]的位置。第二趟全部比較完畢后R[n-1]是序列中次大記錄。如此反復，進行n-1趟冒泡排序后所有待排序的n個記錄序列按關(guān)鍵字有序。50

假設在排序過程中，記錄序列R[1..n]的狀態(tài)為：第i趟起泡排序無序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1無序序列R[1..n-i]有序序列R[n-i+1..n]比較相鄰記錄，將關(guān)鍵字最大的記錄交換到

n-i+1

的位置上51冒泡排序示例初始狀態(tài)[65977613274958]第1趟（j=1~6）[657613274958]97第2趟（j=1~5）[6513274958]7697第3趟（j=1~4）[13274958]657697第4趟（j=1~3）[132749]58657697第5趟（j=1~2）[1327]4958657697第6趟（j=1）[13]274958657697設待排記錄序列的關(guān)鍵字為(65,97,76,13,27,49,58)冒泡排序每一趟執(zhí)行后的序列狀態(tài)如下：52冒泡排序算法voidbubblesort(ElemR[],intn)

//對順序表R[1..n]作冒泡排序

{for(i=1;i<n;i++)for(j=1;j<=n-i;j++)if(R[j].key>R[j+1].key){Swap(R[j],R[j+1]);}//交換元素}53冒泡排序的改進

按前面給出的算法，對具有n個記錄的待排序序列要執(zhí)行n-1趟冒泡排序。從上例中我們發(fā)現(xiàn)，執(zhí)行到第3趟后記錄序列已經(jīng)有序，后面的3趟冒泡“空跑”——沒有發(fā)生交換。因此應該對算法加以改進：能“記住”每趟加工時是否發(fā)生了“交換”，若某一趟未發(fā)生“交換”，表示此時記錄序列已經(jīng)有序，應結(jié)束排序過程。54改進的冒泡排序算法voidbubblesort(ElemR[],intn)//改進的冒泡排序算法一

{i=n;flag=1;//flag=1表示發(fā)生了交換

while((i>1)&&flag)) {flag=0; for(j=1;j<i;j++) if(R[j].key>R[j+1].key) {Swap(R[j],R[j+1]);

flag=1;} i--;}}起泡排序的結(jié)束條件為，

最后一趟沒有進行“交換記錄”55例如:2553157989i=7i=613i=2冒泡排序的進一步改進

一般情況下，每經(jīng)過一趟“起泡”，“i減１”，但并不是每趟都如此。

進一步改進：“記住”本趟進行過交換的最后一個記錄的位置，那么，在下一趟起泡時，就可減少比較次數(shù)。56時間分析:最好的情況“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：需進行n-1趟起泡“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：n-1（關(guān)鍵字在記錄序列中順序有序）：只需進行一趟起泡57

目標：找一個記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動至該記錄之后。致使一趟排序之后，記錄的無序序列R[s..t]將分割成兩部分：R[s..i-1]和R[i+1..t]，且

R[j].key≤R[i].key≤R[j].key(s≤j≤i-1)

樞軸

(i+1≤j≤t)。二、一趟快速排序（一次劃分）58stlowhigh設R[s]=52為樞軸

將R[high].key和樞軸的關(guān)鍵字進行比較，要求R[high].key≥

樞軸的關(guān)鍵字

將R[low].key和樞軸的關(guān)鍵字進行比較，要求R[low].key≤

樞軸的關(guān)鍵字high23low80high14low52例如R[0]52lowhighhighhighlow59

可見，經(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)整過程中，設立了兩個指針：low

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

之后逐漸減小high，增加low，并保證

R[high].key≥52，和R[low].key≤52,否則進行記錄的“交換”。60intPartition(RedType&R[],intlow,inthigh){

//對R[low,..high]進行一趟快速排序

pivotkey=R[low].key;

while(low<high){

while(low<high&&

R[high].key>=pivotkey)

--high;

R[low]←→R[high];

while(low<high&&

R[low].key<=pivotkey)

++low;

R[low]←→R[high];

}

returnlow;

//返回樞軸所在位置}//Partition61intPartition(RedTypeR[],intlow,inthigh){

//一趟快速排序算法的改進}//Partition

R[0]=R[low];pivotkey=R[low].key;//樞軸

while(low<high){while(low<high&&R[high].key>=pivotkey)--high;R[low]=R[high];

//從右向左搜索while(low<high&&R[low].key<=pivotkey)++low;R[high]=R[low];}

//從左向右搜索R[low]=R[0];

returnlow;62三、快速排序

首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。無序的記錄序列無序記錄子序列(1)無序子序列(2)樞軸一次劃分分別進行快速排序63voidQSort(RedType&R[],ints,intt){

//對記錄序列R[s..t]進行快速排序

if(s<t){

//長度大于1

}}//QSortpivotloc=Partition(R,s,t);

//對R[s..t]進行一次劃分

QSort(R,s,pivotloc-1);

//對低子序列遞歸排序，pivotloc是樞軸位置

QSort(R,pivotloc+1,t);

//對高子序列遞歸排序64void

QuickSort(SqList&L){

//對順序表進行快速排序

QSort(L.r,1,L.length);}//QuickSort

第一次調(diào)用函數(shù)Qsort時，待排序記錄序列的上、下界分別為1和L.length。65四、快速排序的時間分析假設一次劃分所得樞軸位置i=k，則對n個記錄進行快排所需時間：其中Tpass(n)為對n個記錄進行一次劃分所需時間。

若待排序列中記錄的關(guān)鍵字是隨機分布的，則k

取1至n

中任意一值的可能性相同。T(n)=Tpass(n)+T(k-1)+T(n-k)66設Tavg(1)≤b則可得結(jié)果：結(jié)論:快速排序的時間復雜度為O(nlogn)由此可得快速排序所需時間的平均值為：67

若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時，快速排序?qū)⑼懟癁槠鹋菖判?，其時間復雜度為O(n2)。

為避免出現(xiàn)這種情況，需在進行一次劃分之前，進行“予處理”，即：

先對R(s).key,R(t).key和R[

(s+t)/2].key，進行相互比較，然后取關(guān)鍵字為

“三者之中”的記錄為樞軸記錄。6810.4選擇排序簡單選擇排序堆排序樹形選擇排序69一、簡單選擇排序基本思想：一趟簡單選擇排序的操作為：通過n-i次關(guān)鍵字間的比較，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i（1≤i≤n)個記錄交換之。對L.r[1..n]中記錄進行簡單選擇排序的算法為：令i從1至n-1,進行n-1趟選擇操作。70假設排序過程中，待排記錄序列的狀態(tài)為：有序序列R[1..i-1]無序序列R[i..n]

第i趟簡單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R[1..i]無序序列

R[i+1..n]71簡單選擇排序初始狀態(tài)[272431]

第1趟（i=1）1[72432]第2趟（i=2）12

[7432]

第3趟（i=3）122

[437]第4趟（i=4）1223

[47]

第5趟（i=5）12234

[7]待排序記錄序列的關(guān)鍵字序列為（2，7，2，4，3，1）簡單選擇排序每一趟執(zhí)行后的序列狀態(tài)：(j=6)(j=3)(j=6)(j=5)(j=5)72簡單選擇排序的算法描述如下：voidSelectSort(ElemR[],intn){

//對記錄序列R[1..n]作簡單選擇排序。

for(i=1;i<n;++i){

//選擇第i小的記錄，并交換到位

}}//SelectSortj=SelectMinKey(R,i);

//在R[i..n]中選擇關(guān)鍵字最小的記錄if(i!=j)R[i]←→R[j];

//與第i個記錄交換73時間性能分析

對n個記錄進行簡單選擇排序，所需進行的關(guān)鍵字間的比較次數(shù)總計為：

移動記錄的次數(shù)，最小值為0,

最大值為3(n-1)。其時間復雜度為O(n2)74二、樹形選擇排序

樹形選擇排序又稱錦標賽排序，是一種按照錦標賽的思想進行選擇排序的方法?；舅枷耄?/p>

首先對n個記錄的關(guān)鍵字進行兩兩比較，然后在其中n/2個較小者之間再進行兩兩比較，如此重復，直至選出最小關(guān)鍵字的記錄為止。75384965977613274938651327381313選出最小關(guān)鍵字13例：493865977613274913763849659776∞274938657627382727

將葉結(jié)點中的最小關(guān)鍵字(13)改為最大值，然后修改該葉子結(jié)點到根的路徑上各結(jié)點的關(guān)鍵字，則根結(jié)點的關(guān)鍵字即為次小關(guān)鍵字。由此選出次小關(guān)鍵字27。1327773849659776∞∞4938657649384938

同理，可依次選出從小到大的所有關(guān)鍵字。居第三的關(guān)鍵字為38。

……13273878樹形選擇排序的時間復雜度分析：

含n個葉子結(jié)點的完全二叉樹的深度為次，log2n+1log2nO(nlog2n)則在樹形選擇排序中，除了最小關(guān)鍵字之外，每選擇一個次小關(guān)鍵字僅需進行次比較，因此，樹形選擇排序的時間復雜度為。3849659776∞27493865762738272779三、堆排序堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小頂堆)(大頂堆)80rir2i

r2i+1

若將該數(shù)列{12,36,27,65,40,34,98,81,73,55,49}視作完全二叉樹，則r2i

是ri

的左孩子；r2i+1

是ri

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

堆排序即是利用堆的特性對記錄序列進行排序的一種排序方法。例如：建大頂堆{98,81,49,73,36,27,40,55,64,12}{12,81,49,73,36,27,40,55,64,98}交換98和12重新調(diào)整為大頂堆{81,73,49,64,36,27,40,55,12,98}{40,55,49,73,12,27,98,81,64,36}經(jīng)過篩選82①如何由一個無序序列“建堆”？實現(xiàn)堆排序需要解決兩個問題:②如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆？定義堆類型為:typedefSqListHeapType;

//堆采用順序表表示之83如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆？

假設在輸出堆頂元素之后，以堆中最后一個元素替代之，此時，根結(jié)點的左右子樹均為堆，則僅需自上至下進行調(diào)整即可。自堆頂至葉子的調(diào)整過程為“篩選”。84

所謂“篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點使整個二叉樹也成為一個堆。堆堆篩選

堆的完全二叉樹的特點：從樹中任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按關(guān)鍵字有序。8598814973556412362740例如:是大頂堆12但在98和12進行互換之后,它就不是堆了,因此，需要對它進行“篩選”。98128173641298比較比較86voidHeapAdjust(RcdType&R[],int

s,int

m){

//已知R[s..m]中記錄的關(guān)鍵字除R[s]之外均

//滿足堆的特征，本函數(shù)自上而下調(diào)整R[s]的

//關(guān)鍵字，使R[s..m]也成為一個大頂堆}//HeapAdjustrc=R[s];//暫存R[s]

for(j=2*s;j<=m;j*=2){//j初值指向左孩子自上而下的篩選過程;}R[s]=rc;//將調(diào)整前的堆頂記錄插入到s位置87if

(rc.key>=R[j].key)

break;

//再作“根”和“子樹根”之間的比較，

//若“>=”成立，則說明已找到rc的插

//入位置s，不需要繼續(xù)往下調(diào)整R[s]=R[j];s=j;

//否則記錄上移，尚需繼續(xù)往下調(diào)整if

(j<m

&&R[j].key<R[j+1].key)++j;

//左/右“子樹根”之間先進行相互比較

//令j指示關(guān)鍵字較大記錄的位置88voidHeapAdjust(RcdType&R[],int

s,int

m){

//大頂堆}//HeapAdjustrc=R[s];//暫存R[s]

for(j=2*s;j<=m;j*=2){//j初值指向左孩子

}R[s]=rc;//將調(diào)整前的堆頂記錄插入到s位置if

(j<m

&&R[j].key＜R[j+1].key)++j;if

(rc.key＞=R[j].key)

break;R[s]=R[j];s=j;89建堆是一個從下往上進行“篩選”的過程。40554973816436122798例如:排序之前的關(guān)鍵字序列為（建大頂堆）123681734998817355

現(xiàn)在，左/右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點，使整個二叉樹是個“堆”即可。9849406436122790TypedefSqListHeapType;

//堆采用順序表存儲表示VoidHeapSort(HeapType&H){//對順序表H進行堆排序

for(i=H.length/2;i>0;--i)

//把H.r[1..H.Length]建成大堆頂

HeapAdjust(H,i,H.length);for(i=H.length;i>1;--i){

H.r[1]←→H.r[i];

//將堆頂記錄和當前未經(jīng)排序子序列

//H.r[1..i]中最后一個記錄相互交換

HeapAdjust(H,1,i-1);

//將H.r[1..i-1]重新調(diào)整為大堆頂

}}91堆排序的時間復雜度分析：1.

對深度為k的堆，“篩選”所需進行的關(guān)鍵字比較的次數(shù)至多為；3.

調(diào)整“堆頂”n-1

次，總共進行的關(guān)鍵字比較的次數(shù)不超過

2(

log2(n-1)

+

log2(n-2)

+

…+log22)<2n(

log2n

)

因此，堆排序的時間復雜度為O(nlogn)。2.

對

n

個關(guān)鍵字，建成深度為h(=

log2n+1)的堆，

所需進行的關(guān)鍵字比較的次數(shù)至多4n；2(k-1)9210.5歸并排序

歸并排序的過程基于下列基本思想進行：將兩個或兩個以上的有序子序列“歸并”為一個有序序列。93在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。有序序列R[i..n]有序子序列R[i..m]有序子序列R[m+1..n]這個操作對順序表而言，是輕而易舉的。94voidMerge(RcdTypeSR[],RcdType&TR[],

inti,intm,intn){

//將有序的記錄序列SR[i..m]和SR[m+1..n]//歸并為有序的記錄序列TR[i..n]}//Mergefor(j=m+1,k=i;i<=m&&j<=n;++k)

{

//將SR中記錄由小到大地并入TR

if(SR[i].key<=SR[j].key)TR[k]=SR[i++];

elseTR[k]=SR[j++];

}

……

95if(i<=m)TR[k..n]=SR[i..m];

//將剩余的SR[i..m]復制到TRif(j<=n)TR[k..n]=SR[j..n];

//將剩余的SR[j..n]復制到TR962路歸并排序的思想：假設初始序列含有n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸并，…如此重復，直到得到一個長度為n的有序序列為止。972-路歸并排序的過程初始狀態(tài)[25][57][48][37][12][92][86]第１趟歸并[2557][3748][1292][86]第２趟歸并[2537

48

57][12

86

92]第３趟歸并[1225

37

48

57

86

92]待排記錄序列為(25,57,48,37,12,92,86)２－路歸并排序每一趟執(zhí)行后的序列狀態(tài):98void

Msort(RcdTypeSR[],RcdType&TR1[],ints,intt)

{

//將SR[s..t]歸并排序為TR1[s..t]

if(s==t)TR1[s]=SR[s];

else

{}}//Msort

……

99m=(s+t)/2;

//將SR[s..t]平分為SR[s..m]和SR[m+1..t]Msort(SR,TR2,s,m);

//遞歸地將SR[s..m]歸并為有序的TR2[s..m]Msort(SR,TR2,m+1,t);

//遞歸地SR[m+1..t]歸并為有序的TR2[m+1..t]Merge(TR2,TR1,s,m,t);

//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]100voidMergeSort(SqList&L){

//對順序表L作2-路歸并排序

MSort(L.r,L.r,1,L.length);}//MergeSort容易看出，每一趟歸并的時間復雜度為O(n)，總共需進行

log2n

趟。對n

個記錄進行歸并排序的時間復雜度為

Ο(nlogn)?？臻g復雜度為O(n)。101

基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來實現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法?；鶖?shù)排序不需要比較關(guān)鍵字。前面的排序方法通過關(guān)鍵字的比較和移動記錄兩種操作實現(xiàn)。多關(guān)鍵字的排序鏈式基數(shù)排序10.6基數(shù)排序102一、多關(guān)鍵字的排序

n

個記錄的序列{R1,R2,…，Rn}對關(guān)鍵字(Ki0,Ki1,…,Kid-1)有序是指：

其中:K0被稱為“最主”位關(guān)鍵字Kd-1被稱為“最次”位關(guān)鍵字

對于序列中任意兩個記錄Ri和Rj(1≤i<j≤n)都滿足下列(詞典)有序關(guān)系：

(Ki0,Ki1,

…,Kid-1)<(Kj0,Kj1,

…,Kjd-1)103

實現(xiàn)多關(guān)鍵字排序通常有兩種作法:最低位優(yōu)先LSD法最高位優(yōu)先MSD法104

先對K0進行排序，并按K0的不同值將記錄序列分成若干子序列(每個子序列中的記錄具有相同的K0)之后，分別對每一個子序列按K1進行排序，...…，依次類推，直至最后對最次位關(guān)鍵字排序完成為止。最高位優(yōu)先MSD法105

先對Kd-1進行排序，然后對Kd-2進行排序，依次類推，直至對最主位關(guān)鍵字K0排序完成為止。

排序過程中對每個關(guān)鍵字都是整個序列參加排序。最低位優(yōu)先LSD法注意：LSD法除最低位關(guān)鍵字之外的其他幾位關(guān)鍵字的排序必須用穩(wěn)定的排序方法106

例如:學生記錄含三個關(guān)鍵字:系別、班號和班內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。

無序序列對K2排序?qū)1排序?qū)0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18

1,2,152,1,202,3,183,1,203,2,30LSD的排序過程如下:107二、鏈式基數(shù)排序?qū)τ跀?shù)字型或字符型的單關(guān)鍵字，可以看成是由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用這種“分配-收集”的辦法進行排序，稱作基數(shù)排序法。108例如：對下列這組關(guān)鍵字

{209,386,768,185,247,606,230,834,539}

首先按其

“個位數(shù)”

取值分別為0,1,…,9“分配”成10組，之后按從0至9的順序?qū)⑺鼈?/p>

“收集”

在一起；{230,834,185,386,606,247,768,209,539}

然后按其

“十位數(shù)”

取值分別為0,1,…,9

“分配”

成10組，之后再按從0至9的順序?qū)⑺鼈?/p>

“收集”

在一起；{606,209,230,834,539,247,768,185,386}

最后按其“百位數(shù)”重復一遍上述操作。{185,209,230,247,386,539,606,768,834}109

在計算機上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應采用鏈表作存儲結(jié)構(gòu)，即鏈式基數(shù)排序，具體作法為：

１．待排序記錄以指針相鏈，構(gòu)成一個鏈表；

２．“分配”時，按當前“關(guān)鍵字位”取值，將記錄分配到不同的“鏈隊列”中，每個隊列中記錄的“關(guān)鍵字位”相同；

３．“收集”時，按當前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;

４．對每個關(guān)鍵字位均重復2)和3)兩步。110例如：p→369→367→167→239→237→138→230→139進行第一次分配(按個位數(shù)分配)進行第一次收集(將各隊列的頭尾指針相鏈)f[0]r[0]f[7]r[7]f[8]r[8]f[9]r[9]p→230→230←→367←→167→237→367→167→237→138→369→239→139→369←→239→139→138←0隊頭7隊頭8隊頭9隊頭0隊尾7隊尾8隊尾9隊尾111進行第二次分配(按十位數(shù)分配)p→230→237→138→239→139p→230→367→167→237→138→369→239→139f[3]r[3]f[6]r[6]→230←→237→138→239→139→367←→167→369→367→167→369進行第二次收集112

進行第三次收集之后便得到記錄的有序序列f[1]r[1]p→230→237→138→239→139→367→167→369進行第三次分配(按百位數(shù)分配)f[2]r[2]f[3]r[3]→138←→139→167→230←→237→239→367←→369p→138→139→167→230→237→239→367→369113

基數(shù)排序的時間復雜度為O(d(n+rd))其中：分配為O(n)

收集為O(rd)(rd為“基”)

d為“分配-收集”的趟數(shù)11410.7各種排序方法的綜合比較115一、時間性能1.平均的時間性能基數(shù)排序時間復雜度為O(nlogn)：快速排序、堆排序和歸并排序時間復雜度為O(n2)：直接插入排序、起泡排序和簡單選擇排序時間復雜度為O(n):直接插入、起泡、快速排序、簡單選擇、堆排序、歸并、基數(shù)1162.當待排記錄序列按關(guān)鍵字順序有序時3.

的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。直接插入排序和起泡排序能達到的時間復雜度，快速排序的時間性能蛻化為。O(n)O(n2)簡單選擇排序、堆排序和歸并排序117二、空間性能指的是排序過程中所需的輔助空間大小1.

所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和堆排序的空間復雜度為；2.

快速排序為，為遞歸程序執(zhí)行過程中，棧所需的輔助空間；O(1)3.

歸并排序所需輔助空間最多，其空間復雜度為;4.鏈式基數(shù)排序需附設隊列首尾指針，則空間復雜度為O(rd)。O(logn)O(n)118三、排序方法的穩(wěn)定性能

1.

穩(wěn)定的排序方法指的是，對于兩個關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。

2.當對多關(guān)鍵字的記錄序列進行LSD方法排序時，除最低位關(guān)鍵字外其他位關(guān)鍵字必須采用穩(wěn)定的排序方法。排序之前:{·····Ri(K)·····Rj(K)·····}排序之后:{·····Ri(K)Rj(K)··········}119例如：

排序前

(56,34,47,23,66,18,82,

47)若排序后得到結(jié)果

(18,23,34,47,47,56,66,82)則稱該排序方法是穩(wěn)定的;若排序后得到結(jié)果

(18,23,34,

47,47,56,66,82)則稱該排序方法是不穩(wěn)定的。1203.

對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。4.

是不穩(wěn)定的排序方法。例如:對{4,3,4,2}進行快速排序，得到{2,3,4,4}快速排序、直接選擇排序、堆排序和希爾排序121四、關(guān)于“排序方法的時間復雜度的下限”

本章討論的各種排序方法，除基數(shù)排序外，其它方法都是基于“比較關(guān)鍵字”進行排序的排序方法。

可以證明，這類排序法可能達到的最快的時間復雜度為O(nlogn)。

(基數(shù)排序不是基于“比較關(guān)鍵字”的排序方法，所以它不受這個限制。)12210.8 外部排序123一.問題的提出

１．待排序的記錄數(shù)量很大，不能一次裝入內(nèi)存，則無法利用前幾節(jié)討論的排序方法124

１．按可用內(nèi)存大小，利用內(nèi)部排序方法，構(gòu)造若干(記錄的)有序子序列，通常稱外存中這些記錄有序子序列為“歸并段”；二、外部排序的基本過程由相對獨立的兩個步驟組成：

２．通過“歸并”，逐步擴大(記錄的)有序子序列的長度，直至外存中整個記錄序列按關(guān)鍵字有序為止。125例如：假設有一個含10,000個記錄的磁盤文件，而當前所用的計算機一次只能對1000個記錄進行內(nèi)部排序，則首先利用內(nèi)部排序的方法得到10個初始歸并段，然后進行逐趟歸并。假設進行2

路歸并(即兩兩歸并)，則第一趟由10個歸并段得到5個歸并段；最后一趟歸并得到整個記錄的有序序列。第三趟由3個歸并段得到2個歸并段；第二趟由5個歸并段得到3個歸并段；126假設“數(shù)據(jù)塊”的大小為200，即每一次訪問外存可以讀/寫200個記錄。則對于10,000個記錄，處理一遍需訪問外存100次(讀和寫各50次)。分析上述外排過程中訪問外存(對外存進行讀/寫)的次數(shù)：127由此，對上述例子而言，1)求得10個初始歸并段需訪問外存100次；2)每進行一趟歸并需訪問外存100次；3)總計訪問外存100+4

100=500次。128

外排總的時間還應包括內(nèi)部排序所需時間和逐趟歸并時進行內(nèi)部歸并的時間，顯然，除去內(nèi)部排序的因素外，外部排序的時間取決于逐趟歸并所需進行的“趟數(shù)”。例如，若對上述例子采用5

路歸并，則只需進行2趟歸并，總的訪問外存的次數(shù)將壓縮到100+2

100=300次。129除去內(nèi)部排序的因素外，外部排序的時間取決于逐趟歸并所需進行的“趟數(shù)”。

一般情況下，假設待排記錄序列含m個初始歸并段，外排時采用

k

路歸并，則歸并趟數(shù)為

logkm

。顯然，隨之k的增大歸并的趟數(shù)將減少，外存讀寫