數(shù)據(jù)結(jié)構(gòu)簡明教程（第3版）課件 第9章 排序(上)（下）

第9章排序9.1排序的基本概念9.2插入排序9.3交換排序9.4選擇排序9.5歸并排序9.6基數(shù)排序9.7外排序第9章

排序1/86所謂排序，是要整理表中的元素，使之按關(guān)鍵字遞增（遞減）有序排列。其確切定義如下：

輸入：n個元素，R0,R1,…,Rn-1,其相應(yīng)的關(guān)鍵字分別為k0,k1,…,kn-1。

輸出：Ri,0,Ri,1,…,Ri,n-1,使得ki,0≤ki,1≤…≤ki,n-1(或ki,0≥ki,1≥…≥ki,n-1)。本章僅考慮遞增排序9.1排序的基本概念1.什么是排序9.1排序的基本概念2/86在排序過程中，若整個表都是放在內(nèi)存中處理，排序時不涉及數(shù)據(jù)的內(nèi)、外存交換，則稱之為內(nèi)排序。若排序過程中要進行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外排序。2.內(nèi)排序和外排序9.1排序的基本概念3/863.內(nèi)排序的分類根據(jù)內(nèi)排序算法是否基于關(guān)鍵字的比較，將內(nèi)排序算法分為基于比較的排序算法和不基于比較的排序算法。像插入排序、交換排序、選擇排序和歸并排序都是基于比較的排序算法。而基數(shù)排序是不基于比較的排序算法。9.1排序的基本概念4/864.基于比較的排序算法的性能基于比較的排序算法中，主要進行以下兩種基本操作：這類排序算法的性能由算法的時間和空間確定的，而時間是由比較和移動的次數(shù)之和確定的，兩個元素的一次交換一般需要3次移動。比較：關(guān)鍵字之間的比較移動：元素從一個位置移動到另一個位置9.1排序的基本概念5/86若待排序元素的關(guān)鍵字順序正好和要排序順序相同，稱此表中元素為正序。若待排序元素的關(guān)鍵字順序正好和要排序順序相反，稱此表中元素為反序?；诒容^的排序算法中有些算法是與初始序列的正序或反序相關(guān)，有些算法與初始序列的正序和反序無關(guān)。9.1排序的基本概念6/86當待排序元素的關(guān)鍵字均不相同時，排序的結(jié)果是唯一，否則排序的結(jié)果不一定唯一。

如果待排序的表中，存在有多個關(guān)鍵字相同的元素，經(jīng)過排序后這些具有相同關(guān)鍵字的元素之間的相對次序保持不變，稱這種排序方法是穩(wěn)定的；反之，若具有相同關(guān)鍵字的元素之間的相對次序發(fā)生變化，則稱這種排序方法是不穩(wěn)定的。5.算法的穩(wěn)定性9.1排序的基本概念7/86在本章中，以順序表作為排序數(shù)據(jù)的存儲結(jié)構(gòu)（除基數(shù)排序采用單鏈表和外排序之外）。為簡單起見，假設(shè)關(guān)鍵字類型為int類型。待排序的順序表中元素類型定義如下：typedefintKeyType;typedefstruct{KeyTypekey; //存放關(guān)鍵字,KeyType為關(guān)鍵字類型

ElemTypedata; //其他數(shù)據(jù),ElemType為其他數(shù)據(jù)的類型}SqType;6.排序數(shù)據(jù)的組織9.1排序的基本概念8/869.2插入排序插入排序基本思路：每一趟將一個待排序的元素，按其關(guān)鍵字值的大小插入到已經(jīng)排序的部分文件中適當位置上，直到全部插入完成。主要的插入排序算法：直接插入排序、折半插入排序和希爾排序。9.2插入排序9/869.2.1直接插入排序直接插入排序是一種最簡單的排序方法，其過程是依次將每個元素插入到一個有序的序列中去。

有序區(qū)R[0]

……

R[i-1]無序區(qū)R[i]

……

R[n-1]有序區(qū)R[0]……

R[i-1]

R[i]無序區(qū)R[i+1]

……

R[n-1]一趟排序初始時，有序區(qū)只有一個元素R[0]i＝1~n-1，共經(jīng)過n-1趟排序9.2插入排序10/86

【例9.1】已知有10個待排序的元素，它們的關(guān)鍵字序列為(75,87,68,92,88,61,77,96,80,72)，給出用直接插入排序法進行排序的過程。初始序列75876892886177968072i=175876892886177968072i=268758792886177968072i=368758792886177968072i=468758788926177968072i=561687587889277968072i=661687577878892968072i=761687577878892968072i=861687577808788929672i=961687275778087889296最終結(jié)果616872757780878892969.2插入排序i=1的行表示i=1這一趟的排序結(jié)果11/86以i=6即插入77為例說明一趟的過程：616875878892770123456有序區(qū)tmp…i=5的排序結(jié)果：i=6的排序結(jié)果12/86直接插入排序算法如下：voidInsertSort(SqTypeR[],intn) {inti,j;SqTypetmp;

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

//從第二個元素即R[1]開始的

{if(R[i-1].key>R[i].key)

{tmp=R[i];

//取出無序區(qū)的第一個元素R[i]

j=i-1; //在R[0..i-1]中找R[i]的插入位置

do

{R[j+1]=R[j]; //將關(guān)鍵字大于tmp.key的元素后移

j--; //繼續(xù)向前比較

}while(j>=0&&R[j].key>tmp.key);

R[j+1]=tmp;

//在j+1處插入R[i]

}

}}9.2插入排序13/86直接插入排序算法分析：最好的情況（關(guān)鍵字在元素序列中順序有序）：“比較”的次數(shù)：0“移動”的次數(shù)：最壞的情況（關(guān)鍵字在元素序列中逆序有序）：“比較”的次數(shù)：“移動”的次數(shù)：總的平均比較和移動次數(shù)約為9.2插入排序14/86歸納起來，直接插入排序算法的性能如表9.1所示。時間復雜度空間復雜度穩(wěn)定性最好情況最壞情況平均情況O(n)O(n2)O(n2)O(1)穩(wěn)定9.2插入排序15/869.2.2折半插入排序利用有序區(qū)的有序性?？梢圆捎谜郯氩檎曳椒ㄏ仍赗[0..i-1]中找到插入位置，再通過移動元素進行插入。這樣的插入排序稱為折半插入排序或二分插入排序。9.2插入排序16/86折半插入排序的算法如下：voidBinInsertSort(SqTypeR[],intn){inti,j,low,high,mid;SqTypetmp;

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

{if(R[i-1].key>R[i].key)

{tmp=R[i]; //將R[i]保存到tmp中

low=0;high=i-1;

while(low<=high)

//在R[low..high]中折半查找

{mid=(low+high)/2;//取中間位置

if(tmp.key<R[mid].key)

high=mid-1;

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

else

low=mid+1;

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

}

for(j=i-1;j>=high+1;j--) //元素后移

R[j+1]=R[j];

R[high+1]=tmp;

//插入原來的R[i]

}

}}9.2插入排序17/86折半插入排序的元素移動次數(shù)與直接插入排序相同，不同的僅是變分散移動為集中移動。在R[0..i-1]中查找插入R[i]的位置，折半查找的平均關(guān)鍵字比較次數(shù)為log2(i+1)，平均移動元素的次數(shù)為i/2+2，所以平均時間復雜度為：就平均性能而言，折半查找優(yōu)于順序查找，所以折半插入排序也優(yōu)于直接插入排序。9.2插入排序18/86希爾排序基本思路：先取定一個小于n的整數(shù)d1作為第一個增量，把表的全部元素分成d1個組，所有距離為d1的倍數(shù)的元素放在同一個組中，在各組內(nèi)進行直接插入排序。然后取第二個增量d2（＜d1），重復上述的分組和排序，直至所取的增量dt=1（dt<dt-1<…<d2<d1），即所有元素放在同一組中進行直接插入排序為止。9.2.3希爾排序9.2插入排序19/86將元素序列分成若干子序列，分別對每個子序列進行插入排序。

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

個元素分成d

個子序列：

{R[0]，R[d]，R[2d]，…，

R[kd]}{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}

…{R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1]}9.2插入排序20/86例如：9876543210初始序列8765943210d=5直接插入排序4321098765d=d/2=243210987650123456789直接插入排序d=d/2=10123456789直接插入排序0123456789注意：對于d=1的一趟，排序前的數(shù)據(jù)已將近正序！9.2插入排序21/86取d1=n/2，di+1=

di/2

時的希爾排序的算法如下：voidShellSort(SqTypeR[],intn) {inti,j,d;

SqTypetmp;

d=n/2;

//增量置初值

while(d>0)

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

{tmp=R[i]; //對所有相隔d位置的元素組采用直接插入排序

j=i-d;

while(j>=0&&tmp.key<R[j].key){R[j+d]=R[j];j=j-d;

}

R[j+d]=tmp;

}

d=d/2;

//減小增量

}}9.2插入排序22/86希爾排序的時間復雜度約為O(n1.3)。為什么希爾排序比直接插入排序好？例如：有10個元素要排序。希爾排序直接插入排序大約時間=102=100d=5：分為5組，時間約為5*22＝20d=2：分為2組，時間約為2*52＝50d=1：分為1組，幾乎有序，時間約為10＋＋＝809.2插入排序23/86歸納起來，希爾排序算法的性能如表9.2所示。時間復雜度空間復雜度穩(wěn)定性最好情況最壞情況平均情況－O(n2)O(n1.5)O(1)不穩(wěn)定9.2插入排序24/869.3交換排序交換排序基本思路：兩兩比較待排序元素的關(guān)鍵字，并交換不滿足次序要求的那些偶對，直到全部滿足為止。主要的交換排序算法：冒泡排序和快速排序。9.3交換排序25/86有序區(qū)R[0]┇R[i-1]無序區(qū)R[i]R[i+1]┇R[n-1]將無序區(qū)中最小元素放在R[i]有序區(qū)R[0]┇R[i-1]R[i]無序區(qū)R[i+1]┇R[n-1]一趟排序初始有序區(qū)為空。i＝0~n-2，共n-1趟使整個數(shù)據(jù)有序。R[i]有序區(qū)總是全局有序的9.3.1冒泡排序9.3交換排序26/86R[j]和R[j-1]反序

交換。若某一趟比較時不出現(xiàn)任何元素交換，說明所有元素已排好序了，就可以結(jié)束本算法。9.3交換排序27/86

【例9.3】已知有10個待排序的元素，它們的關(guān)鍵字序列為(75,87,68,92,88,61,77,96,80,72)，給出用冒泡排序法進行排序的過程。初始序列75876892886177968072i=0[61]758768928872779680i=161[68]7587729288778096i=26168[72]75877792888096i=3616872[75]778780928896i=461687275[77]8087889296i=56168727577[80]87889296最后結(jié)果616872757780878892969.3交換排序28/86冒泡排序算法如下：voidBubbleSort(SqTypeR[],intn){

inti,j,exchange;

SqTypetmp;

for(i=0;i<n-1;i++)

{exchange=0;

//本趟排序前置exchange為0

for(j=n-1;j>i;j--) //比較,找出最小關(guān)鍵字的元素

{

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

{tmp=R[j];

//R[j]與R[j-1]進行交換,

R[j]=R[j-1]; //將最小關(guān)鍵字元素前移

R[j-1]=tmp;

exchange=1; //本趟排序發(fā)生交換置exchange為1

}

}if(exchange==0) //本趟未發(fā)生交換時結(jié)束算法

return;

}}29/86最好的情況（正序）：只需進行一趟冒泡“比較”的次數(shù)：0“移動”的次數(shù)：n-1最壞的情況（反序）：需進行n-1趟冒泡“比較”的次數(shù)：“移動”的次數(shù)：9.3交換排序30/86歸納起來，冒泡排序算法的性能如表9.3所示。時間復雜度空間復雜度穩(wěn)定性最好情況最壞情況平均情況O(n)O(n2)O(n2)O(1)穩(wěn)定9.3交換排序31/86

首先對無序的元素序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。無序序列無序子序列(1)無序子序列(2)基準一次劃分分別進行快速排序9.3.2快速排序9.3交換排序32/86每趟使表的第一個元素（基準）放入適當位置，將表一分為二，對子表按遞歸方式繼續(xù)這種劃分。直至劃分的子表長為0或者1。9.3交換排序33/86

【例9.4】設(shè)待排序的表有10個元素，其關(guān)鍵字分別為（6，8，7，9，0，1，3，2，4，5）。說明采用快速排序方法進行排序的過程。9.3交換排序34/866

87

9

0

1

3

2455

423019

7861

423

050，1，2，3，4，5，6，7，8，902

3

413

42348

7978快速排序遞歸樹將遞歸樹看成一棵3叉樹，每個分支結(jié)點對應(yīng)一次遞歸調(diào)用。這里遞歸次數(shù)：7左右子序列處理的順序無關(guān)9.3交換排序35/8631542劃分如何做？tmpiji=j：處理完畢劃分完畢整個序列：R[s..t]左子序列：R[s..i-1]右子序列：R[i+1..t]36/86快速排序算法如下：voidQuickSort(SqTypeR[],ints,intt)//對R[s..t]的元素進行遞增快速排序{inti=s,j=t;SqTypetmp;if(s<t) //區(qū)間內(nèi)至少存在2個元素的情況

{tmp=R[s]; //用區(qū)間的第1個元素作為基準

while(i!=j) //從區(qū)間兩端交替向中間掃描,直至i=j為止

{while(j>i&&R[j].key>=tmp.key)

j--; //從右向左掃描,找第1個小于tmp.key的R[j] if(i<j)

{R[i]=R[j]; //將R[j]前移到R[i]的位置

i++;}

while(i<j&&R[i].key<=tmp.key)

i++; //從左向右掃描,找第1個大于tmp.key的R[i]

if(i<j){R[j]=R[i]; //將R[i]后移到R[j]的位置

j--;}

}

R[i]=tmp;9.3交換排序37/86QuickSort(R,s,i-1);

//對左區(qū)間遞歸排序

QuickSort(R,i+1,t);

//對右區(qū)間遞歸排序

}}9.3交換排序R[s]………R[t]R[s]…R[i-1]R[i+1]…R[t]R[i]一次劃分分別進行快速排序38/86算法分析最好的情況（隨機分布）n個元素n/2個元素n/2-1個元素時間復雜度:O(nlog2n)最壞的情況（正序或者反序）n個元素n-1個元素空時間復雜度:O(n2)39/86則可得結(jié)果：結(jié)論:

快速排序的時間復雜度為O(nlog2n)平均情況：平均所需棧空間為O(log2n)。nk-1n-k1次劃分的時間Tavg(n)=Cnlog2n。9.3交換排序40/86歸納起來，快速排序算法的性能如表9.4所示。時間復雜度空間復雜度穩(wěn)定性最好情況最壞情況平均情況O(nlog2n)O(n2)O(nlog2n)O(log2n)不穩(wěn)定9.3交換排序41/869.4選擇排序選擇排序基本思路：每步從待排序的元素中選出關(guān)鍵字最小的元素，按順序放在已排序的元素序列的最后，直到全部排完為止。主要的選擇排序算法：簡單選擇排序和堆排序。9.4選擇排序42/86有序序列R[0..i-1]無序序列R[i..n-1]

第i

趟簡單選擇排序從中選出關(guān)鍵字最小的元素有序序列R[0..i-1]無序序列R[i+1..n-1]9.4.1簡單選擇排序9.4選擇排序43/86

【例9.5】已知有10個待排序的元素，它們的關(guān)鍵字序列為(75,87,68,92,88,61,77,96,80,72)，給出用直接選擇排序法進行排序的過程。初始序列75876892886177968072i=061876892887577968072i=161688792887577968072i=261687292887577968087i=361687275889277968087i=461687275779288968087i=561687275778088969287i=661687275778087969288i=761687275778087889296i=861687275778087889296最后結(jié)果616872757780878892969.4選擇排序44/86簡單選擇排序算法如下：voidSelectSort(SqTypeR[],intn) {inti,j,k;

SqTypetmp;

for(i=0;i<n-1;i++)

{k=i;

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

if(R[j].key<R[k].key)

k=j; //用k指出每趟在無序區(qū)段的最小元素

}if(k!=i)

{tmp=R[i]; //將R[k]與R[i]交換

R[i]=R[k];R[k]=tmp;

}

}}9.4選擇排序45/86

對n

個元素進行簡單選擇排序，所需進行的關(guān)鍵字間的比較次數(shù)總計為：移動元素的次數(shù)，最小值為0,最大值為3(n-1)。9.4選擇排序46/86歸納起來，簡單選擇排序算法的性能如表9.5所示。時間復雜度空間復雜度穩(wěn)定性最好情況最壞情況平均情況O(n2)O(n2)O(n2)O(1)不穩(wěn)定9.4選擇排序47/86堆排序采用堆結(jié)構(gòu)選擇最大（最?。┰?。設(shè)排序元素為R[1..n]。將R[1..n]看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)。如果每個結(jié)點的關(guān)鍵字均大于等于其所有孩子結(jié)點的關(guān)鍵字，稱為大根堆。如果每個結(jié)點的關(guān)鍵字均小于等于其所有孩子結(jié)點的關(guān)鍵字，稱為小根堆。本章的堆排序采用的大根堆。9.4.2堆排序9.4選擇排序48/86a1a2a3an…完全二叉樹i2i2i+1左孩子右孩子大根堆：對應(yīng)的完全二叉樹中，任意一個結(jié)點的關(guān)鍵字都大于或等于它的孩子結(jié)點的關(guān)鍵字。最小關(guān)鍵字的元素一定是某個葉子結(jié)點?。。有蚓幪柗绞剑篴1

a2

…

an將序列a1

a2

…

an看成是一顆完全二叉樹9.4選擇排序49/86堆排序的關(guān)鍵是構(gòu)造堆,這里采用篩選算法建堆。所謂“篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點使整個二叉樹也成為一個堆。堆堆篩選堆9.4選擇排序50/86例如：（6,8,9,5,7,1）89571大根堆大根堆考慮根，不是大根堆比較tmp6比較整個調(diào)整成大根堆了！9.4選擇排序51/86

假設(shè)對R[low..high]進行堆調(diào)整，它是一棵滿足篩選條件的完全二叉樹，即以R[low]為根結(jié)點的左子樹和右子樹均為堆，其調(diào)整堆的算法sift()如下：voidSift(SqTypeR[],intlow,inthigh) //對R[low..high]進行堆篩選{inti=low,j=2*i; //R[j]是R[i]的左孩子

SqTypetmp=R[i];while(j<=high)

{if(j<high&&R[j].key<R[j+1].key)

j++;

//若右孩子較大,把j指向右孩子

if(tmp.key<R[j].key)

{R[i]=R[j]; //將R[j]調(diào)整到雙親結(jié)點位置上

i=j; //修改i和j值,以便繼續(xù)向下篩選

j=2*i;

}

elsebreak; //已是大根堆,篩選結(jié)束

}

R[i]=tmp; //被篩選結(jié)點的值放入最終位置}9.4選擇排序52/869.4選擇排序是一個堆是一個堆295413從根開始篩選大根堆tmp篩選示例相當于：將2有序插入的（9,4）中（9,4,2）53/86堆排序過程：從最后一個分支結(jié)點（編號為n/2）開始到根結(jié)點（編號為1）通過多次調(diào)用篩選算法建立初始堆。排序過程：9.4選擇排序?qū)[1]（無序區(qū)中最大元素）與無序區(qū)最后一個元素交換，歸位無序區(qū)最后一個元素，無序區(qū)減少一個元素。再篩選，重復進行，直到無序區(qū)只有一個元素。54/86堆排序的算法如下：voidHeapSort(SqTypeR[],intn)//對R[1..n]進行遞增堆排序{inti;

SqTypetmp;

for(i=n/2;i>=1;i--) //循環(huán)建立初始堆

Sift(R,i,n);

for(i=n;i>=2;i--) //進行n-1次循環(huán),完成堆排序

{ tmp=R[1]; //將R[1]和R[i]交換

R[1]=R[i];R[i]=tmp;

Sift(R,1,i-1); //篩選

}}9.4選擇排序55/86【例9.6】已知有10個待排序的元素，它們的關(guān)鍵字序列為（75，87，68，92，88，61，77，96，80，72），給出用堆排序法進行排序的過程。75876892886177968072（1）建立初始堆的過程758768928861779680729.4選擇排序56/8675876892886177968072758768968861779280729.4選擇排序57/8675876896886177928072758777968861689280729.4選擇排序58/8675877796886168928072759677928861688780729.4選擇排序59/867596779288616887807296927787886168758072初始堆：96,92,77,87,88,61,68,75,80,729.4選擇排序60/86（2）排序過程96927787886168758072第1趟排序結(jié)果（i=10）初始堆：72,92,77,87,88,61,68,75,80,96交換72969.4選擇排序61/86729277878861687580第2趟排序結(jié)果（i=9）初始堆：80,88,77,87,72,61,68,75,92,96交換928877877261687580篩選9280最終結(jié)果：61,68,72,75,77,80,87,88,92,90以此類推9.4選擇排序62/86堆排序的時間復雜度分析：對高度為k的堆，“篩選”所需進行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；調(diào)整“堆頂”n-1次，總共進行的關(guān)鍵字比較的次數(shù)不超過

2(

log2(n-1)

+

log2(n-2)

+…+log22)<2n(

log2n

)

因此，堆排序的時間復雜度為O(nlog2n)。對n個關(guān)鍵字，建成高度為h(=

log2n+1)的堆，所需進行的關(guān)鍵字比較的次數(shù)不超過4n9.4選擇排序63/86歸納起來，堆排序算法的性能如表9.6所示。時間復雜度空間復雜度穩(wěn)定性最好情況最壞情況平均情況O(nlog2n)O(nlog2n)O(nlog2n)O(1)不穩(wěn)定9.4選擇排序64/86歸并排序是多次將兩個或兩個以上的有序表合并成一個新的有序表。最簡單的歸并是直接將兩個有序的子表合并成一個有序的表─二路歸并排序。9.5歸并排序9.5

歸并排序65/86在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的元素有序子序列。歸并為一個元素的有序序列。有序序列R[low..high]有序子序列R[low..mid]有序子序列R[mid+1..high]9.5

歸并排序66/86

【例9.7】已知有10個待排序的元素，它們的關(guān)鍵字序列為（75，87，68，92，88，61，77，96，80，72），給出用歸并排序法進行排序的過程。75，87，68，92，88，61，77，96，80，7275，8768，9261，8877，9672，8068，75，87，9261，77，88，9672，8061，68，75，77，87，88，92，9672，8061，68，72，75，77，80，87，88，92，96

log2n

趟9.5

歸并排序67/86將兩個有序子表歸并為一個有序子表的算法Merge()：voidMerge(SqTypeR[],intlow,intmid,inthigh)//將R[low..mid]和R[mid+1..high]兩個相鄰的有序表歸并為有序表R[low..high]{SqType*R1;

inti=low,j=mid+1,k=0; //k是R1的下標R1=(SqType*)malloc((high-low+1)*sizeof(SqType));

//動態(tài)分配空間R1while(i<=mid&&j<=high) //均未掃描完時循環(huán){if(R[i].key<=R[j].key) //將第1子表中的元素放入R1中

{R1[k]=R[i];

i++;k++;

}

else

//將第2子表中的元素放入R1中

{R1[k]=R[j];

j++;k++;

}}9.5

歸并排序68/86

while(i<=mid) //將第1子表余下部分復制到R1

{ R1[k]=R[i]; i++;k++;

}

while(j<=high) //將第2子表余下部分復制到R1

{ R1[k]=R[j]; j++;k++;

}

for(k=0,i=low;i<=high;k++,i++)

R[i]=R1[k]; //將R1復制回R中

free(R1); //釋放R1所占內(nèi)存空間}9.5

歸并排序69/86MergePass()算法解決一趟歸并問題：voidMergePass(SqTypeR[],intlength,intn)//一趟二路歸并排序{inti;

for(i=0;i+2*length-1<n;i=i+2*length)

Merge(R,i,i+length-1,i+2*length-1);

//歸并length長的兩相鄰子表if(i+length-1<n)

//余下兩個子表,后者長度小于lengthMerge(R,i,i+length-1,n-1);}9.5

歸并排序70/86二路歸并排序算法如下：voidMergeSort(SqTypeR[],intn) //二路歸并算法{intlength;

for(length=1;length<n;length=2*length)

MergePass(R,length,n);}9.5

歸并排序71/86每一趟歸并的時間復雜度為O(n)，總共需進行

log2n

趟。所以對n個元素進行歸并排序的時間復雜度為Ο(nlog2n)。9.5

歸并排序72/86歸納起來，二路歸并排序算法的性能如表9.7所示。時間復雜度空間復雜度穩(wěn)定性最好情況最壞情況平均情況O(nlog2n)O(nlog2n)O(nlog2n)O(n)穩(wěn)定9.5

歸并排序73/86基數(shù)排序是通過“分配”和“收集”過程來實現(xiàn)排序。是一種借助于多關(guān)鍵字排序的思想對單關(guān)鍵字排序的方法。9.6基數(shù)排序9.6基數(shù)排序74/86一般地，元素R[i]的關(guān)鍵字R[i].key是由d位數(shù)字組成，即kd-1kd-2…k0，每一個數(shù)字表示關(guān)鍵字的一位，其中kd-1為最高位，k0是最低位，每一位的值都在0≤ki<r范圍內(nèi)，其中r稱為基數(shù)。例如，對于二進制數(shù)r為2，對于十進制數(shù)r為10。

9.6基數(shù)排序75/86基數(shù)排序有兩種：最低位優(yōu)先（LSD）和最高位優(yōu)先（MSD）。最低位優(yōu)先的過程：先按最低位的值對元素進行排序，在此基礎(chǔ)上，再按次低位進行排序，依此類推。由低位向高位，每趟都是根據(jù)關(guān)鍵字的一位并在前一趟的基礎(chǔ)上對所有元素進行排序，直至最高位，則完成了基數(shù)排序的整個過程。最高位優(yōu)先類似。9.6基數(shù)排序76/86分配：開始時，把Q0,Q1,…,Qr-1各個隊列置成空隊列，然后依次考察線性表中的每一個結(jié)點aj（j=0,1,…,n-1），如果aj的關(guān)鍵字kji=k，就把aj放進Qk隊列中。收集：把Q0,Q1,…,Qr-1各個隊列中的結(jié)點依次首尾相接，得到新的結(jié)點序列，從而組成新的線性表。對i=0,1,…,d-1，依次做一次“分配”和“收集”（其實就是一次穩(wěn)定的排序過程）。9.6基數(shù)排序77/86建立10個隊列，f為隊頭，r為隊尾

進行第1次分配：按個位進行第1次收集h→369→367→167→239→237→138→230→139f[0]←r[0]f[7]←r[7]f[8]←r[8]f[9]←r[9]→369→367→167→237→239→139→138→230h→230→367→167→237→138→369→239→139例如(369,367,167,239,237,138,230,139)

基數(shù)排序第1趟排序完畢分配時是按一個一個元素進行的收集時是按一個一個隊列進行的9.6基數(shù)排序78/86

進行第2次分配：按拾位進行第2次收集f[3]←r[3]f[6]←r[6]→367→167→369→230h第2趟排序完畢→237→138→139→239h→230→367→167→237→138→369→239→139→230→237→138→139→239→367→167→3699.6基數(shù)排序79/86

進行第3次分配：按百位f[1]←r[1]f[2]←r[2]f[3]←r[3]→239→139→138→237→230→369→367h→230→237→138→139→239→367→167→369→167進行第3次收集h第3趟排序完畢，得到最終排序結(jié)果→139→138→167→239→237→230→369→3679.6基數(shù)排序80/86單鍵表中結(jié)點類型RadixNode聲明如下：typedefstructrnode{charkey[MAXD]; //存放關(guān)鍵字ElemTypedata; //存放其他數(shù)據(jù)

structrnode*next;}RadixNode; //單鏈表結(jié)點類型9.6基數(shù)排序123"321"低位高位對于整數(shù)應(yīng)該按個位開始排序，轉(zhuǎn)換為字符數(shù)組后按最高位優(yōu)先排序！81/86voidRadixSort1(RadixNode*&h,intd,intr)//實現(xiàn)基數(shù)排序:h為待排序數(shù)列單鏈表指針,r為基數(shù),d為關(guān)鍵字位數(shù){RadixNode*head[MAXR]; //建立鏈隊隊頭數(shù)組

RadixNode*tail[MAXR]; //建立鏈隊隊尾數(shù)組RadixNode*p,*tc;

inti,j,k;9.6基數(shù)排序最高位優(yōu)先基數(shù)排序算法82/86for(i=d-1;i>=0;i--) //從高位到低位循環(huán){for(j=0;j<r;j++) //初始化各鏈隊首、尾指針

head[j]=tail[j]=NULL;

p=h;

while(p!=NULL)

//分配：對于原鏈表中每個結(jié)點循環(huán)

{k=p->key[i]-'0'; //找第k個鏈隊

if(head[k]==NULL) //第k個鏈隊空，隊頭隊尾均指向p結(jié)點

head[k]=tail[k]=p;

else

{tail[k]->next=p; //第k個鏈隊非空時，p結(jié)點入隊

tail[k]=p;

}

p=p->next; //取下一個待排序的元素

}9.6基數(shù)排序83/86h=NULL;

//重新用h來收集所有結(jié)點

for(j=0;j<r;j++) //收集：對于每一個鏈隊循環(huán)

{

if(head[j]!=NULL) //若第j個鏈隊是第一個非空鏈隊

{if(h==NULL)

{h=head[j];tc=tail[j];}

else

//若第j個鏈隊是其他非空鏈隊

{tc->next=head[j];tc=tail[j];}

}

tc->next=NULL; //尾結(jié)點的next域置NULL

}

}}9.6基數(shù)排序84/86

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

收集為O(r)（r為“基數(shù)”）

d為“分配-收集”的趟數(shù)9.6基數(shù)排序85/86歸納起來，基數(shù)排序算法的性能如表9.8所示。時間復雜度空間復雜度穩(wěn)定性最好情況最壞情況平均情況O(d(n+r))O(d(n+r))O(d(n+r))O(r)穩(wěn)定9.6基數(shù)排序86/86第9章排序9.1排序的基本概念9.2插入排序9.3交換排序9.4選擇排序9.5歸并排序9.6基數(shù)排序9.7外排序第9章

排序87/32（1）生成若干初始歸并段（順串）：這一過程也稱為文件預處理，常規(guī)方法：

①把含有n個元素的文件，按內(nèi)存大小分成若干長度為L的子文件（歸并段）。

②分別將各子文件（歸并段）調(diào)入內(nèi)存，采用有效的內(nèi)排序方法排序后送回外存。

（2）多路歸并：對這些初始歸并段進行多遍歸并，使得有序的歸并段逐漸擴大，最后在外存上形成整個文件的單一歸并段，也就完成了這個文件的外排序。9.7外排序9.7外排序外排序的基本方法是歸并排序法。它分為以下兩個步驟：88/32內(nèi)存abc.databc1.databc2.dat…abcn.dat內(nèi)存abc1.databc2.dat…abcn.databc.dat第1步第2步有序均有序某內(nèi)排序算法某排序算法：一般為歸并算法9.7外排序89/32外排序的時間：讀寫文件的時間：用讀寫元素次數(shù)表示。關(guān)鍵字比較的時間：內(nèi)存中的元素比較。外排序的時間≈讀寫文件時間+關(guān)鍵字比較時間9.7外排序90/329.7.1磁盤排序過程磁盤（磁盤是一種直接存取設(shè)備）排序過程如下：Fin文件內(nèi)存讀寫Fout文件F1文件F2文件Fm文件…寫寫寫內(nèi)存讀讀讀

生成若干初始歸并段

歸并成一個有序文件9.7外排序91/32設(shè)有一個文件Fin.dat，內(nèi)含4500個元素：A1,A2,…,A4500?，F(xiàn)在要對該文件進行排序?？烧加玫膬?nèi)存空間至多只能對750個元素進行排序。輸入文件（被排序的文件）放在磁盤上，頁塊長為250個元素。文件Fin.dat（含4500個元素）容量為750個元素產(chǎn)生6個長度為750個元素的有序文件F1～F6。第一階段某種內(nèi)排序方法9.7外排序92/32可用內(nèi)存空間大小為750個元素第二階段：歸并過程

F1F2F3F4F5F6F7F8F9F10F119.7外排序93/329.7.2初始歸并段的生成方法1采用前面介紹的常規(guī)內(nèi)排序方法，可以實現(xiàn)初始歸并段的生成，但所生成的歸并段的大小正好等于一次能放入內(nèi)存中的元素個數(shù)。顯然存在局限性。

內(nèi)存abc.databc1.databc2.dat…abcn.dat均有序某內(nèi)排序算法特點：產(chǎn)生的初始歸并段個數(shù)多，每個初始歸并段的長度大致相等。9.7外排序94/32采用置換－選擇排序算法用于生成初始歸并段。方法2

特點：產(chǎn)生的初始歸并段個數(shù)少，每個初始歸并段的長度可能差異大。9.7外排序95/32

【例9.9】設(shè)某個磁盤文件中共有18個元素，各元素的關(guān)鍵字分別為（15，4，97，64，17，32，108，44，76，9，39，82，56，31，80，73，255，68）。

若內(nèi)存工作區(qū)可容納5個元素，用置換-選擇排序算法可產(chǎn)生幾個初始歸并段，每個初始歸并段包含哪些元素？9.7外排序96/32173294476108398256318073154976425568∞18個元素（w=5）：內(nèi)存工作區(qū)w=5歸并段1：歸并段2：Rmin=415173244647682971089依次類推，產(chǎn)生歸并段2：9，31，39，56，68，73，80，2559.7外排序97/32k=2時,采用平衡歸并時，如果初始歸并段有m個，那么這樣的歸并樹就有

log2m

+1層。要對數(shù)據(jù)進行

log2m

趟掃描。9.7.3多路平衡歸并

說明：如果所有初始歸并段的長度（初始歸并段中的元素個數(shù)）相等或大致相等，可采用k路平衡歸并。1.k路平衡歸并的效率分析9.7外排序98/32例如：二路平衡歸并5初始序列：（5,4,1,6,8,3,2,7）4168327451638271456237812345678高度log2m=4歸并3趟每個頁塊讀寫各1次假設(shè)一個頁塊存放1個元素讀或者寫元素次數(shù)恰好是WPL，這里WPL=8*1*3=24讀寫元素次數(shù)=2WPL，這里為48用WPL反映外排序中的讀寫文件的時間9.7外排序99/32k路平衡歸并的讀寫文件時間分析：若有m個初始歸并段，共u個元素歸并趟數(shù)=

logkm

k越大，WPL越少，則讀寫元素的次數(shù)越少。在內(nèi)存空間允許的情況下，k越大越好！9.7外排序100/32若在歸并中采用簡單選擇方法，每次在k個元素中選擇最小者，需要關(guān)鍵字比較k-1次。每趟歸并u個元素需要做(u-1)*(k-1)次比較，s=

logkm

）趟歸并總共需要的關(guān)鍵字比較次數(shù)為：k路平衡歸并的關(guān)鍵字比較時間分析：k越大，關(guān)鍵字比較次數(shù)越多！增大歸并路數(shù)k，會使內(nèi)部歸并的時間增大。若k增大到一定的程度，就會抵消掉由于減少讀寫磁盤次數(shù)而贏得的時間。s*(u-1)*(k-1)=

logkm

*(u-1)*(k-1)=

log2m

*(u-1)*(k-1)／

log2k

9.7外排序101/32在k路歸并中從k個元素簡單選擇最小元素2.利用敗者樹實現(xiàn)k路平衡歸并采用敗者樹從k個元素簡單選擇最小元素9.7外排序102/32利用敗者樹實現(xiàn)k路平衡歸并的過程是：

敗者樹類似于堆排序中的堆。先建立敗者樹。然后對k個輸入有序段進行k路平衡歸并。9.7外排序103/32

【例9.10】設(shè)有5個初始歸并段，它們中各元素的關(guān)鍵字分別是：

F0：{17，21，∞}

F1：{5，44，∞}

F2：{10，12，∞}

F3：{29，32，∞}

F4：{15，56，∞}

其中，∞是段結(jié)束標志。說明利用敗者樹進行k=5路平衡歸并排序的過程。9.7外排序104/32解：

構(gòu)建敗者樹29F315F417F05F110F25(-∞)5(-∞)5(-∞)5(-∞)冠軍（最小者）k=5：創(chuàng)建含有k個葉子結(jié)點的完全二叉樹，總共2k-1=9個結(jié)點，另外添加一個冠軍結(jié)點。每個葉子結(jié)點對應(yīng)一個歸并段，段號為0～4。初始時每個分支結(jié)點（含冠軍）取值“5(-∞)”，5表示段號（此時為虛擬段號），-∞表示最小關(guān)鍵字。例如，某結(jié)點取值為“4(15)”，表示結(jié)點值來自4號段的關(guān)鍵字15對應(yīng)的元素。9.7外排序105/3229F3