《數(shù)據(jù)結(jié)構(gòu)JAVA語言版》課件 第9章 排序

第9章排序在信息處理過程中，最基本的操作是查找。從查找來說，效率最高的是折半查找，折半查找的前提是所有的數(shù)據(jù)元素是按關(guān)鍵字有序的，需要將一個無序的數(shù)據(jù)元素序列轉(zhuǎn)變?yōu)橐粋€有序的數(shù)據(jù)元素序列。

將數(shù)據(jù)元素序列通過某種方法整理成為按關(guān)鍵字有序排列的處理過程稱為排序，排序是數(shù)據(jù)處理中一種最常用的操作。9.1

排序的基本概念⑴排序(Sorting)

排序是將一批(組)任意次序的數(shù)據(jù)元素重新排列成按關(guān)鍵字有序的數(shù)據(jù)元素序列的過程，其定義為：給定一組數(shù)據(jù)元素序列：{R1,R2,…,Rn}，其相應(yīng)的關(guān)鍵字序列是{K1,K2,…,Kn}。確定1,2,…n的一個排列p1,p2,…,pn，使其相應(yīng)的關(guān)鍵字滿足如下非遞減(或非遞增)關(guān)系：Kp1≤Kp2≤…≤Kpn的序列{Kp1,Kp2,…,Kpn}，這種操作稱為排序。關(guān)鍵字Ki可以是數(shù)據(jù)元素Ri的主關(guān)鍵字，也可以是次關(guān)鍵字或若干數(shù)據(jù)項(xiàng)的組合。

◆

Ki是主關(guān)鍵字：排序后得到的結(jié)果是唯一的；

◆

Ki是次關(guān)鍵字：排序后得到的結(jié)果是不唯一的。⑵排序的穩(wěn)定性若數(shù)據(jù)元素序列中有兩個或兩個以上關(guān)鍵字相等的數(shù)據(jù)元素：Ki=Kj(i≠j，i,j=1,2,…n)，且在排序前Ri先于Rj(i<j)，排序后的數(shù)據(jù)元素序列仍然是Ri先于Rj，稱排序方法是穩(wěn)定的，否則是不穩(wěn)定的。排序算法有許多，但就全面性能而言，還沒有一種公認(rèn)為最好的。每種算法都有其優(yōu)點(diǎn)和缺點(diǎn)，分別適合不同的數(shù)據(jù)量和硬件配置。評價排序算法的標(biāo)準(zhǔn)有：執(zhí)行時間和所需的輔助空間，其次是算法的穩(wěn)定性。若排序算法所需的輔助空間不依賴問題的規(guī)模n，即空間復(fù)雜度是O(1)，則稱排序方法是就地排序，否則是非就地排序。⑶排序的分類待排序的數(shù)據(jù)元素數(shù)量不同，排序過程中涉及的存儲器的不同，有不同的排序分類。①待排序的數(shù)據(jù)元素數(shù)不太多，所有的數(shù)據(jù)元素都能存放在內(nèi)存中進(jìn)行排序，稱為內(nèi)部排序；②待排序的數(shù)據(jù)元素數(shù)太多，所有的數(shù)據(jù)元素不可能全部存放在內(nèi)存中，排序過程中必須在內(nèi)、外存之間進(jìn)行數(shù)據(jù)交換，這樣的排序稱為外部排序。⑷內(nèi)部排序的基本操作

對內(nèi)部排序而言，其基本操作有兩種：（1）比較兩個關(guān)鍵字的大??；（2）數(shù)據(jù)元素的移動，有時候移動的并不是數(shù)據(jù)元素本身，而是數(shù)據(jù)元素存儲地址（引用）的移動；或數(shù)據(jù)元素存儲地址（引用）的修改。第一種操作是必不可少的；而第二種操作到底是什么，取決于數(shù)據(jù)元素的存儲方式，具體情況是：①數(shù)據(jù)元素存儲在一組連續(xù)地址的存儲空間：數(shù)據(jù)元素之間的邏輯順序關(guān)系是通過其物理存儲位置的相鄰來體現(xiàn)，移動的是數(shù)據(jù)元素本身；②數(shù)據(jù)元素采用鏈?zhǔn)酱鎯Ψ绞剑簲?shù)據(jù)元素之間的邏輯順序關(guān)系是通過數(shù)據(jù)元素結(jié)點(diǎn)中的引用來體現(xiàn)，排序過程僅需修改數(shù)據(jù)元素結(jié)點(diǎn)的引用，而不需要移動數(shù)據(jù)元素；③數(shù)據(jù)元素存儲在一組連續(xù)地址的存儲空間：構(gòu)造另一個輔助表來保存各個數(shù)據(jù)元素的存儲地址（引用）：排序過程不需要移動數(shù)據(jù)元素，而僅需修改輔助表中的引用，排序后視具體情況決定是否調(diào)整數(shù)據(jù)元素的存儲位置。④數(shù)據(jù)元素存儲在一組任意地址的存儲空間：構(gòu)造另一個輔助表來保存各個數(shù)據(jù)元素的存放地址（引用）：排序過程不需要移動數(shù)據(jù)元素本身，而僅需移動輔助表中的引用，排序后視具體情況決定是否調(diào)整數(shù)據(jù)元素的存儲位置。①比較適合數(shù)據(jù)元素數(shù)較少的情況；而②、③、④則適合數(shù)據(jù)元素數(shù)較多的情況。在Java語言的層面上討論問題時，假設(shè)待排序的數(shù)據(jù)元素是以④的情況存儲；輔助表即類數(shù)組，存儲的是數(shù)據(jù)元素的引用，關(guān)鍵字是可直接用比較運(yùn)算符進(jìn)行比較的類型：假設(shè)為int整型；排序中移動的不是數(shù)據(jù)元素本身，而是指示數(shù)據(jù)元素存儲地址的引用。待排序的數(shù)據(jù)元素類型的定義如下。 classDataType{ publicintkey;//關(guān)鍵字域 //infoTypeotherinfo;//其他域}輔助表的定義如下。publicclassSqlist{ publicDataType[]R;

//R數(shù)組存儲數(shù)據(jù)元素的地址，0號單元不用 publicintn;//n是待排序的元素個數(shù)}9.2

插入排序

采用的是以“玩橋牌者”的方法為基礎(chǔ)的。即在考察數(shù)據(jù)元素Ri之前，設(shè)以前的所有數(shù)據(jù)元素R1,R2,….,Ri-1已排好序，然后將Ri插入到已排好序的諸數(shù)據(jù)元素的適當(dāng)位置。最基本的插入排序是直接插入排序(StraightInsertionSort)。9.2.1

直接插入排序1排序思想

將待排序的數(shù)據(jù)元素Ri，插入到已排好序的數(shù)據(jù)元素表R1，R2，…，Ri-1中，得到一個新的、數(shù)據(jù)元素數(shù)增加1的有序表，直到所有的數(shù)據(jù)元素都插入完為止。設(shè)待排序的數(shù)據(jù)元素順序存放在數(shù)組分量R[1…n]中，在排序的某一時刻，將數(shù)據(jù)元素序列分成兩部分：①R[1…i-1]：已排好序的有序部分；②R[i…n]：未排好序的無序部分。顯然，在剛開始排序時，R[1]是已經(jīng)排好序的。例：設(shè)有關(guān)鍵字序列為：7,4,-2,19,13,6，直接插入排序的過程如下圖9-1所示：初始數(shù)據(jù)元素的關(guān)鍵字：[7]4-219136第一趟排序：[47]-219136第二趟排序：[-247]19136第三趟排序：[-24719]136第四趟排序：[-2471319]6第五趟排序：[-24671319]圖9-1直接插入排序的過程2算法實(shí)現(xiàn)publicvoidstraight_insert_sort(SqlistL){ inti,j; for(i=2;i<=L.n;i++){ L.R[0]=L.R[i];/*設(shè)置哨兵*/ j=i-1; while(L.R[0].key<L.R[j].key){ L.R[j+1]=L.R[j]; j--; }/*查找插入位置*/ L.R[j+1]=L.R[0];/*插入到相應(yīng)位置*/ }}3算法說明

算法中的L.R[0]開始時并不存放任何待排序的數(shù)據(jù)元素，引入的作用主要有兩個：

①不需要增加輔助空間：保存當(dāng)前待插入的數(shù)據(jù)元素L.R[i]，L.R[i]會因?yàn)閿?shù)據(jù)元素的后移而被占用；

②保證查找插入位置的內(nèi)循環(huán)總可以在超出循環(huán)邊界之前找到一個等于當(dāng)前數(shù)據(jù)元素的數(shù)據(jù)元素，起“哨兵監(jiān)視”作用，避免在內(nèi)循環(huán)中每次都要判斷j是否越界，從而可以使比較次數(shù)減少約一半。4

算法分析

從空間性能看，i、j、L.R[0]所占用的輔助存儲空間是一個常數(shù)，所以空間復(fù)雜度為O（1）。

從時間性能看，向有序表中逐個插入數(shù)據(jù)元素的的操作，共進(jìn)行了n-1趟，每趟操作分為比較關(guān)鍵字和移動數(shù)據(jù)元素，而比較的次數(shù)和數(shù)據(jù)元素移動的次數(shù)取決于初始數(shù)據(jù)元素序列的排列情況，可以分兩種情況進(jìn)行討論。4

算法分析⑴最好情況：若待排序數(shù)據(jù)元素按關(guān)鍵字從小到大排列（正序），算法中的內(nèi)循環(huán)無須執(zhí)行，則一趟排序時，關(guān)鍵字比較次數(shù)1次（L.R[0].key<L.R[j].key），數(shù)據(jù)元素移動次數(shù)2次（L.R[0]=L.R[i]，L.R[j+1]=L.R[0]），則整個排序的關(guān)鍵字比較次數(shù)和數(shù)據(jù)元素移動次數(shù)分別是：

比較次數(shù)：移動次數(shù)：⑵最壞情況：若待排序數(shù)據(jù)元素按關(guān)鍵字從大到小排列（逆序），則一趟排序時：算法中的內(nèi)循環(huán)體執(zhí)行i-1，關(guān)鍵字比較次數(shù)i次，數(shù)據(jù)元素移動次數(shù)i+1。則就整個排序而言：

一般地，如果待排序的數(shù)據(jù)元素可能出現(xiàn)的各種排列的概率相同，關(guān)鍵字平均比較次數(shù)和數(shù)據(jù)元素平均移動次數(shù)約等于以上兩種情況的平均值，約為n2/4，時間復(fù)雜度為O（n2）。比較次數(shù)：移動次數(shù)：9.2.2其它插入排序1折半插入排序

當(dāng)將待排序的數(shù)據(jù)元素R[i]插入到已排好序的數(shù)據(jù)元素子表R[1…i-1]中時，由于R1,R2,…,Ri-1已排好序，則查找插入位置可以用“折半查找”實(shí)現(xiàn)，則直接插入排序就變成為折半插入排序。代碼見教材。從時間上比較，折半插入排序僅僅減少了關(guān)鍵字的比較次數(shù)，卻沒有減少數(shù)據(jù)元素的移動次數(shù)，故時間復(fù)雜度仍然為O(n2)。⑵

排序示例設(shè)有一組關(guān)鍵字30,13,70,85,39,42,6,20，采用折半插入排序方法排序的過程如下所示：i=1(30)1370853942620i=213(1330)70853942620┇i=76(6133039427085)20i=820(6133039427085)20lowhighmidi=820(6133039427085)20lowhighmidi=820(6133039427085)20midhighlowi=820(613203039427085)圖9-2折半插入排序過程22-路插入排序

是對折半插入排序的改進(jìn)，以減少排序過程中移動數(shù)據(jù)元素的次數(shù)。該算法需要附加n個數(shù)據(jù)元素的輔助空間，方法是：①另設(shè)一個和L.R同類型的數(shù)組d，L.R[1]賦給d[1]，將d[1]看成是排好序的序列中中間位置的數(shù)據(jù)元素；②分別將L.R[]中的第i個數(shù)據(jù)元素依次插入到d[1]之前或之后的有序序列中，具體方法：若L.R[i].key<d[1].key：L.R[i]插入到d[1]之前的有序表中；若L.R[i].key≥d[1].key：L.R[i]插入到d[1]之后的有序表中。關(guān)鍵點(diǎn)：實(shí)現(xiàn)時將向量d看成是循環(huán)向量，并設(shè)兩個指針first和final分別指示排序過程中得到的有序序列中的第一個和最后一個數(shù)據(jù)元素。排序示例例如，設(shè)有初始關(guān)鍵字集合{49，38，65，13，97，27，76，49}，采用2-路插入排序的過程如圖9-3所示。在2-路插入排序中，移動數(shù)據(jù)元素的次數(shù)約為n2/8。但當(dāng)L.R[1]是待排序數(shù)據(jù)元素中關(guān)鍵字最大或最小的數(shù)據(jù)元素時，2-路插入排序就完全失去了優(yōu)越性。圖9-32-路插入排序的過程3表插入排序前面的插入排序不可避免地要移動數(shù)據(jù)元素，若不希望移動數(shù)據(jù)元素就需要改變存儲結(jié)構(gòu)，進(jìn)行表插入排序。數(shù)據(jù)元素類型修改為：classDataType1{ intkey;/*關(guān)鍵字碼*/ //infoTypeotherinfo;/*其他域*/ intnext;}初始化：下標(biāo)值為0的分量作為表頭結(jié)點(diǎn)，關(guān)鍵字取為int類型最大值，各分量的next值為空；①將靜態(tài)鏈表中數(shù)組下標(biāo)值為1的分量（結(jié)點(diǎn)）與表頭結(jié)點(diǎn)構(gòu)成一個靜態(tài)循環(huán)鏈表；②i=2，將分量R[i]按關(guān)鍵字非遞減有序插入到靜態(tài)循環(huán)鏈表；③增加i，重復(fù)②，直到全部分量插入到靜態(tài)循環(huán)鏈表。例：設(shè)有關(guān)鍵字集合{49,38,65,97,76,13,27,49}，采用表插入排序的過程如下圖9-4所示。

012345678key域next域MAXINT4938651397277649

1

0-------i=2MAXINT4938651397277649

201------i=3MAXINT4938651397277649

231

0-----i=4MAXINT4938651397277649

4310

2----i=5MAXINT4938651397277649

43152

0---

和直接插入排序相比，不同的是修改2n次next值以代替移動數(shù)據(jù)元素，而關(guān)鍵字的比較次數(shù)相同，故時間復(fù)雜度為O（n2）。

表插入排序得到一個有序鏈表，對其可以方便地進(jìn)行順序查找，但不能實(shí)現(xiàn)隨機(jī)查找。根據(jù)需要，可以對數(shù)據(jù)元素進(jìn)行重排。i=6MAXINT4938651397277649

43156

02--i=7MAXINT4938651397277649

43176

025-i=8MAXINT4938651397277649

48176

0253圖9-4表插入排序過程9.2.3希爾排序

希爾排序(ShellSort，又稱縮小增量法)是一種分組插入排序方法。1排序思想①先取一個正整數(shù)d1(d1<n)作為第一個增量，將全部n個數(shù)據(jù)元素分成d1組，把所有相隔d1的數(shù)據(jù)元素放在一組中，即對于每個k(k=1,2,…d1)，R[k],R[d1+k],R[2d1+k],…分在同一組中，在各組內(nèi)進(jìn)行直接插入排序。這樣一次分組和排序過程稱為一趟希爾排序；②取新的增量d2<d1，重復(fù)①的分組和排序操作；直至所取的增量di=1為止，即所有數(shù)據(jù)元素放進(jìn)一個組中排序?yàn)橹埂?排序示例設(shè)有10個待排序的數(shù)據(jù)元素，關(guān)鍵字分別為9,13,8,2,5,13,7,1,15,11，增量序列是5,3,1，希爾排序的過程如圖9-5所示。97125131381511第一趟排序后:25197131181513第二趟排序后:12578911131315第三趟排序后:圖9-5希爾排序過程9138251371151171318初始關(guān)鍵字序列:第一趟排序過程:3算法實(shí)現(xiàn)先給出一趟希爾排序的算法，類似直接插入排序。publicvoidshell_pass(SqlistL,intd)/*對順序表L進(jìn)行一趟希爾排序,增量為d*/{intj,k;for(j=d+1;j<=L.n;j++){if(L.R[j].key<L.R[j-d].key){ L.R[0]=L.R[j];/*設(shè)置監(jiān)視哨兵*/ k=j-d; while(k>0&&L.R[0].key<L.R[k].key){ L.R[k+d]=L.R[k]; k=k-d; } L.R[k+d]=L.R[0];}}}然后在根據(jù)增量數(shù)組dk進(jìn)行希爾排序。publicvoidshell_sort(SqlistL,int[]dk,intt)/*按增量序列dk[0…t-1],進(jìn)行希爾排序*/{ intm; for(m=0;m<t;m++) shell_pass(L,dk[m]);}

希爾排序的分析比較復(fù)雜，涉及一些數(shù)學(xué)上的問題，其時間是所取的“增量”序列的函數(shù)。希爾排序特點(diǎn)子序列的構(gòu)成不是簡單的“逐段分割”，而是將相隔某個增量的數(shù)據(jù)元素組成一個子序列。希爾排序可提高排序速度，原因是：◆分組后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了；◆關(guān)鍵字較小的數(shù)據(jù)元素跳躍式前移，在進(jìn)行最后一趟增量為1的插入排序時，序列已基本有序。增量序列取法◆無除1以外的公因子；◆最后一個增量值必須為1。9.3

快速排序

是一類基于交換的排序，系統(tǒng)地交換反序的數(shù)據(jù)元素的偶對，直到不再有這樣的偶對為止。其中最基本的是冒泡排序(BubbleSort)。9.3.1冒泡排序1排序思想

依次比較相鄰的兩個數(shù)據(jù)元素的關(guān)鍵字，若兩個數(shù)據(jù)元素是反序的(即前一個數(shù)據(jù)元素的關(guān)鍵字大于后前一個數(shù)據(jù)元素的關(guān)鍵字)，則進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。①首先將L.R[1]與L.R[2]的關(guān)鍵字進(jìn)行比較，若為反序(L.R[1]的關(guān)鍵字大于L.R[2]的關(guān)鍵字)，則交換兩個數(shù)據(jù)元素；然后比較L.R[2]與L.R[3]的關(guān)鍵字，依此類推，直到L.R[n-1]與L.R[n]的關(guān)鍵字比較后為止，稱為一趟冒泡排序，L.R[n]為關(guān)鍵字最大的數(shù)據(jù)元素。②然后進(jìn)行第二趟冒泡排序，對前n-1個數(shù)據(jù)元素進(jìn)行同樣的操作。一般地，第i趟冒泡排序是對L.R[1…n-i+1]中的數(shù)據(jù)元素進(jìn)行的，因此，若待排序的數(shù)據(jù)元素有n個，則要經(jīng)過n-1趟冒泡排序才能使所有的數(shù)據(jù)元素有序。2排序示例

設(shè)有9個待排序的數(shù)據(jù)元素，關(guān)鍵字分別為23,38,22,45,23,67,31,15,41，冒泡排序的過程如圖9-6所示。3算法實(shí)現(xiàn)圖

9-6

冒泡排序過程233822452367311541初始關(guān)鍵字序列:第一趟排序后:2322

38

23

45

31

15

41

67第二趟排序后:22

23

23

38

31

15

41

45

67第三趟排序后:22

23

23

31

15

38

41

45

67第四趟排序后:22

23

23

15

31

38

41

45

67第五趟排序后:22

23

15

23

31

38

41

45

67第六趟排序后:22

15

23

23

31

38

41

45

67第七趟排序后:152223

23

31

38

41

45

67publicstaticvoidBubble_Sort(SqlistL){inti,k;booleanflag=true;for(i=1;i<L.n&&flag;i++)/*共有n-1趟排序*/{flag=false;for(k=1;k<=L.n-i;k++)/*一趟排序*/if(L.R[k+1].key<L.R[k].key){flag=true;L.R[0]=L.R[k];L.R[k]=L.R[k+1];L.R[k+1]=L.R[0];} }}3算法實(shí)現(xiàn)故時間復(fù)雜度：T(n)=O(n2)空間復(fù)雜度：S(n)=O(1)4算法分析時間復(fù)雜度◆

最好情況(正序)：比較次數(shù)：n-1；移動次數(shù)：0；◆

最壞情況(逆序)：比較次數(shù)：∑(n-i)=n-1i=1n(n-1)2移動次數(shù)：3∑(n-i)=n-1i=13n(n-1)29.3.2快速排序1排序思想通過一趟排序，將待排序數(shù)據(jù)元素分割成獨(dú)立的兩部分，其中一部分?jǐn)?shù)據(jù)元素的關(guān)鍵字均比另一部分?jǐn)?shù)據(jù)元素的關(guān)鍵字小，再分別對這兩部分?jǐn)?shù)據(jù)元素進(jìn)行下一趟排序，以達(dá)到整個序列有序。2排序過程設(shè)待排序的數(shù)據(jù)元素序列是R[s…t]，在數(shù)據(jù)元素序列中任取一個數(shù)據(jù)元素(一般取R[s])作為參照(又稱為基準(zhǔn)或樞軸)，以R[s].key為基準(zhǔn)重新排列其余的所有數(shù)據(jù)元素，方法是：◆

所有關(guān)鍵字比基準(zhǔn)小的放R[s]之前；◆

所有關(guān)鍵字比基準(zhǔn)大的放R[s]之后。以R[s].key最后所在位置i作為分界，將序列R[s…t]分割成兩個子序列，稱為一趟快速排序。3一趟快速排序方法

從序列的兩端交替掃描各個數(shù)據(jù)元素，將關(guān)鍵字小于基準(zhǔn)關(guān)鍵字的數(shù)據(jù)元素依次放置到序列的前邊；而將關(guān)鍵字大于基準(zhǔn)關(guān)鍵字的數(shù)據(jù)元素從序列的最后端起，依次放置到序列的后邊，直到掃描完所有的數(shù)據(jù)元素。設(shè)置指針low，high，初值為第1個和最后一個數(shù)據(jù)元素的位置。設(shè)兩個變量i，j，初始時令i=low，j=high，以R[low].key作為基準(zhǔn)(將R[low]保存在R[0]中)。①從j所指位置向前搜索：將R[0].key與R[j].key進(jìn)行比較：◆

若R[0].key≤R[j].key：令j=j-1，然后繼續(xù)進(jìn)行比較，直到i=j或R[0].key>R[j].key為止；◆

若R[0].key>R[j].key：R[j]R[i]，騰空R[j]的位置，且令i=i+1；②從i所指位置起向后搜索：將R[0].key與R[i].key進(jìn)行比較：◆

若R[0].key≥R[i].key：令i=i+1，然后繼續(xù)進(jìn)行比較，直到i=j或R[0].key<R[i].key為止；◆

若R[0].key<R[i].key：R[i]R[j]，騰空R[i]的位置，且令j=j-1；重復(fù)①、②，直至i=j為止，i就是R[0](基準(zhǔn))所應(yīng)放置的位置。4一趟排序示例

設(shè)有6個待排序的數(shù)據(jù)元素，關(guān)鍵字分別為29,38,22,45,23,67，一趟快速排序的過程如圖9-7所示。圖9-7

一趟快速排序過程j前移2個位置后,R[j]放R[i]的位置:29

23382245

6731ij初始關(guān)鍵字序列:2929382245236731ij029

232245386731iji后移1個位置后,R[i]放R[j]的位置:29

23

2245386731ijj前移2個位置后,R[j]放R[i]的位置:29

23

22

2945386731iji后前移1個位置后,i和j的位置重合:5算法實(shí)現(xiàn)⑴

一趟快速排序算法的實(shí)現(xiàn)publicintquick_one_pass(SqlistL,intlow,inthigh){inti=low,j=high;L.R[0]=L.R[i];/*R[0]作為臨時單元和哨兵*/do{while((L.R[0].key<=L.R[j].key)&&(j>i))j--;if(j>i){L.R[i]=L.R[j];i++;}while((L.R[i].key<=L.R[0].key)&&(j>i))i++;if(j>i){L.R[j]=L.R[i];j--;}}while(i!=j);/*i=j時退出掃描*/L.R[i]=L.R[0];returni;}⑵

快速排序算法實(shí)現(xiàn)

當(dāng)進(jìn)行一趟快速排序后，采用同樣方法分別對兩個子序列快速排序，直到子序列數(shù)據(jù)元素個數(shù)為1為止。publicvoidquick_Sort(SqlistL,intlow,inthigh){intk;if(low<high){k=quick_one_pass(L,low,high);quick_Sort(L,low,k-1);quick_Sort(L,k+1,high);}/*序列分為兩部分后分別對每個子序列排序*/}6算法分析

快速排序的主要時間是花費(fèi)在劃分上，對長度為k的數(shù)據(jù)元素序列進(jìn)行劃分時關(guān)鍵字的比較次數(shù)是k-1。設(shè)長度為n的數(shù)據(jù)元素序列進(jìn)行排序的比較次數(shù)為C(n)，則C(n)=n-1+C(k)+C(n-k-1)?！?/p>

最好情況：每次劃分得到的子序列大致相等，則C(n)≤n+2×C(n/2)+C(n-k-1)≤n+2×[n/2+2×C((n/2)/2)≤2n+4×C(n/4)≤…≤h×n+2h×C(n/2h)，當(dāng)n/2h=1時排序結(jié)束。即C(n)≤n×㏒2n+n×C(1)，C(1)看成常數(shù)因子，即C(n)≤O(n×㏒2n)

；◆

最壞情況：每次劃分得到的子序列中有一個為空，另一個子序列的長度為n-1。即每次劃分所選擇的基準(zhǔn)是當(dāng)前待排序序列中的最小(或最大)關(guān)鍵字。比較次數(shù)：∑(n-i)=n-1i=1n(n-1)2即C(n)=O(n2)◆

一般情況：對n個數(shù)據(jù)元素進(jìn)行快速排序所需的時間T(n)組成是：①對n個數(shù)據(jù)元素進(jìn)行一趟劃分所需的時間是：n×C，C是常數(shù)；②對所得到的兩個子序列進(jìn)行快速排序的時間：Tavg(n)=C(n)+Tavg(k-1)+Tavg(n-k)……⑴若數(shù)據(jù)元素是隨機(jī)排列的，k取值在1~n之間的概率相同，則：Tavg(n)=n×C+∑[Tavg(k-1)+Tavg(n-k)]nk=01n=n×C+∑Tavg(k)……⑵n-1k=02n當(dāng)n>1時，用n-1代替⑵中的n，得到：Tavg(n)=(n-1)×C+∑Tavg(k)……⑶n-2k=02n∴nTavg(n)-(n-1)Tavg(n-1)=(2n-1)×C+2Tavg(n-1)，即Tavg(n)=(n+1)/n×Tavg(n-1)+(2n-1)/n×C<(n+1)/n×Tavg(n-1)+2C<(n+1)/n×[n/(n-1)×Tavg(n-2)+2C]+2C=(n+1)/(n-1)×Tavg(n-2)+2(n+1)[1/n+1/(n+1)]×C<…Tavg(1)+2(n+1)×C[2n+13141+1n+1n1+…++]∴Tavg(n)<只有1個數(shù)據(jù)元素的排序時間是一個常數(shù)，∴快速排序的平均時間復(fù)雜度是：T(n)=O(n㏒2n)

從所需要的附加空間來看，快速排序算法是遞歸調(diào)用，系統(tǒng)內(nèi)用堆棧保存遞歸參數(shù)，當(dāng)每次劃分比較均勻時，棧的最大深度為[㏒2n]+1

?！嗫焖倥判虻目臻g復(fù)雜度是：S(n)=O(㏒2n)

從排序的穩(wěn)定性來看，快速排序是不穩(wěn)定的。9.4

選擇排序

選擇排序(SelectionSort)的基本思想是：每次從當(dāng)前待排序的數(shù)據(jù)元素中選取關(guān)鍵字最小的數(shù)據(jù)元素，然后與待排序的數(shù)據(jù)元素序列中的第一個數(shù)據(jù)元素進(jìn)行交換，直到整個數(shù)據(jù)元素序列有序?yàn)橹埂?/p>

9.4.1

簡單選擇排序

簡單選擇排序(SimpleSelectionSort

，又稱為直接選擇排序)的基本操作是：通過n-i次關(guān)鍵字間的比較，從n-i+1個數(shù)據(jù)元素中選取關(guān)鍵字最小的數(shù)據(jù)元素，然后和第i個數(shù)據(jù)元素進(jìn)行交換，i=1,2,…n-1。1排序示例

例：設(shè)有關(guān)鍵字序列為：7,4,-2,19,13,6，直接選擇排序的過程如下圖9-8所示。圖9-8直接選擇排序的過程初始數(shù)據(jù)元素的關(guān)鍵字：74-219136第一趟排序：-24719136第二趟排序：-24719136第三趟排序：-24619137第四趟排序：-24671319第五趟排序：-24671319第六趟排序：-246713

192算法實(shí)現(xiàn)publicstaticvoidsimple_selection_sort(SqlistL){inti,j,k;for(i=1;i<L.n;i++){ k=i; for(j=i+1;j<=L.n;j++) if(L.R[j].key<L.R[k].key) k=j; if(k!=i)/*數(shù)據(jù)元素交換*/ { L.R[0]=L.R[i]; L.R[i]=L.R[k]; L.R[k]=L.R[0]; }}}3算法分析整個算法是二重循環(huán)：外循環(huán)控制排序的趟數(shù)，對n個數(shù)據(jù)元素進(jìn)行排序的趟數(shù)為n-1趟；內(nèi)循環(huán)控制每一趟的排序。進(jìn)行第i趟排序時，關(guān)鍵字的比較次數(shù)為n-i，則：比較次數(shù)：∑(n-i)=n-1i=1n(n-1)2

∴時間復(fù)雜度是：T(n)=O(n2)

空間復(fù)雜度是：S(n)=O(1)

從排序的穩(wěn)定性來看，直接選擇排序是不穩(wěn)定的。9.4.2樹形選擇排序

借助“淘汰賽”中的對壘就很容易理解樹形選擇排序的思想。首先對n個數(shù)據(jù)元素的關(guān)鍵字兩兩進(jìn)行比較，選取

n/2

個較小者；然后這

n/2

個較小者兩兩進(jìn)行比較，選取

n/4

個較小者…如此重復(fù)，直到只剩1個關(guān)鍵字為止。該過程可用一棵有n個葉子結(jié)點(diǎn)的完全二叉樹表示，如圖9-9所示。每個枝結(jié)點(diǎn)的關(guān)鍵字都等于其左、右孩子結(jié)點(diǎn)中較小的關(guān)鍵字，根結(jié)點(diǎn)的關(guān)鍵字就是最小的關(guān)鍵字。輸出最小關(guān)鍵字后，根據(jù)關(guān)系的可傳遞性，欲選取次小關(guān)鍵字，只需將葉子結(jié)點(diǎn)中的最小關(guān)鍵字改為“最大值”，然后重復(fù)上述步驟即可。含有n個葉子結(jié)點(diǎn)的完全二叉樹的深度為

㏒2n

+1，則總的時間復(fù)雜度為O(n㏒2n)

。492525372828196519153415251515圖9-９“淘汰賽”過程示意圖9.4.3堆排序1堆的定義

是n個元素的序列H={k1,k2,…kn}，滿足：ki≤k2i當(dāng)2i≤n時ki≤k2i+1當(dāng)2i+1≤n時或ki≥k2i當(dāng)2i≤n時ki≥k2i+1當(dāng)2i+1≤n時其中：

i=1,2,…,

n/2

由堆的定義知，堆是一棵以k1為根的完全二叉樹。若對該二叉樹的結(jié)點(diǎn)進(jìn)行編號(從上到下，從左到右)，得到的序列就是將二叉樹的結(jié)點(diǎn)以順序結(jié)構(gòu)存放，堆的結(jié)構(gòu)正好和該序列結(jié)構(gòu)完全一致。2堆的性質(zhì)①堆是一棵采用順序存儲結(jié)構(gòu)的完全二叉樹，k1是根結(jié)點(diǎn)；②堆的根結(jié)點(diǎn)是關(guān)鍵字序列中的最小(或最大)值，分別稱為小(或大)根堆；③從根結(jié)點(diǎn)到每一葉子結(jié)點(diǎn)路徑上的元素組成的序列都是按元素值(或關(guān)鍵字值)非遞減(或非遞增)的；堆中的任一子樹也是堆。

3堆排序思想

利用堆頂數(shù)據(jù)元素的關(guān)鍵字值最小(或最大)的性質(zhì)，從當(dāng)前待排序的數(shù)據(jù)元素中依次選取關(guān)鍵字最小(或最大)的數(shù)據(jù)元素，就可以實(shí)現(xiàn)對數(shù)據(jù)數(shù)據(jù)元素的排序，這種排序方法稱為堆排序。步驟如下：①對一組待排序的數(shù)據(jù)元素，按堆的定義建立堆；②將堆頂數(shù)據(jù)元素和最后一個數(shù)據(jù)元素交換位置，則前n-1個數(shù)據(jù)元素是無序的，而最后一個數(shù)據(jù)元素是有序的；③堆頂數(shù)據(jù)元素被交換后，前n-1個數(shù)據(jù)元素不再是堆，需將前n-1個待排序數(shù)據(jù)元素重新組織成為一個堆，然后將堆頂數(shù)據(jù)元素和倒數(shù)第二個數(shù)據(jù)元素交換位置，即將整個序列中次小關(guān)鍵字值的數(shù)據(jù)元素調(diào)整(排除)出無序區(qū)；④重復(fù)上述步驟，直到全部數(shù)據(jù)元素排好序?yàn)橹埂?/p>

結(jié)論：排序過程中，若采用小根堆，排序后得到的是非遞減序列；若采用大根堆，排序后得到的是非遞增序列。堆排序的關(guān)鍵①如何由一個無序序列建成一個堆？②如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？

4堆的調(diào)整——篩選⑴堆的調(diào)整思想

輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直到是葉子結(jié)點(diǎn)或其關(guān)鍵字值小于等于左、右子樹的關(guān)鍵字的值，將得到新的堆。稱這個從堆頂至葉子的調(diào)整過程為“篩選”，如圖所示。注意：篩選過程中，根結(jié)點(diǎn)的左、右子樹都是堆，因此，篩選是從根結(jié)點(diǎn)到某個葉子結(jié)點(diǎn)的一次調(diào)整過程。

堆的篩選過程492537281965341829154925372819653429181549293728196534251815492537281965341815295堆的建立

利用篩選算法，可以將任意無序的數(shù)據(jù)元素序列建成一個堆，設(shè)R[1],R[2],…,R[n]是待排序的數(shù)據(jù)元素序列。將二叉樹的每棵子樹都篩選成為堆。只有根結(jié)點(diǎn)的樹是堆。第

n/2

個結(jié)點(diǎn)之后的所有結(jié)點(diǎn)都沒有子樹，即以第

n/2

個結(jié)點(diǎn)之后的結(jié)點(diǎn)為根的子樹都是堆。因此，以這些結(jié)點(diǎn)為左、右孩子的結(jié)點(diǎn)，其左、右子樹都是堆，則進(jìn)行一次篩選就可以成為堆。同理，只要將這些結(jié)點(diǎn)的直接父結(jié)點(diǎn)進(jìn)行一次篩選就可以成為堆…。只需從第

n/2

個數(shù)據(jù)元素到第1個數(shù)據(jù)元素依次進(jìn)行篩選就可以建立堆。

6堆排序算法實(shí)現(xiàn)

堆的根結(jié)點(diǎn)是關(guān)鍵字最小的數(shù)據(jù)元素，輸出根結(jié)點(diǎn)后，是以序列的最后一個數(shù)據(jù)元素作為根結(jié)點(diǎn)，而原來堆的左、右子樹都是堆，則進(jìn)行一次篩選就可以成為堆。7算法分析

主要過程：初始建堆和重新調(diào)整成堆。設(shè)數(shù)據(jù)元素個數(shù)為n，所對應(yīng)的完全二叉樹深度為h。◆

初始建堆：每個非葉子結(jié)點(diǎn)都要從上到下做“篩選”。第i層結(jié)點(diǎn)數(shù)≤2i-1，結(jié)點(diǎn)下移的最大深度是h-i，而每下移一層要比較2次，則比較次數(shù)C1(n)為：C1(n)≤2∑(2i-1×(h-i))≤4(2h-h-1)h-1i=1∵h(yuǎn)=

㏒2n

+1，∴C1(n)≤4(n-㏒2n-1)◆

篩選調(diào)整：每次篩選要將根結(jié)點(diǎn)“下沉”到一個合適位置。第i次篩選時：堆中元素個數(shù)為n-i+1；堆的深度是

㏒2(n-i+1)

+1，則進(jìn)行n-1次“篩選”的比較次數(shù)C2(n)為：C2(n)≤∑(2×㏒2(n-i+1))n-1i=1∴C2(n)<2n㏒2n∴

堆排序的比較次數(shù)的數(shù)量級為：T(n)=O(n㏒2n)；而附加空間就是交換時所用的臨時空間，故空間復(fù)雜度為：S(n)=O(1)。9.5

歸并排序

歸并(Merging)：是指將兩個或兩個以上的有序序列合并成一個有序序列。若采用線性表(無論是那種存儲結(jié)構(gòu))易于實(shí)現(xiàn)，其時間復(fù)雜度為O(m+n)。

歸并思想實(shí)例：兩堆撲克牌，都已從小到大排好序，要將兩堆合并為一堆且要求從小到大排序?！?/p>

將兩堆最上面的抽出(設(shè)為C1，C2)比較大小，將小者置于一邊作為新的一堆(不妨設(shè)C1<C2)；再從第一堆中抽出一張繼續(xù)與C2進(jìn)行比較，將較小的放置在新堆的最下面；◆

重復(fù)上述過程，直到某一堆已抽完，然后將剩下一堆中的所有牌轉(zhuǎn)移到新堆中。1排序思想

①初始時，將每個數(shù)據(jù)元素看成一個單獨(dú)的有序序列，則n個待排序數(shù)據(jù)元素就是n個長度為1的有序子序列；②對所有有序子序列進(jìn)行兩兩歸并，得到

n/2

個長度為2或1的有序子序列——一趟歸并；③重復(fù)②，直到得到長度為n的有序序列為止。上述排序過程中，子序列總是兩兩歸并，稱為2-路歸并排序。其核心是如何將相鄰的兩個子序列歸并成一個子序列。設(shè)相鄰的兩個子序列分別為：{R[k],R[k+1],…,R[m]}和{R[m+1],R[m+2],…,R[h]}，將它們歸并為一個有序的子序列：{DR[l],DR[l+1],…,DR[m],DR[m+1],…,DR[h]}例：設(shè)有9個待排序的數(shù)據(jù)元素，關(guān)鍵字分別為23,38,22,45,23,67,31,15,41，歸并排序的過程如下所示。

歸并排序過程[23][38][22][45][23][67][31][15][41]初始關(guān)鍵字:[2338][2245][2367][1531][41]一趟歸并后:[22233845][15233167][41]二趟歸并后:[152223233138

4567][41]三趟歸并后:[152223233138

414567四趟歸并后:歸并的算法publicvoidMerge(DataType[]R,DataType[]DR,intk,intm,inth){ intp,q,n; p=n=k; q=m+1; while((p<=m)&&(q<=h)){ if(R[p].key<=R[q].key)/*比較兩個子序列*/ DR[n++]=R[p++]; else DR[n++]=R[q++]; } while(p<=m)/*將剩余子序列復(fù)制到結(jié)果序列中*/ DR[n++]=R[p++]; while(q<=h) DR[n++]=R[q++];}2一趟歸并排序一趟歸并排序都是從前到后，依次將相鄰的兩個有序子序列歸并為一個，且除最后一個子序列外，其余每個子序列的長度都相同。設(shè)這些子序列的長度為d，則一趟歸并排序的過程是：

從j=1開始，依次將相鄰的兩個有序子序列R[j…j+d-1]和R[j+d…j+2d-1]進(jìn)行歸并；每次歸并兩個子序列后，j后移動2d個位置，即j=j+2d；若剩下的元素不足兩個子序列時，分以下兩種情況處理：①剩下的元素個數(shù)>d：再調(diào)用一次上述過程，將一個長度為d的子序列和不足d的子序列進(jìn)行歸并；②剩下的元素個數(shù)≤d：將剩下的元素依次復(fù)制到歸并后的序列中。⑴一趟歸并排序算法publicvoidMerge_pass(DataType[]R,DataType[]DR,intd,intn){ intj=1; while((j+2*d-1)<=n){ Merge(R,DR,j,j+d-1,j+2*d-1); j=j+2*d; }/*子序列兩兩歸并*/ if(j+d-1<n)/*剩余元素個數(shù)超過一個子序列長度d*/ Merge(R,DR,j,j+d-1,n); else Merge(R,DR,j,n,n);/*剩余子序列復(fù)制*/}⑵

歸并排序的算法

開始?xì)w并時，每個數(shù)據(jù)元素是長度為1的有序子序列，對這些有序子序列逐趟歸并，每一趟歸并后有序子序列的長度均擴(kuò)大一倍；當(dāng)有序子序列的長度與整個數(shù)據(jù)元素序列長度相等時，整個數(shù)據(jù)元素序列就成為有序序列。算法是：publicvoidMerge_sort(SqlistL,DataType[]DR){ intd=1; while(d<L.n){ Merge_pass(L.R,DR,d,L.n); Merge_pass(DR,L.R,2*d,L.n); d=4*d; }}9.6

基數(shù)排序

基數(shù)排序(RadixSorting)

又稱為桶排序或數(shù)字排序：按待排序數(shù)據(jù)元素的關(guān)鍵字的組成成分(或“位”)進(jìn)行排序?；鶖?shù)排序和前面的各種內(nèi)部排序方法完全不同，不需要進(jìn)行關(guān)鍵字的比較和數(shù)據(jù)元素的移動。借助于多關(guān)鍵字排序思想實(shí)現(xiàn)單邏輯關(guān)鍵字的排序。9.6.1多關(guān)鍵字排序

設(shè)有n個數(shù)據(jù)元素{R1,R2,…,Rn}，每個數(shù)據(jù)元素Ri的關(guān)鍵字是由若干項(xiàng)(數(shù)據(jù)項(xiàng))組成，即數(shù)據(jù)元素Ri的關(guān)鍵字Key是若干項(xiàng)的集合：{Ki1,Ki2,…,Kid}(d>1)。數(shù)據(jù)元素{R1,R2,…,Rn}有序的，指的是

i,j∈[1,n]，i<j，若數(shù)據(jù)元素的關(guān)鍵字滿足：{Ki1,Ki2,…Kid}

≤{Kj1,Kj2,…Kjd}，即Kip≤Kjp(p=1,2,…d)多關(guān)鍵字排序思想先按第一個關(guān)鍵字K1進(jìn)行排序，將數(shù)據(jù)元素序列分成若干個子序列，每個子序列有相同的K1值；然后分別對每個子序列按第二個關(guān)鍵字K2進(jìn)行排序，每個子序列又被分成若干個更小的子序列；如此重復(fù)，直到按最后一個關(guān)鍵字Kd進(jìn)行排序。最后，將所有的子序列依次聯(lián)接成一個有序的數(shù)據(jù)元素序列，該方法稱為最高位優(yōu)先(MostSignificantDigitfirst)。另一種方法正好相反，排序的順序是從最低位開始，稱為最低位優(yōu)先(LeastSignificantDigitfirst)。9.6.2鏈?zhǔn)交鶖?shù)排序若數(shù)據(jù)元素的關(guān)鍵字由若干確定的部分(又稱為“位”)組成，每一位(部分)都有確定數(shù)目的取值。對這樣的數(shù)據(jù)元素序列排序的有效方法是基數(shù)排序。設(shè)有n個待排序數(shù)據(jù)元素{R1,R2,…,Rn}，(單)關(guān)鍵字是由d位(部分)組成，每位有r種取值，則關(guān)鍵字R[i].key可以看成一個d元組：R[i].key={Ki1,Ki2,…,Kid}。基數(shù)排序可以采用前面介紹的MSD或LSD方法。以下以LSD方法討論鏈?zhǔn)交鶖?shù)排序。1