排序概念市公開課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

第9章排序排序概念第1頁9.1排序概念排序概念第2頁排序（sort）或分類

所謂排序，就是要整理文件中統(tǒng)計(jì)，使之按關(guān)鍵字遞增(或遞減)次序排列起來。其確切定義以下：

輸入：n個(gè)統(tǒng)計(jì)R1，R2，…，Rn，其對應(yīng)關(guān)鍵字分別為K1，K2，…，Kn。

輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

排序概念第3頁2．排序運(yùn)算依據(jù)--關(guān)鍵字

用來作排序運(yùn)算依據(jù)關(guān)鍵字，能夠是數(shù)字類型，也能夠是字符類型。

關(guān)鍵字選取應(yīng)依據(jù)問題要求而定。

【例】在高考成績統(tǒng)計(jì)中將每個(gè)考生作為一個(gè)統(tǒng)計(jì)。每條統(tǒng)計(jì)包含準(zhǔn)考證號、姓名、各科分?jǐn)?shù)和總分?jǐn)?shù)等項(xiàng)內(nèi)容。若要惟一地標(biāo)識一個(gè)考生統(tǒng)計(jì)，則必須用"準(zhǔn)考證號"作為關(guān)鍵字。若要按照考生總分?jǐn)?shù)排名次，則需用"總分?jǐn)?shù)"作為關(guān)鍵字。

排序概念第4頁排序穩(wěn)定性當(dāng)待排序統(tǒng)計(jì)關(guān)鍵字均不相同時(shí)，排序結(jié)果是惟一，不然排序結(jié)果不唯一。

在待排序文件中，若存在多個(gè)關(guān)鍵字相同統(tǒng)計(jì)，經(jīng)過排序后這些含有相同關(guān)鍵字統(tǒng)計(jì)之間相對次序保持不變，該排序方法是穩(wěn)定；若含有相同關(guān)鍵字統(tǒng)計(jì)之間相對次序發(fā)生改變，則稱這種排序方法是不穩(wěn)定。

排序概念第5頁01姓名9802850376049805100排序概念第6頁注意：排序算法穩(wěn)定性是針對全部輸入實(shí)例而言。即在全部可能輸入實(shí)例中，只要有一個(gè)實(shí)例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定。

排序概念第7頁排序方法分類1．按是否包括數(shù)據(jù)內(nèi)、外存交換分

在排序過程中，若整個(gè)文件都是放在內(nèi)存中處理，排序時(shí)不包括數(shù)據(jù)內(nèi)、外存交換，則稱之為內(nèi)部排序(簡稱內(nèi)排序)；反之，若排序過程中要進(jìn)行數(shù)據(jù)內(nèi)、外存交換，則稱之為外部排序。

注意：

①內(nèi)排序適合用于統(tǒng)計(jì)個(gè)數(shù)不很多小文件

②外排序則適合用于統(tǒng)計(jì)個(gè)數(shù)太多，不能一次將其全部統(tǒng)計(jì)放人內(nèi)存大文件。

排序概念第8頁內(nèi)1內(nèi)2內(nèi)3內(nèi)4內(nèi)5外1外2排序概念第9頁2．按策略劃分內(nèi)部排序方法能夠分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。排序概念第10頁按性能分類簡單排序算法：性能o(n2)復(fù)雜排序算法：性能o(nlog2n)排序概念第11頁排序算法分析1．排序算法基本操作

大多數(shù)排序算法都有兩個(gè)基本操作：

(1)比較兩個(gè)關(guān)鍵字大?。?/p>

(2)改變指向統(tǒng)計(jì)指針或移動統(tǒng)計(jì)本身。

注意：

temp=a[i];a[i]=a[i+1];a[i+1]=tem

第(2)種基本操作實(shí)現(xiàn)依賴于待排序統(tǒng)計(jì)存放方式。

排序概念第12頁2．待排文件慣用存放方式（1）以次序表(或直接用向量)作為存放結(jié)構(gòu)

排序過程：對統(tǒng)計(jì)本身進(jìn)行物理重排（即經(jīng)過關(guān)鍵字之間比較判定，將統(tǒng)計(jì)移到適當(dāng)位置）

（2）以鏈表作為存放結(jié)構(gòu)

排序過程：無須移動統(tǒng)計(jì)，僅需修改指針。通常將這類排序稱為鏈表(或鏈?zhǔn)?排序；

（3）用次序方式存放待排序統(tǒng)計(jì)，但同時(shí)建立一個(gè)輔助表(如包含關(guān)鍵字和指向統(tǒng)計(jì)位置指針組成索引表)

排序過程：只需對輔助表表目進(jìn)行物理重排（即只移動輔助表表目，而不移動統(tǒng)計(jì)本身）。適合用于難于在鏈表上實(shí)現(xiàn)，仍需防止排序過程中移動統(tǒng)計(jì)排序方法。排序概念第13頁用索引表實(shí)現(xiàn)排序b[0]b[1]4078212502836345948955628673774538501965a[10]b[10]排序概念第14頁3．排序算法性能評價(jià)（1）評價(jià)排序算法好壞標(biāo)準(zhǔn)

評價(jià)排序算法好壞標(biāo)準(zhǔn)主要有兩條：

①執(zhí)行時(shí)間和所需輔助空間

②算法本身復(fù)雜程度

（2）排序算法空間復(fù)雜度

若排序算法所需輔助空間并不依賴于問題規(guī)模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。

非就地排序普通要求輔助空間為O(n)。

（3）排序算法時(shí)間開銷

大多數(shù)排序算法時(shí)間開銷主要是關(guān)鍵字之間比較和統(tǒng)計(jì)移動。有排序算法其執(zhí)行時(shí)間不但依賴于問題規(guī)模，還取決于輸入實(shí)例中數(shù)據(jù)狀態(tài)。排序概念第15頁文件次序存放結(jié)構(gòu)表示#definenl00//假設(shè)文件長度，即待排序統(tǒng)計(jì)數(shù)目typedefStudinfoInfoType;

typedefintKeyType；//假設(shè)關(guān)鍵字類型

typedefstruct{//統(tǒng)計(jì)類型

KeyTypekey；//關(guān)鍵字項(xiàng)

InfoTypeotherinfo；//其它數(shù)據(jù)項(xiàng)，類型InfoType依賴于詳細(xì)應(yīng)用而定義

}RecType；

typedefRecTypeSeqList[n+1]；//SeqList為次序表類型，表中第0個(gè)單元普通用作哨兵排序概念第16頁9.2插入法排序插入排序(InsertionSort)基本思想是：每次將一個(gè)待排序統(tǒng)計(jì)，按其關(guān)鍵字大小插入到前面已經(jīng)排好序數(shù)組中適當(dāng)位置，直到全部統(tǒng)計(jì)插入完成為止。

本節(jié)介紹兩種插入排序方法：直接插入排序和希爾排序。排序概念第17頁直接插入排序基本思想1、基本思想

假設(shè)待排序統(tǒng)計(jì)存放在數(shù)組R[1..n]中。初始時(shí)，R[1]自成1個(gè)有序區(qū)，無序區(qū)為R[2..n]。從i=2起直至i=n為止，依次將R[i]插入當(dāng)前有序區(qū)R[1..i-1]中，生成含n個(gè)統(tǒng)計(jì)有序區(qū)。

排序概念第18頁排序概念第19頁012345672623547421103923265474211039i=2i=7jjjji3551217排序概念第20頁for(i=2;i<=n;i++){在1到i-1之間找到一個(gè)適當(dāng)位置把a(bǔ)[i]插入到這個(gè)適當(dāng)位置}排序概念第21頁2、第i-1趟直接插入排序：

通常將一個(gè)統(tǒng)計(jì)R[i](i=2，3，…，n-1)插入到當(dāng)前有序區(qū)，使得插入后仍確保該區(qū)間里統(tǒng)計(jì)是按關(guān)鍵字有序操作稱第i-1趟直接插入排序。

排序過程某一中間時(shí)刻，R被劃分成兩個(gè)子區(qū)間R[1．．i-1]（已排好序有序區(qū)）和R[i．．n]（當(dāng)前未排序部分，可稱無序區(qū)）。

直接插入排序基本操作是將當(dāng)前無序區(qū)第1個(gè)統(tǒng)計(jì)R[i]插人到有序區(qū)R[1．．i-1]中適當(dāng)位置上，使R[1．．i]變?yōu)樾掠行騾^(qū)。因?yàn)檫@種方法每次使有序區(qū)增加1個(gè)統(tǒng)計(jì)，通常稱增量法。

排序概念第22頁2．改進(jìn)方法一個(gè)查找比較操作和統(tǒng)計(jì)移動操作交替地進(jìn)行方法。

詳細(xì)做法：

將待插入統(tǒng)計(jì)R[i]關(guān)鍵字從右向左依次與有序區(qū)中統(tǒng)計(jì)R[j](j=i-1，i-2，…，1)關(guān)鍵字進(jìn)行比較：

①若R[j]關(guān)鍵字大于R[i]關(guān)鍵字，則將R[j]后移一個(gè)位置；

②若R[j]關(guān)鍵字小于或等于R[i]關(guān)鍵字，則查找過程結(jié)束，j+1即為R[i]插入位置。

關(guān)鍵字比R[i]關(guān)鍵字大統(tǒng)計(jì)均已后移，所以j+1位置已經(jīng)騰空，只要將R[i]直接插入此位置即可完成一趟直接插入排序。排序概念第23頁直接插入排序算法1．算法描述

voidlnsertSort(SeqListR)

{//對次序表R中統(tǒng)計(jì)R[1..n]按遞增序進(jìn)行插入排序

inti，j；

for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]

if(R[i].key<R[i-1].key){//若R[i].key大于等于有序區(qū)中全部keys，則R[i]

//應(yīng)在原有位置上

R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]副本

do{//從右向左在有序區(qū)R[1．．i-1]中查找R[i]插入位置

R[j+1]=R[j]；//將關(guān)鍵字大于R[i].key統(tǒng)計(jì)后移

j--；

}while(R[0].key<R[j].key)；//當(dāng)R[i].key≥R[j].key時(shí)終止

R[j+1]=R[0]；13//R[i]插入到正確位置上

}//endif

}//InsertSort排序概念第24頁直接插入排序算法1．算法描述

voidlnsertSort(SeqListR)

{//對次序表R中統(tǒng)計(jì)R[1..n]按遞增序進(jìn)行插入排序

inti，j；

for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]

if(R[i].key<R[i-1].key){//若R[i].key大于等于有序區(qū)中全部keys，則R[i]

//應(yīng)在原有位置上

R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]副本

do{//從右向左在有序區(qū)R[1．．i-1]中查找R[i]插入位置

R[j+1]=R[j]；//將關(guān)鍵字大于R[i].key統(tǒng)計(jì)后移

j--；

}while(R[0].key<R[j].key)；//當(dāng)R[i].key≥R[j].key時(shí)終止

R[j+1]=R[0]；13//R[i]插入到正確位置上

}//endif

}//InsertSort排序概念第25頁直接插入排序算法1．算法描述main()voidlnsertSort(SeqListR)

{

inti，j；

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

if(R[i].key<R[i-d].key){

R[0]=R[i];j=i-d;

do{

R[j+d]=R[j]；

j=j-d；

}while(j>0&&R[0].key<R[j].key)；

R[j+d]=R[0]；

}

}排序概念第26頁voidf1(inta[2]){a[0]=23;a[1]=100;}main(){intb[2]={18,10};f1(b);pritnf(}排序概念第27頁2．哨兵作用

算法中引進(jìn)附加統(tǒng)計(jì)R[0]稱監(jiān)視哨或哨兵(Sentinel)。

哨兵有兩個(gè)作用：

①進(jìn)人查找(插入位置)循環(huán)之前，它保留了R[i]副本，使不致于因統(tǒng)計(jì)后移而丟失R[i]內(nèi)容；

②它主要作用是：在查找循環(huán)中"監(jiān)視"下標(biāo)變量j是否越界。一旦越界(即j=0)，因?yàn)镽[0].key和自己比較，循環(huán)判定條件不成立使得查找循環(huán)結(jié)束，從而防止了在該循環(huán)內(nèi)每一次均要檢測j是否越界(即省略了循環(huán)判定條件"j>=1")。

注意：

①實(shí)際上，一切為簡化邊界條件而引入附加結(jié)點(diǎn)(元素)均可稱為哨兵。

【例】單鏈表中頭結(jié)點(diǎn)實(shí)際上是一個(gè)哨兵

②引入哨兵后使得測試查找循環(huán)條件時(shí)間大約降低了二分之一，所以對于統(tǒng)計(jì)數(shù)較大文件節(jié)約時(shí)間就相當(dāng)可觀。對于類似于排序這么使用頻率非常高算法，要盡可能地降低其運(yùn)行時(shí)間。所以不能把上述算法中哨兵視為雕蟲小技，而應(yīng)該深刻了解并掌握這種技巧排序概念第28頁排序過程示例次數(shù)R[0]R[1]R[2]R[3]R[4]R[5]R[6]R[7]R[8]初始710132025304255排序概念第29頁算法性能分析最壞情形排序概念第30頁排序概念第31頁最好情形(原來已經(jīng)排序好）Cmin=n-1=O(n)Mmin=0=O(1)平均情況C=O(n2)M=O(直接插入法排序最大特點(diǎn)，當(dāng)原來已經(jīng)排序好(基本上已經(jīng)排序好），則速度最快，當(dāng)原來序列大致已排序好時(shí)，也比較快。排序概念第32頁注意：

初始文件按關(guān)鍵字遞增有序，簡稱"正序"。

初始文件按關(guān)鍵字遞減有序，簡稱"反序"。

排序概念第33頁9.2.2希爾排序(ShellSort)

希爾排序(ShellSort)是插入排序一個(gè)。因D．L．Shell于1959年提出而得名。

希爾排序基本思想

基本思想：

先取一個(gè)小于n整數(shù)d1作為第一個(gè)增量，把文件全部統(tǒng)計(jì)分成d1個(gè)組。全部距離為dl倍數(shù)統(tǒng)計(jì)放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個(gè)增量d2<d1重復(fù)上述分組和排序，直至所取增量dt=1(dt<dt-l<…<d2<d1)，即全部統(tǒng)計(jì)放在同一組中進(jìn)行直接插入排序?yàn)橹埂?/p>

該方法實(shí)質(zhì)上是一個(gè)分組插入方法。

給定實(shí)例shell排序排序過程

假設(shè)待排序文件有10個(gè)統(tǒng)計(jì)，其關(guān)鍵字分別是：

49，38，65，97，76，13，27，49，55，04。

增量序列取值依次為：

5，3，1排序概念第34頁Shell排序算法實(shí)現(xiàn)1．不設(shè)監(jiān)視哨算法描述

voidShellPass(SeqListR，intd)

{//希爾排序中一趟排序，d為當(dāng)前增量

for(i=d+1;i<=n；i++)//將R[d+1．．n]分別插入各組當(dāng)前有序區(qū)

if(R[i].key<R[i-d].key){

R[0]=R[i];j=i-d；//R[0]只是暫存單元，不是哨兵

do{//查找R[i]插入位置

R[j+d]=R[j]；//后移統(tǒng)計(jì)

j=j-d；//查找前一統(tǒng)計(jì)

}while(j>0&&R[0].key<R[j].key)；

R[j+d]=R[0]；//插入R[i]到正確位置上

}//endif

}//ShellPass

void

ShellSort(SeqListR){intincrement=n；//增量初值，不妨設(shè)n>0

do{

increment=increment/3+1；//求下一增量

ShellPass(R，increment)；//一趟增量為incrementShell插入排序

}while(increment>1)

}//ShellSort排序概念第35頁

分析排序概念第36頁次數(shù)R[0]R[1]R[2]R[3]R[4]R[5]R[6]R[7]R[8]初始4938659776132749550413132749550449386597768132749550449386597765311304493827495565977604232738494955657697排序概念第37頁shell排序算法性能分析時(shí)間復(fù)雜度為=O(nlog2n)<O(n2)算法不穩(wěn)定排序概念第38頁2．算法空間復(fù)雜度分析

算法所需輔助空間是一個(gè)監(jiān)視哨，輔助空間復(fù)雜度S(n)=O(1)。是一個(gè)就地排序。

3．直接插入排序穩(wěn)定性

直接插入排序是穩(wěn)定排序方法。排序概念第39頁8.3交換排序交換排序基本思想是：兩兩比較待排序統(tǒng)計(jì)關(guān)鍵字，發(fā)覺兩個(gè)統(tǒng)計(jì)次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序統(tǒng)計(jì)為止。

應(yīng)用交換排序基本思想主要排序方法有：冒泡排序和快速排序。

排序概念第40頁8.3.1冒泡排序1、排序方法

將被排序統(tǒng)計(jì)數(shù)組R[1..n]垂直排列，每個(gè)統(tǒng)計(jì)R[i]看作是重量為R[i].key氣泡。依據(jù)輕氣泡不能在重氣泡之下標(biāo)準(zhǔn)，從下往上掃描數(shù)組R：凡掃描到違反本標(biāo)準(zhǔn)輕氣泡，就使其向上"飄浮"。如此重復(fù)進(jìn)行，直到最終任何兩個(gè)氣泡都是輕者在上，重者在下為止。

排序概念第41頁（2）第一趟掃描從無序區(qū)底部向上依次比較相鄰兩個(gè)氣泡重量，若發(fā)覺輕者在下、重者在上，則交換二者位置。即依次比較(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；對于每對氣泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，則交換R[j+1]和R[j]內(nèi)容。

第一趟掃描完成時(shí)，"最輕"氣泡就飄浮到該區(qū)間頂部，即關(guān)鍵字最小統(tǒng)計(jì)被放在最高位置R[1]上。

排序概念第42頁（3）第二趟掃描掃描R[2..n]。掃描完成時(shí)，"次輕"氣泡飄浮到R[2]位置上……

最終，經(jīng)過n-1

趟掃描可得到有序區(qū)R[1..n]

排序概念第43頁規(guī)律n個(gè)數(shù)n-1趟第1趟比較n-1次第2趟比較n-2次第i趟比較n-i第n-1趟比較1次for(i=1;i<=n-1;i++)for(j=0;j<n-i;j++)if(a[j]>a[j+1]){a[j]與a[j+1]交換;}排序概念第44頁排序示例趟14938383838384949494965656527272727276549494949496514233241排序概念第45頁排序示例1513131517172525343487545497979787排序概念第46頁（2）詳細(xì)算法voidBubbleSort(SeqListR){//R（l..n)是待排序文件，采取自下向上掃描，對R做冒泡排序

inti，j；

Booleanexchange；//交換標(biāo)志

for(i=1;i<n;i++){//最多做n-1趟排序

exchange=FALSE；//本趟排序開始前，交換標(biāo)志應(yīng)為假

for(j=n-1;j>i；j--)//對當(dāng)前無序區(qū)R[i..n]自下向上掃描

if(R[j+1].key<R[j].key){//交換統(tǒng)計(jì)

temp=R[j+1]；//R[0]不是哨兵，僅做暫存單元

R[j+1]=R[j]；

R[j]=temp；

exchange=TRUE；//發(fā)生了交換，故將交換標(biāo)志置為真

}

if(exchange==FALSE)//本趟排序未發(fā)生交換，提前終止算法

return；

}//endfor(外循環(huán))

}//BubbleSort排序概念第47頁4、算法分析（1）算法最好時(shí)間復(fù)雜度

若文件初始狀態(tài)是正序，一趟掃描即可完成排序。所需關(guān)鍵字比較次數(shù)C和統(tǒng)計(jì)移動次數(shù)M均到達(dá)最小值：

Cmin=n-1

Mmin=0。

冒泡排序最好時(shí)間復(fù)雜度為O(n)。

排序概念第48頁（2）算法最壞時(shí)間復(fù)雜度

若初始文件是反序，需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i次關(guān)鍵字比較(1≤i≤n-1)，且每次比較都必須移動統(tǒng)計(jì)三次來到達(dá)交換統(tǒng)計(jì)位置。在這種情況下，比較和移動次數(shù)均到達(dá)最大值：

Cmax=n(n-1)/2=O(n2)

Mmax=3n(n-1)/2=O(n2)

冒泡排序最壞時(shí)間復(fù)雜度為O(n2)。

排序概念第49頁（2）算法最壞時(shí)間復(fù)雜度若初始文件是反序，需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i次關(guān)鍵字比較(1≤i≤n-1)，且每次比較都必須移動統(tǒng)計(jì)三次來到達(dá)交換統(tǒng)計(jì)位置。在這種情況下，比較和移動次數(shù)均到達(dá)最大值：

Cmax=n(n-1)/2=O(n2)

Mmax=3n(n-1)/2=O(n2)

冒泡排序最壞時(shí)間復(fù)雜度為O(n2)。

排序概念第50頁（3）算法平均時(shí)間復(fù)雜度為O(n2)

即使冒泡排序不一定要進(jìn)行n-1趟，但因?yàn)樗y(tǒng)計(jì)移動次數(shù)較多，故平均時(shí)間性能比直接插入排序要差得多。

排序概念第51頁（4）算法穩(wěn)定性

冒泡排序是就地排序，且它是穩(wěn)定。

排序概念第52頁(1)記住最終一次交換發(fā)生位置lastExchange冒泡排序

在每趟掃描中，記住最終一次交換發(fā)生位置lastExchange，（該位置之前相鄰統(tǒng)計(jì)均已經(jīng)有序）。下一趟排序開始時(shí)，R[1..lastExchange-1]是有序區(qū)，R[lastExchange..n]是無序區(qū)。這么，一趟排序可能使當(dāng)前有序區(qū)擴(kuò)充多個(gè)統(tǒng)計(jì)，從而降低排序趟數(shù)。詳細(xì)算法【參見習(xí)題】。

(2)改變掃描方向冒泡排序

①冒泡排序不對稱性

能一趟掃描完成排序情況：

只有最輕氣泡位于R[n]位置，其余氣泡均已排好序，那么也只需一趟掃描就能夠完成排序。

【例】對初始關(guān)鍵字序列12，18，42，44，45，67，94，10就僅需一趟掃描。

需要n-1趟掃描完成排序情況：

當(dāng)只有最重氣泡位于R[1]位置，其余氣泡均已排好序時(shí)，則仍需做n-1趟掃描才能完成排序。

排序概念第53頁9.3.2快速排序(QuickSort)1、算法思想

快速排序是C.R.A.Hoare于1962年提出一個(gè)劃分交換排序。它采取了一個(gè)分治策略，通常稱其為分治法(Divide-and-ConquerMethod)。

（1）分治法基本思想

分治法基本思想是：將原問題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問題相同子問題。遞歸地解這些子問題，然后將這些子問題解組合為原問題解。排序概念第54頁（2）快速排序基本思想

設(shè)當(dāng)前待排序無序區(qū)為R[low..high]，利用分治法可將快速排序基本思想描述為：

①分解：

在R[low..high]中任選一個(gè)統(tǒng)計(jì)作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左、右兩個(gè)較小子區(qū)間R[low..pivotpos-1)和R[pivotpos+1..high]，并使左邊子區(qū)間中全部統(tǒng)計(jì)關(guān)鍵字均小于等于基準(zhǔn)統(tǒng)計(jì)(不妨記為pivot)關(guān)鍵字pivot.key，右邊子區(qū)間中全部統(tǒng)計(jì)關(guān)鍵字均大于等于pivot.key，而基準(zhǔn)統(tǒng)計(jì)pivot則位于正確位置(pivotpos)上，它無須參加后續(xù)排序。排序概念第55頁②求解：

經(jīng)過遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

③組合：

因?yàn)楫?dāng)"求解"步驟中兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已經(jīng)有序。對快速排序而言，"組合"步驟無須做什么，可看作是空操作。

排序概念第56頁2、快速排序算法QuickSort

voidQuickSort(SeqListR，intlow，inthigh)

{//對R[low..high]快速排序

intpivotpos；//劃分后基準(zhǔn)統(tǒng)計(jì)位置

if(low<high){//僅當(dāng)區(qū)間長度大于1時(shí)才須排序

pivotpos=Partition(R，low，high)；//對R[low..high]做劃分

QuickSort(R，low，pivotpos-1)；//對左區(qū)間遞歸排序

QuickSort(R，pivotpos+1，high)；//對右區(qū)間遞歸排序

}

}//QuickSort

排序概念第57頁3、劃分算法Partition（1）簡單劃分方法

①詳細(xì)做法

第一步：(初始化)設(shè)置兩個(gè)指針i和j，它們初值分別為區(qū)間下界和上界，即i=low，i=high；選取無序區(qū)第一個(gè)統(tǒng)計(jì)R[i](即R[low])作為基準(zhǔn)統(tǒng)計(jì)，并將它保留在變量pivot中；

第二步：令j自high起向左掃描，直到找到第1個(gè)關(guān)鍵字小于pivot.key統(tǒng)計(jì)R[j]，將R[j])移至i所指位置上，這相當(dāng)于R[j]和基準(zhǔn)R[i](即pivot)進(jìn)行了交換，使關(guān)鍵字小于基準(zhǔn)關(guān)鍵字pivot.key統(tǒng)計(jì)移到了基準(zhǔn)左邊，交換后R[j]中相當(dāng)于是pivot；然后，令i指針自i+1位置開始向右掃描，直至找到第1個(gè)關(guān)鍵字大于pivot.key統(tǒng)計(jì)R[i]，將R[i]移到i所指位置上，這相當(dāng)于交換了R[i]和基準(zhǔn)R[j]，使關(guān)鍵字大于基準(zhǔn)關(guān)鍵字統(tǒng)計(jì)移到了基準(zhǔn)右邊，交換后R[i]中又相當(dāng)于存放了pivot；接著令指針j自位置j-1開始向左掃描，如此交替改變掃描方向，從兩端各自往中間靠攏，直至i=j時(shí)，i便是基準(zhǔn)pivot最終位置，將pivot放在此位置上就完成了一次劃排序概念第58頁③劃分算法：intPartition(SeqListR，inti，intj){ReceTypepivot=R[i]；while(i<j){

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

j--；

if(i<j)

R[i++]=R[j]；

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

i++；

if(i<j)

R[j--]=R[i];

}//endwhile

R[i]=pivot；

returni；

}//partition排序概念第59頁③劃分算法：intPartition(SeqListR，inti，intj){//調(diào)用Partition(R，low，high)時(shí)，對R[low..high]做劃分，//并返回基準(zhǔn)統(tǒng)計(jì)位置

ReceTypepivot=R[i]；//用區(qū)間第1個(gè)統(tǒng)計(jì)作為基準(zhǔn)‘while(i<j){//從區(qū)間兩端交替向中間掃描，直至i=j為止

while(i<j&&R[j].key>=pivot.key)//pivot相當(dāng)于在位置i上

j--；//從右向左掃描，查找第1個(gè)關(guān)鍵字小于pivot.key統(tǒng)計(jì)R[j]

if(i<j)//表示找到R[j]關(guān)鍵字<pivot.key

R[i++]=R[j]；//相當(dāng)于交換R[i]和R[j]，交換后i指針加1

while(i<j&&R[i].key<=pivot.key)//pivot相當(dāng)于在位置j上

i++；//從左向右掃描，查找第1個(gè)關(guān)鍵字大于pivot.key統(tǒng)計(jì)R[i]

if(i<j)//表示找到了R[i]，使R[i].key>pivot.key

R[j--]=R[i];//相當(dāng)于交換R[i]和R[j]，交換后j指針減1

}//endwhile

R[i]=pivot；//基準(zhǔn)統(tǒng)計(jì)已被最終定位

returni；

}//partition排序概念第60頁4、快速排序執(zhí)行過程排序概念第61頁快速遞歸過程排序概念第62頁6、算法分析快速排序時(shí)間主要花費(fèi)在劃分操作上，對長度為k區(qū)間進(jìn)行劃分，共需k-1次關(guān)鍵字比較。排序概念第63頁（1）最壞時(shí)間復(fù)雜度

最壞情況是每次劃分選取基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最小(或最大)統(tǒng)計(jì)，劃分結(jié)果是基準(zhǔn)左邊子區(qū)間為空(或右邊子區(qū)間為空)，而劃分所得另一個(gè)非空子區(qū)間中統(tǒng)計(jì)數(shù)目，僅僅比劃分前無序區(qū)中統(tǒng)計(jì)個(gè)數(shù)降低一個(gè)。

所以，快速排序必須做n-1次劃分，第i次劃分開始時(shí)區(qū)間長度為n-i+1，所需比較次數(shù)為n-i(1≤i≤n-1)，故總比較次數(shù)到達(dá)最大值：

Cmax=n(n-1)/2=O(n2)

假如按上面給出劃分算法，每次取當(dāng)前無序區(qū)第1個(gè)統(tǒng)計(jì)為基準(zhǔn)，那么當(dāng)文件統(tǒng)計(jì)已按遞增序(或遞減序)排列時(shí)，每次劃分所取基準(zhǔn)就是當(dāng)前無序區(qū)中關(guān)鍵字最小(或最大)統(tǒng)計(jì)，則快速排序所需比較次數(shù)反而最多。

排序概念第64頁（2）最好時(shí)間復(fù)雜度在最好情況下，每次劃分所取基準(zhǔn)都是當(dāng)前無序區(qū)"中值"統(tǒng)計(jì)，劃分結(jié)果是基準(zhǔn)左、右兩個(gè)無序子區(qū)間長度大致相等?？傟P(guān)鍵字比較次數(shù)：

0(nlgn)

排序概念第65頁9.4選擇法排序選擇排序(SelectionSort)基本思想是：每一趟從待排序統(tǒng)計(jì)中選出關(guān)鍵字最小統(tǒng)計(jì)，次序放在已排好序子文件最終，直到全部統(tǒng)計(jì)排序完成。

慣用選擇排序方法有直接選擇排序和堆排序。

排序概念第66頁直接選擇排序(StraightSelectionSort)1、直接選擇排序基本思想

n個(gè)統(tǒng)計(jì)文件直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：

①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。

②第1趟排序

在無序區(qū)R[1..n]中選出關(guān)鍵字最小統(tǒng)計(jì)R[k]，將它與無序區(qū)第1個(gè)統(tǒng)計(jì)R[1]交換，使R[1..1]和R[2..n]分別變?yōu)榻y(tǒng)計(jì)個(gè)數(shù)增加1個(gè)新有序區(qū)和統(tǒng)計(jì)個(gè)數(shù)降低1個(gè)新無序區(qū)?！?/p>

排序概念第67頁③第i趟排序第i趟排序開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小統(tǒng)計(jì)R[k]，將它與無序區(qū)第1個(gè)統(tǒng)計(jì)R[i]交換，使R[1..i]和R[i+1..n]分別變?yōu)榻y(tǒng)計(jì)個(gè)數(shù)增加1個(gè)新有序區(qū)和統(tǒng)計(jì)個(gè)數(shù)降低1個(gè)新無序區(qū)。

這么，n個(gè)統(tǒng)計(jì)文件直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。排序概念第68頁直接選擇法排序初始4938659776132749第1趟1338659776492749排序概念第69頁3、算法描述voidSelectSort(SeqListR){

inti，j，k；

for(i=1;i<n;i++){//做第i趟排序(1≤i≤n-1)

k=i；

for(j=i+1;j<=n;j++)//在當(dāng)前無序區(qū)R[i..n]中選key最小統(tǒng)計(jì)R[k]

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

k=j;//k記下當(dāng)前找到最小關(guān)鍵字所在位置

if(k!=i){//交換R[i]和R[k]

R[0]=R[i]；R[i]=R[k]；R[k]=R[0]；//R[0]作暫存單元

}//endif

}//endfor

}//SeleetSort排序概念第70頁4、算法分析（1）關(guān)鍵字比較次數(shù)

不論文件初始狀態(tài)怎樣，在第i趟排序中選出最小關(guān)鍵字統(tǒng)計(jì)，需做n-i次比較，所以，總比較次數(shù)為：

n(n-1)/2=0(n2)

（2）統(tǒng)計(jì)移動次數(shù)

當(dāng)初始文件為正序時(shí)，移動次數(shù)為0

文件初態(tài)為反序時(shí)，每趟排序均要執(zhí)行交換操作，總移動次數(shù)取最大值3(n-1)。

直接選擇排序平均時(shí)間復(fù)雜度為O(n2)。

（3）直接選擇排序是一個(gè)就地排序排序概念第71頁（4）穩(wěn)定性分析

直接選擇排序是不穩(wěn)定排序概念第72頁9.4.2堆排序排序概念第73頁1、堆排序定義n個(gè)關(guān)鍵字序列Kl，K2，…，Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足以下性質(zhì)(簡稱為堆性質(zhì))：

(1)ki≤K2i且ki≤K2i+1

或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)

若將此序列所存放向量R[1..n]看做是一棵完全二叉樹存放結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足以下性質(zhì)完全二叉樹：樹中任一非葉結(jié)點(diǎn)關(guān)鍵字均小于(或大于)其左右孩子(若存在)結(jié)點(diǎn)關(guān)鍵字。

排序概念第74頁例【例】關(guān)鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(zhì)(1)和(2)，故它們均是堆，其對應(yīng)完全二叉樹分別如小根堆示例和大根堆示例所表示。

排序概念第75頁示例排序概念第76頁2、大根堆和小根堆根結(jié)點(diǎn)(亦稱為堆頂)關(guān)鍵字是堆里全部結(jié)點(diǎn)關(guān)鍵字中最小者堆稱為小根堆。

根結(jié)點(diǎn)(亦稱為堆頂)關(guān)鍵字是堆里全部結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆。

注意：

①堆中任一子樹亦是堆。

②以上討論堆實(shí)際上是二叉堆(BinaryHeap)，類似地可定義k叉堆排序概念第77頁34，25，72，62，17，53，32,753262327522494917low=425large=8排序概念第78頁3、堆排序特點(diǎn)

堆排序(HeapSort)是一樹形選擇排序。

堆排序特點(diǎn)是：在排序過程中，將R[l..n]看成是一棵完全二叉樹次序存放結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間內(nèi)在關(guān)系【參見二叉樹次序存放結(jié)構(gòu)】，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大(或最小)統(tǒng)計(jì)。

排序概念第79頁5、堆排序

堆排序利用了大根堆(或小根堆)堆頂統(tǒng)計(jì)關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無序區(qū)中選取最大(或最小)關(guān)鍵字統(tǒng)計(jì)變得簡單。排序概念第80頁（1）用大根堆排序基本思想①先將初始文件R[1..n]建成一個(gè)大根堆，此堆為初始無序區(qū)

②再將關(guān)鍵字最大統(tǒng)計(jì)R[1](即堆頂)和無序區(qū)最終一個(gè)統(tǒng)計(jì)R[n]交換，由此得到新無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key

③因?yàn)榻粨Q后新根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大統(tǒng)計(jì)R[1]和該區(qū)間最終一個(gè)統(tǒng)計(jì)R[n-1]交換，由此得到新無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，一樣要將R[1..n-2]調(diào)整為堆。

……

直到無序區(qū)只有一個(gè)元素為止。

排序概念第81頁（2）大根堆排序算法基本操作：①初始化操作：將R[1..n]結(jié)構(gòu)為初始堆；

②每一趟排序基本操作：將當(dāng)前無序區(qū)堆頂統(tǒng)計(jì)R[1]和該區(qū)間最終一個(gè)統(tǒng)計(jì)交換，然后將新無序區(qū)調(diào)整為堆(亦稱重建堆)。排序概念第82頁（3）堆排序算法：

voidHeapSort(SeqListR)

{//對R[1..n]進(jìn)行堆排序，不妨用R[0]做暫存單元

inti；

BuildHeap(R)；//將R[1-n]建成初始堆

for(i=n;i>1；i--){//對當(dāng)前無序區(qū)R[1..i]進(jìn)行堆排序，共做n-1趟。

R[0]=R[1]；R[1]=R[i];R[i]=R[0]；//將堆頂和堆中最終一個(gè)統(tǒng)計(jì)交換

Heapify(R，1，i-1)；//將R[1..i-1]重新調(diào)整為堆，僅有R[1]可能違反堆性質(zhì)

}//endfor

}//HeapSort排序概念第83頁篩選法調(diào)整堆voidHeapify(SeqListR,intlow,inthigh){intlarge;RecTypetemp=R[low];//temp=25for(large=2*low;large<=high;large*=2）//large=16{if(large<high&&R[large].key<R[Large+1].key)large++;if(temp.key>=R[large].key)//25>=75break;R[low]=R[large];low=large;low=8}R[low]=temp;}排序概念第84頁建堆算法voidbuildHeap(SeqListR){inti;

for(i=n/2;i>0;i--)Heapify(R,i,n);//對R進(jìn)行調(diào)整，從i這個(gè)元素開始，到n}排序概念第85頁建堆過程示例(初始)13172324429116051388422324160591排序概念第86頁建堆過程示例(2)

88與23交換后42138824912316054213918824160523排序概念第87頁建堆過程示例(3)

i=3符合要求,不調(diào)整42138824912316054213912324160523排序概念第88頁建堆過程示例(4)

i=213與88調(diào)整42881324912316054288912324160513排序概念第89頁建堆過程示例(5)

i=113與88調(diào)整05882324421316059188422324160513排序概念第90頁調(diào)整過程O(nlog2n)O(n2)排序概念第91頁初始狀態(tài)91884924491342059188422324160513排序概念第92頁調(diào)整(1)13882324429116059188422324160513排序概念第93頁調(diào)整(1A)88132324429116059188422324160513排序概念第94頁調(diào)整(1B)88242313429116059188422324160513排序概念第95頁效率或時(shí)間復(fù)雜度O(nlog2n)8個(gè)隊(duì)，按循環(huán)賽，要進(jìn)行多少場比賽。8排序概念第96頁9.5歸并排序兩路歸并算法

1、算法基本思緒

設(shè)兩個(gè)有序子文件(相當(dāng)于輸入堆)放在同一向量中相鄰位置上：R[low..m]，R[m+1..high]，先將它們合并到一個(gè)局部暫存向量R1(相當(dāng)于輸出堆)中，待合并完成后將R1復(fù)制回R[low..high]中。

排序概念第97頁（1）合并過程

合并過程中，設(shè)置i，j和p三個(gè)指針，其初值分別指向這三個(gè)統(tǒng)計(jì)區(qū)起始位置。合并時(shí)依次比較R[i]和R[j]關(guān)鍵字，取關(guān)鍵字較小統(tǒng)計(jì)復(fù)制到R1[p]中，然后將被復(fù)制統(tǒng)計(jì)指針i或j加1，以及指向復(fù)制位置指針p加1。

重復(fù)這一過程直至兩個(gè)輸入子文件有一個(gè)已全部復(fù)制完成(不妨稱其為空)，此時(shí)將另一非空子文件中剩下統(tǒng)計(jì)依次復(fù)制到R1中即可。排序概念第98頁歸并示例504025198352318123ijkp排序概念第99頁o(nlog2n),存放空間O(n),O(1)3253133364427863325423lowmhigh排序概念第100頁n個(gè)數(shù)歸并示例231235425187101960234287191235511060428735512319121060排序概念第101頁2、歸并算法

voidMerge(SeqListR，intlow，intm，inthigh)

{//將兩個(gè)有序子文件R[low..m)和R[m+1..high]歸并成一個(gè)有序

//子文件R[low..high]

inti=low