數(shù)據(jù)結(jié)構(gòu)JAVA語言描述習題答案(劉小晶等主編).第7章排序(Java版)

第七章排序1教學內(nèi)容7.1排序的基本概念

7.2插入排序7.3交換排序

7.4選擇排序

7.5歸并排序

7.6基數(shù)排序

教學重點與難點重點：掌握排序的基本概念以及各種常見排序方法的實現(xiàn)。難點：希爾排序、快速排序、歸并排序和堆排序等高效排序方法。【課前思考】1.熟悉排序嗎？過去曾經(jīng)學過哪些排序方法？

在第一章中曾以選擇排序和起泡排序為例討論算法實際復雜度．

2.自己有沒有編過排序的程序？是用的什么策略？4

1、排序的定義3、內(nèi)部排序的方法4、排序算法的性能評價5、待排序記錄的類描述2、排序的分類7.1排序的基本概念5

1、排序的定義排序是計算機內(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個記錄的序列為{R0,R1,…，Rn-1}其相應的關(guān)鍵字序列為{K0,K1,…，Kn-1}這些關(guān)鍵字相互之間可以進行比較，且在它們之間存在著這樣一個關(guān)系：

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

{Rp1,Rp2,

…，Rpn}的操作稱作排序。1、排序的定義7

關(guān)鍵字

是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標識（識別）一個數(shù)據(jù)元素（或記錄）。

若此關(guān)鍵字可以識別唯一的一個記錄，則稱之謂“主關(guān)鍵字”。

若此關(guān)鍵字能識別若干記錄，則稱之謂“次關(guān)鍵字”。8

2、排序的分類(1)按排序過程中所涉及到的存儲器不同分為：(2)按相同關(guān)鍵字在排序前后的位置不同分為：穩(wěn)定排序

內(nèi)部排序

外部排序

不穩(wěn)定排序假設Ki=Kj（i≠j),且在排序前的序列中Ri領先于Rj（即i＜j)。若在排序后的序列中Ri仍領先于Rj，則稱所用的排序方法是穩(wěn)定的；反之，則稱所用的排序方法是不穩(wěn)定的。

9

3、內(nèi)部排序的方法內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。經(jīng)過一趟排序有序序列區(qū)無序序列區(qū)有序序列區(qū)無序序列區(qū)10

基于不同的“擴大”有序序列長度的方法，內(nèi)部排序方法大致可分下列幾種類型：插入類交換類選擇類

歸并類其它方法3、內(nèi)部排序的方法11

(1)插入類將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。12

(2)交換類通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。13

(3)選擇類從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。14

(4)歸并類通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。(5)其它方法就各類介紹一二個典型算法。如：基數(shù)排序下面就各類介紹一二個典型算法。15

4、排序算法的性能評價時間比較次數(shù)（與關(guān)鍵字值比較）移動次數(shù)空間：指所需輔助空間的大小穩(wěn)定性16

內(nèi)部排序的時間分析：實現(xiàn)內(nèi)部排序的基本操作有兩個：（2）“移動”記錄。（1）“比較”序列中兩個關(guān)鍵字的大?。?7

待排序的順序表記錄類描述如下:(P242)

publicclassRecordNode

{privateComparablekey;//關(guān)鍵字

privateObjectelement;//數(shù)據(jù)元素……}備注：1.key為Comparable接口類型，它能夠賦值為任何實現(xiàn)Comparable接口類的對象。

2.element為Object類型，在實際應用時，可根據(jù)不同問題定義為不同的具體類。5、待排序記錄的類描述18

待排序的順序表類(P243)publicclass

SeqList{

privateRecordNode[]r;

//順序表記錄結(jié)點數(shù)組

privateint

curlen;

//順序表長度，即記錄個數(shù)//構(gòu)造方法:構(gòu)造一個存儲空間容量為maxSize的順序表

publicSeqList(int

maxSize){

this.r=newRecordNode[maxSize];

//為順序表分配maxSize個存儲單元

this.curlen=0;

//置順序表的當前長度為0}

……}19

總思想：

每次將一個待排序的記錄，按其關(guān)鍵字值的大小插入到前面已排序好的記錄序列中的適當位置，直到全部記錄插入完成為止。7.2插入排序20

有序序列r[0..i-1]R[i]無序序列r[i..n-1]一趟插入排序的基本思想：有序序列r[0..i]無序序列r[i+1..n-1]21

實現(xiàn)“一趟插入排序”可分三步進行：3．將r[i]

插入(復制)到r[j+1]的位置上。2．將r[j+1..i-1]中的所有記錄均后移

一個位置；1．在r[0..i-1]中查找r[i]的插入位置，

r[0..j].keyr[i].key<r[j+1..i-1].key；22

直接插入排序（基于順序查找）

確定插入位置的查找方法不同導致不同的算法描述：希爾排序（基于逐趟縮小增量）7.2插入排序23

待排序記錄依次存放在數(shù)組r[0..n-1]中。思想：

先將第0個記錄組成一個有序的子表，然后依次將后面的記錄插入到這子表中，且一直保持它的有序性。7.2.1直接插入排序-不帶監(jiān)視哨的算法基本條件：24

例：

（43）

21891543

（1521434389）i=4i=1

（2143）

891543

(214389）

1543i=2直接插入排序示例r0r1r2r3r443

218915437.2.1直接插入排序-不帶監(jiān)視哨的算法（15214389)

43i=325

實現(xiàn)直接插入排序的步驟為：(P244)2）后移并插入3）令i=1，2，…,n-1,重復1）、

2），實現(xiàn)整個序列的排序。1）查找r[i]的插入位置7.2.1直接插入排序-不帶監(jiān)視哨的算法將r[i]暫存在臨時變量temp中，將temp與r[j](j=i-1,…，0）依次進行比較

如何查找？26

publicvoidinsertSort(){

RecordNodetemp;

inti,j;

for(i=1;i<this.curlen;i++){

//n-1趟掃描

temp=r[i];

//第i條記錄暫存在temp中

for(j=i-1;j>=0&&temp.getKey().compareTo(r[j].getKey())

<0;j--){

r[j+1]=r[j];

//后移

}

r[j+1]=temp;

//r[i]插入到第j+1個位置

}}

7.2.1直接插入排序-不帶監(jiān)視哨的算法P245算法7.1算法需進行改進??！27

此算法中第6行的循環(huán)條件中的“j>=0”用來控制下標越界。為了提高算法效率，可對該算法進行如下改進：首先將待排序的n條記錄從下標為1的存儲單元開始依次存放在數(shù)組r中，再將順序表的第0個存儲單元設置為一個“監(jiān)視哨”，即在查找之前把r[i]賦給r[0]，這樣每循環(huán)一次只需要進行記錄的比較，不需要比較下標是否越界7.2.1直接插入排序-帶監(jiān)視哨的算法28

例：初始關(guān)鍵字：

（43）

21891543(21)（2143）

891543i=2(15)（15214389)43i=4(43)（1521434389）i=5(89)(214389）

1543i=3直接插入排序示例r0r1r2r3r4r5432189154329

從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].getKey<r[j].getKey;--j);//從后往前找j=i-1插入位置如何查找到r[i]的插入位置？7.2.1直接插入排序-帶監(jiān)視哨的算法30

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

r[j+1]=r[j]；r[0]jr[i]j=i-1上述循環(huán)結(jié)束后可以直接進行“插入”插入位置后移并插入7.2.1直接插入排序-帶監(jiān)視哨的算法31

令i=2，…,curlen-1,實現(xiàn)整個序列的排序。for(i=2;i<=curlen;++i)

{在

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

插入r[i];

}7.2.1直接插入排序-帶監(jiān)視哨的算法32

voidinsertSortWithGuard()(){//對順序表

作直接插入排序。for(i=2;i<=this.curlen;++i){

}}r[0]=r[i];//復制為監(jiān)視哨for(j=i-1;

r[0].getKey().compareTo(r[j].getKey())<0;

j--)

r[j+1]=r[j];

//記錄后移r[j+1]=r[0];//插入到正確位置7.2.1直接插入排序-帶監(jiān)視哨的算法P245算法7.233

不帶監(jiān)視哨的直接插入排序性能分析：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：34

平均值：約n2/4１.直接插入排序的時間復雜度：2.只需記錄的輔助空間３.是的排序方法一個穩(wěn)定O（n2)7.2.1直接插入排序-性能分析35

（又稱縮小增量排序）

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

所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。具體做法為：7.2.2希爾排序36

將記錄序列分成若干子序列，分別對每個子序列進行插入排序。

其中，d

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

{r[0]，r[0+d]，r[0+2d]，…，r[0+kd]}{r[1]，r[1+d]，r[1+2d]，…，r[1+kd]}…{r[d－1]，r[2d－1]，r[3d－1]，…，r[d+kd-1]}7.2.2希爾排序37

例1：初始關(guān)鍵字序列如下：{49，38，65，97，76，13，27，49，5504}，請寫出它們的希爾排序的全過程(其中d=5,3,1）7.2.2希爾排序38

初始關(guān)鍵字：49,38,65,97,76,13,27,49,55,4取d3=1三趟分組：三趟排序結(jié)果：一趟排序結(jié)果：二趟排序結(jié)果：取d1=5一趟分組：取d2=3二趟分組：493865977613274955413274955449386597761327495544938659776134493827495565977613449382749556597764132738494955657697不穩(wěn)定的排序方法39publicvoidshellSort(int[]d){

RecordNodetemp;

inti,j;for(intk=0;k<d.length;k++){

int

dk=d[k];for(i=dk;i<this.curlen;i++){

temp=r[i];for(j=i-dk;j>=0&&temp.getKey().compareTo(r[j].getKey())<0;j-=dk){r[j+dk]=r[j];

}

r[j+dk]=temp;}}P247算法希爾排序-算法40

１.希爾排序的時間復雜度：

不確定，但在插入排序中，希爾排序的效能最高，最好情況可達O（nlog2n)３.是的排序方法例：對序列2，1，1進行希爾排序（d分別取2,1時）結(jié)果：1，1，2不穩(wěn)定2.只需記錄的輔助空間一個7.2.2希爾排序-性能分析41

1.冒泡排序2.快速排序7.2交換排序42

1.基本思想：

將待排序的數(shù)組看成從上到下的存放，把關(guān)鍵字較小的記錄看成“較輕的”，關(guān)鍵字較大的記錄看成“較重的”，小關(guān)鍵字的記錄好像水中的氣泡一樣，向上?。淮箨P(guān)鍵字的記錄如水中的石塊向下沉，當所有的氣泡都浮到了相應的位置，且所有的石塊都沉到了水中，排序就結(jié)束了。7.3.1冒泡排序43

從第一個記錄開始，依次對無序區(qū)中相鄰記錄進行關(guān)鍵字比較，如果大在上，小在下，則交換，第一趟掃描下來表中最大的沉在最下面。然后再對前n-1個記錄進行冒泡排序，直到排序成功為止。

一般地，第i趟掃描時,r[0]到r[n-i]和r[n-i+1]到r[n－1]分別為當前的無序區(qū)和有序區(qū)。2.基本步驟7.3.1冒泡排序44

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

n-i+1的位置上例1：寫出對關(guān)鍵字序列{43，21，89，15，28，43}進行冒泡排序的各趟結(jié)果7.3.1冒泡排序45

985420895420859420854920854290854209大數(shù)沉淀，小數(shù)起泡a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<5;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}46854209584209548209542809542089a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<4;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}47542089452089425089420589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<3;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}48420589240589204589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<2;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}49204589024589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<1;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}50for(i=0;i<5;i++)if(a[i]>a[i+1]){……}for(i=0;i<4;i++)if(a[i]>a[i+1]){……}for(i=0;i<1;i++)if(a[i]>a[i+1]){……}……for(i=0;i<6-j;i++)if(a[i]>a[i+1]){……}for(j=1;j<6;j++)6-16-26-551publicvoid

bubbleSort(){

RecordNodetemp;

//輔助結(jié)點for(inti=1;i<this.curlen;i++){//進行n-1趟排序for(intj=0;j<this.curlen-i;j++){

if(r[j].getKey().compareTo(r[j+1].getKey())>0){

//逆序時，交換

temp=r[j];r[j]=r[j+1];

r[j+1]=temp;}

}}}7.3.1冒泡排序-算法52

publicvoid

bubbleSort(){

RecordNodetemp;

boolean

flag=true;

//是否交換的標記

for(inti=1;i<this.curlen

&&flag;

i++){

//有交換時再進行下一趟，最多n-1趟

flag=false;

//記錄未交換標志

for(intj=0;j<this.curlen-i;j++){

if(r[j].getKey().compareTo(r[j+1].getKey())>0){

//逆序時，交換

temp=r[j];r[j]=r[j+1];

r[j+1]=temp;

flag=true;

//記錄交換標志

}}}7.3.1冒泡排序-改進算法P249/算法7.453

2.一般情況下，每經(jīng)過一趟“冒泡”，“i減一”（即無序區(qū)的長度減一），但并不是每趟都如此。例如:2553157989i=7i=613i=21.冒泡排序的結(jié)束條件為，

最后一趟沒有進行“交換記錄”。7.3.1冒泡排序-注意:54

7.3.1冒泡排序-思考:1）若設置一個變量lastExchangeIndex來標記每趟排序時經(jīng)過交換的最后位置，算法如何改進？2）雙向起泡的排序算法如何寫？3）已知奇偶轉(zhuǎn)換排序如下：第一趟對所有奇數(shù)的i，將a[i]和a[i+1]進行比較，第二趟對所有偶數(shù)的i,將a[i]和a[i+1]進行比較,每次比較時若a[i]>a[i+1],則將二者交換，以后重復上述二趟過程交換進行，直至整個數(shù)組有序。

a)試問排序結(jié)束的條件是什么？

b)實現(xiàn)上述排序過程的算法如何？55

最好的情況（關(guān)鍵字在記錄序列中順序有序）：只需進行一趟起泡“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：需進行n-1趟起泡“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：n-17.3.1冒泡排序-性能分析：56

１.起泡排序的時間復雜度：

O（n2)2.只需一個記錄的輔助空間

O(1)３.是穩(wěn)定的排序方法7.3.1冒泡排序-性能分析：57

通過一趟排序?qū)⒁判虻挠涗浄指畛瑟毩⒌膬蓚€部分，其中一部分的所有記錄的關(guān)鍵字值都比另外一部分的所有記錄關(guān)鍵字值小，然后再按此方法對這兩部分記錄分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個記錄序列變成有序。7.3.2快速排序基本思想：58

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

r[j].getKey()≤r[i].getKey()≤r[j].getKey()(s≤j≤i-1)

樞軸

(i+1≤j≤t)。7.3.2快速排序-一趟快速排序1.目標：59

無序的記錄序列無序記錄子序列(1)無序子序列(2)樞軸通過一趟快速排序后（一次劃分）7.3.2快速排序-一趟快速排序60

lowhighij設r[s]=52為樞軸

將r[j].getKey()和樞軸關(guān)鍵字進行比較,要求r[j].getKey()≥

樞軸的關(guān)鍵字；

將r[i].getKey()和樞軸關(guān)鍵字進行比較，要求r[i].getKey()≤

樞軸的關(guān)鍵字。j23i80j14i52prvot52jjji7.3.2快速排序-一趟快速排序i61

493865977613274927i初始關(guān)鍵字：jx49jii65j13i97jj494938659776132749初始關(guān)鍵字：完成一趟排序：2738134976976549一次劃分后：(273813)49(76976549)分別進行快速排序：(13)

27

(38)

49(4965)

76(97)

(13)

27

(38)

49

49(65)

76(97)快速排序結(jié)束：13

27

3849

4965

76

97不穩(wěn)定的排序方法62

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

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

之后逐漸減小

j，增加

i，并保證

r[j].getKey()≥52，和r[i].getKey()≤52,否則進行記錄的“交換”。7.3.2快速排序-一趟快速排序63

以首結(jié)點為樞軸,考慮的結(jié)點序列為r[low]，r[low+1]，…，r[high],且low<high。1）i=low,j=high,pivot=r[i];2）如果i!=j，則

(a)若r[j].getKey()>pivot,那么j=j-1,

轉(zhuǎn)(a)；否則r[i]=r[j]，i=i+1,轉(zhuǎn)（b）

(b)若r[i].getKey()<=pivot,那么i=i+1，轉(zhuǎn)(b)；否則r[j]=r[i],j=j-1,轉(zhuǎn)2）3）如果i==j，則r[i]=pivot，算法結(jié)束。2.算法基本步驟：7.3.2快速排序-一趟快速排序64

intPartition(inti,intj){//一趟快速排序算法7.5}//PartitionRecordNode

pivot=r[i];//樞軸while(i<j){}while(i<j&&pivot.getKey().compareTo(r[j].getKey())<0)j--;//從右向左搜索if(i<j)r[i++]=r[j];while(i<j&&pivot.getKey().compareTo(r[i].getKey())>0)i++;//從左向右搜索if(i<j)r[j--]=r[i];r[i]=pivot;

returni;65

再例如：根據(jù)算法步驟寫出對關(guān)鍵字序列{26，37，08，63，12，59，12，48}進行快速排序的第一趟排序過程和每一趟排序結(jié)果。66

3、快速排序

首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。無序的記錄序列無序記錄子序列(1)無序子序列(2)樞軸一次劃分分別進行快速排序67

publicvoidqSort(intlow,inthigh){if(low<high){

int

pivotloc=Partition(low,high);

//一趟排序，將排序表分為兩部分

qSort(low,pivotloc-1);

//低子表遞歸排序

qSort(pivotloc+1,high);

//高子表遞歸排序

}[算法7.6]遞歸形式的快速排序算法(P251)68

void

QuickSort(){

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

qSort(0,curlen-1);}//QuickSort

第一次調(diào)用函數(shù)Qsort

時，待排序記錄序列的上、下界分別為

0

和curlen-1。69

快速排序的性能分析假設一次劃分所得樞軸位置i=k，則對n個記錄進行快排所需時間：其中Tpass(n)為對n個記錄進行一次劃分所需時間。

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

取1至n

中任意一值的可能性相同。T(n)=Tpass(n)+T(k-1)+T(n-k)70

設Tavg(1)≤b則可得結(jié)果：由此可得快速排序所需時間的平均值為：71

1)快速排序的時間復雜度為:

2)所需輔助空間

3）是排序O(nlog2n)

是內(nèi)部排序中性能最好的一種。O（log2n）不穩(wěn)定例：對序列2，1，1進行快速排序的結(jié)果：1，1，27.3.2快速排序-性能分析72

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

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

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

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

“三者取中”的記錄為樞軸記錄。7.3.2快速排序73

直接選擇排序樹形選擇排序堆排序7.4選擇排序74

1.基本思想

首先在所有記錄中選出關(guān)鍵字值最小的記錄，把它與第一個記錄進行位置交換，然后在其余的記錄中再選出關(guān)鍵字值次小的記錄與第二個記錄進行位置交換，依此類推，直到所有記錄排好序。7.4.1直接選擇排序75

假設排序過程中，待排記錄序列的狀態(tài)為：有序序列R[1..i-1]無序序列R[i..n]

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

R[i+1..n]7.4.1直接選擇排序76

例：寫出對關(guān)鍵字系列

{4938659776132749

}

進行選擇排序的每一趟結(jié)果。7.4.1直接選擇排序77

13(38659776492749)初始：(4938659776132749)i=11349i=22738i=3i=4i=5i=61327(659776493849)3865132738(9776496549)499713273849(76976549)49761327384976(9765)49766597132738497697(97)497665767697排序結(jié)束13273849769765()497676976576782.基本步驟：（1）置i為0。（2）當i<n-1，重復下列步驟：.a.在（R[i],…,R[n-1]）中選出一個關(guān)鍵字值最小的記錄R[k]；

b.若R[k]不是R[i],(即k!=i），交換R[i],R[k]的位置，否則不進行交換；

c.i值加1。79

直接選擇排序的算法描述如下：void

SelectSort(){//對順序表作簡單選擇排序。

for(i=0;i<length-1;++i){

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

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

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

publicvoidselectsort()//算法7.8{RecordNodetemp;

for(inti=0;i<this.curlen-1;i++){

if(min!=i){temp=r[i];

r[i]=r[min];

r[min]=temp;}}}

intmin=i;

for(intj=i+1;j<this.curlen;j++)if(r[j].key<r[min].key)min=j;81

性能分析：

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

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

最大值為3(n-1)。82

1)直接選擇排序的時間復雜度為

2)所需輔助空間

3）是排序

O(n2)O(1)不穩(wěn)定例如：對序列3,3,1進行選擇排序，結(jié)果為：1，3，37.4.1直接選擇排序-性能分析83

基本思想是:首先針對n個記錄進行兩兩比較，比較的結(jié)果是把關(guān)鍵字值較小者作為優(yōu)勝者上升到父結(jié)點，得到個比較的優(yōu)勝者(關(guān)鍵字值較小者)，作為第一步比較的結(jié)果保留下來；然后對這個記錄再進行關(guān)鍵字的兩兩比較，如此重復，直到選出一個關(guān)鍵字值最小的記錄為止。

這個過程可用一個含有n個葉子結(jié)點的完全二叉樹來表示

7.4.2樹形選擇排序84

例如：對于由8個關(guān)鍵字組成的序列{52，39，67，95，70，8，25，45}，使用樹形選擇排序選出最小關(guān)鍵字值的過程可用圖(a)所示的完全二叉樹來表示。7.4.2樹形選擇排序85

7.4.2樹形選擇排序86

要求出次小關(guān)鍵字記錄，只需將葉子結(jié)點中最小的關(guān)鍵字值改為“∞”，然后從該葉子結(jié)點開始與其左(或右)兄弟的關(guān)鍵字進行比較，用較小關(guān)鍵字修改父結(jié)點關(guān)鍵字，用此方法，從下到上修改從該葉子結(jié)點到根結(jié)點路徑上的所有結(jié)點的關(guān)鍵字值，則可得到次小關(guān)鍵字記錄，如圖(b)所示。以此類推，可依次選出從小到大的所有關(guān)鍵字。7.4.2樹形選擇排序87

7.4.2樹形選擇排序88

⑴空間復雜度樹形選擇排序雖然減少了排序時間，但使用了較多的附加存儲空間。⑵時間復雜度樹形選擇排序的時間復雜度為O(nlog2n)

⑶算法穩(wěn)定性樹形選擇排序是一種穩(wěn)定的排序算法。算法性能分析89

堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或7.4.3堆排序(小頂堆)(大頂堆)

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

是ri

的左孩子；r2i+2

是ri

的右孩子。所以，堆的含義表明：完全二叉樹中所有非終端結(jié)點的值均不大于（或不小于）其左、右孩子結(jié)點的值。90

1236276549817355403498是堆14不{12,36,27,65,40,34,98,81,73,55,49}例如:是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆91

2.堆排序的方法：首先把待排序的記錄序列對應成一棵完全二叉樹，并把它轉(zhuǎn)換成一個初始堆（即首先建初始堆）。這時，根結(jié)點具有最大（或最?。┑年P(guān)鍵字值，然后，交換根結(jié)點和最后一個結(jié)點（即第n個結(jié)點）的位置，除最后一個結(jié)點之外，前n-1個結(jié)點仍構(gòu)成一棵完全二叉樹，再把它們調(diào)整為一個堆。同樣交換根結(jié)點和最后一個結(jié)點（即第n-1個結(jié)點）。重復進行下去，直到只剩下一個根結(jié)點為止，便得一個有序表。92

例如：建大頂堆{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)過篩選初始關(guān)鍵字93

如何“建初始堆”？兩個問題:如何“篩選”？94

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

98814973556412362740例如:是大頂堆12但在98和12進行互換之后，它就不是堆了，因此，需要對它進行“篩選”。98128173641298比較比較96

建堆是一個從下往上進行“篩選”的過程。40554973816436122798例如:排序之前的關(guān)鍵字序列為123681734998817355

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

voidHeapSort(){//堆排序算法7.12(P262)

intn=this.curlen;

RecordNodetemp;}for(inti=n/2-1;i>=0;i--)//創(chuàng)建堆

sift(i,n-1);//每趟將最小關(guān)鍵字值交換到后面，再調(diào)整成堆for(inti=n-1;i>0;i--){

temp=r[0];r[0]=r[i];r[i]=temp;

sift(0,i-1);}98

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

對深度為k的堆，“篩選”所需進行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；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；99

結(jié)論:

1)堆排序的時間復雜度為

2)所需輔助空間

3）是排序

O(nlog2n)O(1)不穩(wěn)定100

歸并排序的過程基于下列基本思想進行：

將兩個或兩個以上的有序子序列“歸并”為一個有序序列。7.5歸并排序101

在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。有序序列r[l..n]有序子序列r[l..m]有序子序列r[m+1..n]這個操作對順序表而言，是輕而易舉的。7.5歸并排序102

2-路歸并的方法

將待排序記錄R[0]到R[n-1]看成是n個長度為1的有序子表，把這些子表依次兩兩歸并，便得到[n/2]個有序的子表，然后，再把這[n/2]個有序的子表兩兩歸并，如此重復，直到最后得到一個長度為n的有序表為止。7.5歸并排序103

例如，如下圖為2-路歸并的一個例子：(52)(23)(80)(36)(68)(14)(27)(2352)(3680)(1468)(27)(23365280)(142768)(14232736526880)一趟歸并之后二趟歸并之后三趟歸并之后7.5歸并排序104

歸并排序的算法如果記錄無序序列R[s..t]的兩部分

R[s..(s+t)/2]和R[(s+t)/2+1..t]分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。

由此，應該先分別對這兩部分進行2-路歸并排序。105

例如：52,23,80,36,68,14(s=1,t=6)[52,23,80][36,68,14][52,23][80][52][23,52][

23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]106

容易看出，對n

個記錄進行歸并排序的時間復雜度為Ο(nlogn)。即：每一趟歸并的時間復雜度為O(n)，總共需進行l(wèi)og2n趟。107

結(jié)論：

1)歸并排序的時間復雜度為

2)所需輔助空間

3）是排序

O(n)穩(wěn)定O(nlog2n)7.5歸并排序-性能分析108

基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來實現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。多關(guān)鍵字的排序鏈式基數(shù)排序7.6基數(shù)排序109

7.6.1多關(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)110

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

先對K1進行排序，并按K1的不同值將記錄序列分成若干子序列之后，分別對K2進行排序，...…，依次類推，直至最后對最次位關(guān)鍵字排序完成為止。7.6.1多關(guān)鍵字的排序-MSD法112

先對Kd

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

排序過程中不需要根據(jù)“前一個”關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個(“前一個”關(guān)鍵字不同的)子序列。7.6.1多關(guān)鍵字的排序-LSD法113

例如:學生記錄含三個關(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的排序過程如下:7.6.1多關(guān)鍵字的排序114

7.6.2鏈式基數(shù)排序假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范圍相同，則按LSD法進行排序時，可以采用“分配-收集”的方法，其好處是不需要進行關(guān)鍵字間的比較。

對于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用這種“分配-收集”的辦法進行排序，稱作基數(shù)排序法。115

例如：對下列這組關(guān)鍵字

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

首先按其

“個位數(shù)”

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

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

“收集”

在一起；

然后按其

“十位數(shù)”

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

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

“收集”

在一起；最后按其“百位數(shù)”重復一遍上述操作。7.6.2鏈式基數(shù)排序116

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

1)待排序記錄以指針相鏈，構(gòu)成一個鏈表；２)“分配”時，按當前“關(guān)鍵字位”所取值，將記錄分配到不同的“鏈隊列”中，每個隊列中記錄的“關(guān)鍵字位”相同；３)“收集”時，按當前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;４)對每個關(guān)鍵字位均重復2)和3)

兩步。7.6.2鏈式基數(shù)排序117

例如：p→369→367→167→239→237→138→230→139進行第一次分配進行第一次收集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→368→239→139→369←→239→139→138←7.6.2鏈式基數(shù)排序118

進行第二次分配p→230→237→138→239→139p→230→367→167→237→138→368→239→139f[3]r[3]f[6]r[6]→230←→237→138→239→139→367←→167→368→367→167→368進行第二次收集7.6.2鏈式基數(shù)排序119