CONTENTS1/63提綱第9章排序019.1排序基本概念029.2插入排序039.3交換排序049.4選擇排序說明：排序數(shù)據(jù)中可以存在相同關(guān)鍵字的記錄。本章僅考慮遞增排序。1、排序的定義

所謂排序，是整理表中的記錄，使之按關(guān)鍵字遞增（或遞減）有序排列：排序n個(gè)記錄，R0，R1，…，Rn-1，對(duì)應(yīng)關(guān)鍵字分別為k0，k1，…，kn-1Ri,0，Ri,1，…，Ri,n-1，使得遞增ki,0≤ki，1≤…≤ki,n-1

（或遞減ki,0≥ki,1≥…≥ki,n-1）2/639.1排序基本概念

當(dāng)待排序記錄的關(guān)鍵字均不相同時(shí)，排序的結(jié)果是唯一的。2435112345張三李四王五劉六陳七張三李四王五陳七劉六3/632、排序的穩(wěn)定性如果待排序的表中，存在有多個(gè)關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變，則稱這種排序方法是穩(wěn)定的。

反之，若具有相同關(guān)鍵字的記錄之間的相對(duì)次序發(fā)生變化，則稱這種排序方法是不穩(wěn)定的。323151233532315123354/63在排序過程中，若整個(gè)表都是放在內(nèi)存中處理，排序時(shí)不涉及數(shù)據(jù)的內(nèi)、外存交換，則稱之為內(nèi)排序；反之，若排序過程中要進(jìn)行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外排序。文件內(nèi)存5/633、排序的分類內(nèi)排序基于比較的排序算法不基于比較的排序算法插入排序交換排序選擇排序歸并排序基數(shù)排序6/63假設(shè)有3個(gè)記錄(R1，R2，R3)，對(duì)應(yīng)的關(guān)鍵字為(k1，k2，k3)。初始數(shù)據(jù)序列有3!=6種情況：1，2，31，3，22，1，32，3，13，1，23，2，1

n個(gè)記錄，初始數(shù)據(jù)序列有n!種情況7/63基于比較的內(nèi)排序算法最快有多快？R1R2R32

3

1R1<R2為真，不交換R1R2R3

2

3

1R2<R3為假，R2、R2交換R1R3R22

1

3R1<R3為假，R1、R2交換R3R1R21

2

3總共3次關(guān)鍵字比較8/63以(R1，R2，R3)=（2，3，1）為例，一種基于比較的排序方法：k1≤k2(R1，R2，R3)k2≤k3(R1，R2，R3)①

(R1，R2，R3)k1≤k3(R1，R3，R2)②(R1，R3，R2)③(R3，R1，R2)是是否是否k1≤k3(R2，R1，R3)④

(R2，R1，R3)k2≤k3(R2，R3，R1)⑤(R2，R3，R1)⑥(R3，R2，R1)是否是否否決策樹是一棵有n!個(gè)葉結(jié)點(diǎn)的二叉樹。9/63所有可能的初始序列的排序過程構(gòu)成一個(gè)決策樹：決策樹可以近似看成是一顆高度為h，葉結(jié)點(diǎn)個(gè)數(shù)為n!的滿二叉樹。

葉結(jié)點(diǎn)層，n!個(gè)結(jié)點(diǎn)h葉結(jié)點(diǎn)個(gè)數(shù)=n!總結(jié)點(diǎn)個(gè)數(shù)=2n!-1h=log2(總結(jié)點(diǎn)個(gè)數(shù)+1)=log2(n!)≈nlog2n平均關(guān)鍵字比較次數(shù)=h-1移動(dòng)次數(shù)也是同樣的數(shù)量級(jí)，即這樣的算法最壞時(shí)間復(fù)雜度為O(nlog2n)。同樣可以證明平均時(shí)間復(fù)雜度也為O(nlog2n)。10/63n個(gè)記錄采用基于比較的排序方法：最好的平均時(shí)間復(fù)雜度為O(nlog2n)。最好情況是排序序列正序，此時(shí)的時(shí)間復(fù)雜度為O(n)。11/63結(jié)論：typedefintKeyType; //定義關(guān)鍵字類型typedefstruct //記錄類型{KeyTypekey; //關(guān)鍵字項(xiàng)

InfoTypedata; //其他數(shù)據(jù)項(xiàng)，類型為InfoType}RecType; //排序的記錄類型定義

待排序的順序表的數(shù)據(jù)元素類型定義如下：12/634、內(nèi)排序數(shù)據(jù)的組織主要的插入排序方法：（1）直接插入排序（2）折半插入排序（3）希爾排序有序區(qū)無序區(qū)一個(gè)一個(gè)地插入9.2插入排序基本思路不一定是全局有序（整體有序）全局有序區(qū)的元素在后面排序中不再發(fā)生位置的改變13/63有序區(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]一趟排序初始時(shí)，有序區(qū)只有一個(gè)元素R[0]i＝1~n-1，共經(jīng)過n-1趟排序基本思路14/639.2.1直接插入排序jR[i]j=i-1插入位置有序區(qū)R[0..i-1]無序區(qū)R[i..n-1]R[j+1]=tmptmp使R[0..i]有序擴(kuò)大有序區(qū)R[j]大時(shí)便后移當(dāng)R[i].key<R[i-1].key時(shí)15/63一趟直接插入排序：在有序區(qū)中插入R[i]的過程。設(shè)待排序的表有10個(gè)元素，其關(guān)鍵字分別為（9，8，7，6，5，4，3，2，1，0）。說明采用直接插入排序方法進(jìn)行排序的過程。16/63示例（9，8，7，6，5，4，3，2，1，0）初始：（8，9，7，6，5，4，3，2，1，0）i=1：（7，8，9，6，5，4，3，2，1，0）i=2：（6，7，8，9，5，4，3，2，1，0）i=3：（5，6，7，8，9，4，3，2，1，0）i=4：（4，5，6，7，8，9，3，2，1，0）i=5：（3，4，5，6，7，8，9，2，1，0）i=6：（2，3，4，5，6，7，8，9，1，0）i=7：（1，2，3，4，5，6，7，8，9，0）i=8：（0，1，2，3，4，5，6，7，8，9）i=9：17/63voidInsertSort(RecTypeR[]，intn){inti，j;RecTypetmp;for(i=1;i<n;i++){if(R[i].key<R[i-1].key])//反序時(shí){tmp=R[i]; j=i-1;

do //找R[i]的插入位置{R[j+1]=R[j]; //將關(guān)鍵字大于R[i].key的記錄后移

j--;}while(j>=0&&R[j].key>tmp.key)R[j+1]=tmp; //在j+1處插入R[i]}}}18/63直接插入排序的算法：算法分析最好的情況（關(guān)鍵字在記錄序列中正序）：最壞的情況（關(guān)鍵字在記錄序列中反序）：“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“比較”的次數(shù)：“移動(dòng)”的次數(shù)：總的平均比較和移動(dòng)次數(shù)約為最好：O(n)最壞：O(n2)平均：O(n2)19/63查找采用折半查找方法，稱為二分插入排序或折半插入排序。有序區(qū)R[0]……R[i-1]無序區(qū)R[i]……R[n-1]采用折半查找在有序區(qū)找到插入的位置基本思路20/639.2.2折半插入排序voidBinInsertSort(RecTypeR[]，intn){inti，j，low，high，mid;RecTypetmp;for(i=1;i<n;i++){if(R[i].key<R[i-1].key]) //反序時(shí){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; //插入點(diǎn)在左半?yún)^(qū)

else low=mid+1; //插入點(diǎn)在右半?yún)^(qū)

}//找位置high for(j=i-1;j>=high+1;j--) //記錄后移

R[j+1]=R[j]; R[high+1]=tmp; //插入tmp

}}21/63折半插入排序算法：折半插入排序：在R[0..i-1]中查找插入R[i]的位置，折半查找的平均關(guān)鍵字比較次數(shù)為log2(i+1)-1，平均移動(dòng)元素的次數(shù)為i/2+2，所以平均時(shí)間復(fù)雜度為：折半插入排序采用折半查找，查找效率提高。但元素移動(dòng)次數(shù)不變，僅僅將分散移動(dòng)改為集合移動(dòng)。22/63算法分析說明：本題為6312年全國(guó)考研題對(duì)同一待排序序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是（）。A.排序的總趟數(shù)

B.元素的移動(dòng)次數(shù)C.使用輔助空間的數(shù)量

D.元素之間的比較次數(shù)23/63示例常見的交換排序方法：（1）冒泡排序（或起泡排序）（2）快速排序兩個(gè)記錄反序時(shí)進(jìn)行交換基本思路24/639.3交換排序有序區(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趟使整個(gè)數(shù)據(jù)有序。R[i]有序區(qū)總是全局有序的25/639.3.1冒泡排序voidBubbleSort(RecTypeR[]，intn){inti，j;RecTypetemp;for(i=0;i<n-1;i++){for(j=n-1;j>i;j--) //比較找本趟最小關(guān)鍵字的記錄

if(R[j].key<R[j-1].key) {temp=R[j]; //R[j]

R[j-1]

R[j]=R[j-1]; R[j-1]=temp; }}}26/63冒泡排序算法27/63下標(biāo)當(dāng)i=1時(shí)將最小值1冒泡到頂端192135485367748692915837426915837246915832746915823746915283746912583746192583746采用前面的冒泡排序方法對(duì)(9,1,5,8,3,7,4,6,2)進(jìn)行排序28/63112932455863778496下標(biāo)192583476192538476192358476129358476當(dāng)i=2時(shí)將次小值2冒泡到第二位置采用前面的冒泡排序方法對(duì)(9,1,5,8,3,7,4,6,2)進(jìn)行排序voidBubbleSort(RecTypeR[]，intn){inti，j;boolexchange;RecTypetemp;for(i=0;i<n-1;i++){exchange=false;for(j=n-1;j>i;j--)

//比較，找出最小關(guān)鍵字的記錄

if(R[j].key<R[j-1].key) {temp=R[j];R[j]=R[j-1];R[j-1]=temp;exchange=true; }if(exchange==false)return;//中途結(jié)束算法

}}29/63改進(jìn)冒泡排序算法：最好的情況（關(guān)鍵字在記錄序列中正序）：只需進(jìn)行一趟冒泡最壞的情況（關(guān)鍵字在記錄序列中反序）：需進(jìn)行n-1趟冒泡0“移動(dòng)”的次數(shù)：“比較”的次數(shù)：n-1“比較”的次數(shù)：“移動(dòng)”的次數(shù)：所以冒泡排序最好時(shí)間復(fù)雜度為O(n)，最壞和平均為O(n2)。算法分析30/63無序的記錄序列無序子序列

無序子序列

基準(zhǔn)一次劃分分別進(jìn)行快速排序每趟使表的第1個(gè)元素放入適當(dāng)位置（歸位），將表一分為二，對(duì)子表按遞歸方式繼續(xù)這種劃分，直至劃分的子表長(zhǎng)為0或1（遞歸出口）?；鶞?zhǔn)31/639.3.2快速排序31542tmpiji=j：區(qū)間處理完畢劃分完畢整個(gè)區(qū)間：R[s..t]左區(qū)間：R[s..i-1]右區(qū)間：R[i+1..t]32/63回顧劃分：示例voidQuickSort(RecTypeR[]，ints，intt)//對(duì)R[s]至R[t]的元素進(jìn)行快速排序{inti=s，j=t;RecTypetmp;if(s<t) //區(qū)間內(nèi)至少存在2個(gè)元素的情況

{tmp=R[s]; //用區(qū)間的第1個(gè)記錄作為基準(zhǔn)

while(i!=j) //兩端交替向中間掃描，直至i=j為止

{while(j>i&&R[j].key>=tmp.key)j--; R[i]=R[j];while(i<j&&R[i].key<=tmp.key)i++; R[j]=R[i];}R[i]=tmp;QuickSort(R，s，i-1); //對(duì)左區(qū)間遞歸排序

QuickSort(R，i+1，t); //對(duì)右區(qū)間遞歸排序

}//遞歸出口：不需要任何操作}一次劃分33/63快速排序算法設(shè)待排序的表有10個(gè)記錄，其關(guān)鍵字分別為（52,49,80,36,14,75,58,97,23,61）。說明采用快速排序方法進(jìn)行排序的過程。34/63示例經(jīng)第1趟快速排序之后為(23,49,14,36)52(75,58,97,80,61)，經(jīng)第2趟快速排序之后為(14)23(49,36)52(61,58)75(80,97)，經(jīng)第3趟快速排序之后為(14,23,36,49,52,58,61,75,80,97)采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是（）。A.遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B.每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)C.每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D.遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)說明：本題為2010年全國(guó)考研題35/63示例為實(shí)現(xiàn)快速排序法，待排序序列宜采用存儲(chǔ)方式是（）。A.順序存儲(chǔ) B.散列存儲(chǔ)C.鏈?zhǔn)酱鎯?chǔ) D.索引存儲(chǔ)說明：本題為2011年全國(guó)考研題36/63示例最好情況：n個(gè)元素……

log2n

層此時(shí)時(shí)間復(fù)雜度為O(nlog2n)，空間復(fù)雜度為O(log2n)。n/2或n/2-1個(gè)元素n/2或n/2-1個(gè)元素劃分時(shí)間為O(n)37/63算法分析n個(gè)元素n-1個(gè)元素n-2個(gè)元素┇n層此時(shí)時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(n)。劃分時(shí)間為O(n)38/63最壞情況：結(jié)論:快速排序的平均時(shí)間復(fù)雜度為O(nlog2n)。平均所需?？臻g為O(log2n)。1次劃分的時(shí)間則可得結(jié)果：

Tavg(n)=Cnlog2n。n個(gè)元素k-1個(gè)元素n-k個(gè)元素k：1~n，共有n種情況由此可得快速排序所需時(shí)間的平均值為：平均情況：劃分時(shí)間為O(n)39/63常見的選擇排序方法：（1）簡(jiǎn)單選擇排序（或稱直接選擇排序）（2）堆排序基本思路全局有序區(qū)無序區(qū)選出最小記錄R[k]40/639.4選擇排序從a[i..n-1]中選出最小元素：intMin(inta[]，intn，inti){intk=i，j; //k保存最小元素的下標(biāo)for(j=i+1;j<n;j++)

if(a[j]<a[k])k=j;

returna[k];}簡(jiǎn)單選擇n個(gè)記錄中找最小記錄需要n-1次比較41/639.4.1簡(jiǎn)單選擇排序全局有序區(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]采用簡(jiǎn)單選擇方法選出最小記錄初始時(shí)，全局有序區(qū)為空i＝0~n-2，共經(jīng)過n-1趟排序42/63基本思路voidSelectSort(RecTypeR[]，intn){inti，j，k;RecTypetmp;for(i=0;i<n-1;i++)

//做第i趟排序

{k=i;for(j=i+1;j<n;j++) if(R[j].key<R[k].key)

k=j;

if(k!=i)

//R[i]

R[k]{tmp=R[i];R[i]=R[k];R[k]=tmp;}}}在R[i..n-1]中采用簡(jiǎn)單選擇方法選出最小的R[k]43/63簡(jiǎn)單選擇排序算法初始關(guān)鍵字2134512345i=012345i=112345i=212345i=3采用簡(jiǎn)單選擇排序方法對(duì)(2，1，3，4，5)進(jìn)行排序任何情況下：都有做n-1趟沒有記錄移動(dòng)44/63移動(dòng)記錄的次數(shù)，正序?yàn)樽钚≈?，反序?yàn)樽畲笾?(n-1)。

對(duì)n

個(gè)記錄進(jìn)行簡(jiǎn)單選擇排序，所需進(jìn)行的關(guān)鍵字的比較次數(shù)總計(jì)為：簡(jiǎn)單選擇排序的最好、最壞和平均時(shí)間復(fù)雜度為O(n2)。從i個(gè)記錄中挑選最小記錄需要比較i-1次。第i（i=0～n-2）趟從n-i記錄中挑選最小記錄需要比較n-i-1。45/63算法分析全局有序區(qū)無序區(qū)選出最小記錄R[k]采用堆方法選出最小記錄：堆排序算法基本思路46/639.4.2堆排序一個(gè)序列R[1..n]，關(guān)鍵字分別為k1、k2、、kn。該序列滿足如下性質(zhì)（簡(jiǎn)稱為堆性質(zhì)）：

ki≤k2i

且ki≤k2i+1

或

ki≥k2i

且ki≥k2i+1 （1≤i≤

n/2）

滿足第

種情況的堆稱為小根堆，滿足第

種情況的堆稱為大根堆。下面討論的堆是大根堆。47/631、堆的定義a1a2a3an…完全二叉樹i2i2i+1左孩子右孩子大根堆：對(duì)應(yīng)的完全二叉樹中，任意一個(gè)結(jié)點(diǎn)的關(guān)鍵字都大于或等于它的孩子結(jié)點(diǎn)的關(guān)鍵字。

最小關(guān)鍵字的記錄一定是某個(gè)葉子結(jié)點(diǎn)?。。有蚓幪?hào)方式：a1

a2…an

將序列a1

a2…an看成是一顆完全二叉樹48/631295413n=6如何判斷一顆完全二叉樹是否為大根堆124356從編號(hào)為n/2=3的結(jié)點(diǎn)開始，逐一判斷所有分支結(jié)點(diǎn)所有分支結(jié)點(diǎn)滿足定義

為大根堆49/63

堆排序的關(guān)鍵是構(gòu)造堆，這里采用篩選算法建堆。所謂“篩選”指的是，對(duì)一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點(diǎn)使整個(gè)二叉樹也成為一個(gè)堆。堆堆篩選堆篩選50/632、堆排序算法設(shè)計(jì)295413是一個(gè)堆是一個(gè)堆

篩選：不是堆

堆從根開始篩選大根堆僅僅處理從根結(jié)點(diǎn)

某個(gè)葉子結(jié)點(diǎn)路徑上的結(jié)點(diǎn)n個(gè)結(jié)點(diǎn)的完全二叉樹高度為

log2(n+1)

所有篩選的時(shí)間復(fù)雜度為O(log2n)tmp51/63low2*low2*low+1……h(huán)igh…sift(RecTypeR[]，intlow，inthigh)：R[low..high]R[low..high]根最后結(jié)點(diǎn)52/63篩選算法voidsift(RecTypeR[]，intlow，inthigh) //調(diào)整堆的算法{inti=low，j=2*i; //R[j]是R[i]的左孩子

RecTypetmp=R[i];while(j<=high){if(j<high&&R[j].key<R[j+1].key)j++;if(tmp.key<R[j].key)//雙親小{R[i]=R[j];//將R[j]調(diào)整到雙親結(jié)點(diǎn)位置i=j;//修改i和j值，以便繼續(xù)向下篩選j=2*i;}elsebreak;//雙親大：不再調(diào)整}R[i]=tmp;}j指向大孩子53/63篩選或調(diào)整算法：

一顆完全二叉樹

初始堆435216124356例如，序列：（4，3，5，2，1，6）n=6從編號(hào)為n/2=3的結(jié)點(diǎn)開始，逐一篩選65546初始堆:（6，3，5，2，1，4）for(i=n/2;i>=1;i--)//循環(huán)建立初始堆

sift(R，i，n);最大記錄篩選步驟：sift(R，3，6)sift(R，2，6)sift(R，1，6)54/63635214124356

最大記錄歸位4，3，5，2，1，6最大記錄6歸位R[1]R[i]4352112435654R[1]R[i-1]再對(duì)R[1..i-1]的記錄進(jìn)行篩選55/63voidHeapSort(RecTypeR[]，intn){inti;RecTypetmp;for(i=n/2;i>=1;i--) //循環(huán)建立初始堆

sift(R，i，n);for(i=n;i>=2;i--) //進(jìn)行n-1次循環(huán)，完成推排序

{temp=R[1]; //R[1]

R[i]

R[1]=R[i];R[i]=tmp;sift(R，1，