嚴蔚敏數(shù)據(jù)結(jié)構(gòu)課件第九章

第10章內(nèi)部排序

在信息處理過程中，最基本的操作是查找。從查找來說，效率最高的是折半查找，折半查找的前提是所有的數(shù)據(jù)元素(記錄)是按關(guān)鍵字有序的。需要將一個無序的數(shù)據(jù)文件轉(zhuǎn)變?yōu)橐粋€有序的數(shù)據(jù)文件。將任一文件中的記錄通過某種方法整理成為按(記錄)關(guān)鍵字有序排列的處理過程稱為排序。排序是數(shù)據(jù)處理中一種最常用的操作。10.1

排序的基本概念⑴

排序(Sorting)

排序是將一批(組)任意次序的記錄重新排列成按關(guān)鍵字有序的記錄序列的過程，其定義為：給定一組記錄序列：{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可以是記錄Ri的主關(guān)鍵字，也可以是次關(guān)鍵字或若干數(shù)據(jù)項的組合。

◆

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

◆

Ki是次關(guān)鍵字：排序后得到的結(jié)果是不唯一的。⑵排序的穩(wěn)定性若記錄序列中有兩個或兩個以上關(guān)鍵字相等的記錄：Ki=Kj(i≠j，i,j=1,2,…n)，且在排序前Ri先于Rj(i<j)，排序后的記錄序列仍然是Ri先于Rj，稱排序方法是穩(wěn)定的，否則是不穩(wěn)定的。排序算法有許多，但就全面性能而言，還沒有一種公認為最好的。每種算法都有其優(yōu)點和缺點，分別適合不同的數(shù)據(jù)量和硬件配置。評價排序算法的標準有：執(zhí)行時間和所需的輔助空間，其次是算法的穩(wěn)定性。

若排序算法所需的輔助空間不依賴問題的規(guī)模n，即空間復(fù)雜度是O(1)，則稱排序方法是就地排序，否則是非就地排序。⑶排序的分類待排序的記錄數(shù)量不同，排序過程中涉及的存儲器的不同，有不同的排序分類。①待排序的記錄數(shù)不太多：所有的記錄都能存放在內(nèi)存中進行排序，稱為內(nèi)部排序；②待排序的記錄數(shù)太多：所有的記錄不可能存放在內(nèi)存中，排序過程中必須在內(nèi)、外存之間進行數(shù)據(jù)交換，這樣的排序稱為外部排序。⑷內(nèi)部排序的基本操作對內(nèi)部排序地而言，其基本操作有兩種：◆

比較兩個關(guān)鍵字的大??；◆

存儲位置的移動：從一個位置移到另一個位置。第一種操作是必不可少的；而第二種操作卻不是必須的，取決于記錄的存儲方式，具體情況是：①

記錄存儲在一組連續(xù)地址的存儲空間：記錄之間的邏輯順序關(guān)系是通過其物理存儲位置的相鄰來體現(xiàn)，記錄的移動是必不可少的；②

記錄采用鏈式存儲方式：記錄之間的邏輯順序關(guān)系是通過結(jié)點中的指針來體現(xiàn)，排序過程僅需修改結(jié)點的指針，而不需要移動記錄；③記錄存儲在一組連續(xù)地址的存儲空間：構(gòu)造另一個輔助表來保存各個記錄的存放地址(指針)：排序過程不需要移動記錄，而僅需修改輔助表中的指針，排序后視具體情況決定是否調(diào)整記錄的存儲位置。①比較適合記錄數(shù)較少的情況；而②、③則適合記錄數(shù)較少的情況。為討論方便，假設(shè)待排序的記錄是以①的情況存儲，且設(shè)排序是按升序排列的；關(guān)鍵字是一些可直接用比較運算符進行比較的類型。待排序的記錄類型的定義如下：#defineMAX_SIZE100TypedefintKeyType;typedefstructRecType{KeyTypekey;/*關(guān)鍵字碼*/infoTypeotherinfo;/*其他域*/}RecType;typedefstructSqlist{RecTypeR[MAX_SIZE];intlength;}Sqlist;10.2

插入排序

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

直接插入排序1排序思想將待排序的記錄Ri，插入到已排好序的記錄表R1,R2,….,Ri-1中，得到一個新的、記錄數(shù)增加1的有序表。直到所有的記錄都插入完為止。設(shè)待排序的記錄順序存放在數(shù)組R[1…n]中，在排序的某一時刻，將記錄序列分成兩部分：◆

R[1…i-1]：已排好序的有序部分；◆

R[i…n]：未排好序的無序部分。顯然，在剛開始排序時，R[1]是已經(jīng)排好序的。

例：設(shè)有關(guān)鍵字序列為：7,4,-2,19,13,6，直接插入排序的過程如下圖10-1所示：初始記錄的關(guān)鍵字：[7]4-219136第一趟排序：[47]-219136第二趟排序：[-247]19136第三趟排序：[-24719]136第四趟排序：[-2471319]6第五趟排序：[-24671319]圖10-1直接插入排序的過程2算法實現(xiàn)voidstraight_insert_sort(Sqlist*L){inti,j;for(i=2;i<=L->length;i++){L->R[0]=L->R[i];j=i-1;/*設(shè)置哨兵*/while(LT(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算法說明算法中的R[0]開始時并不存放任何待排序的記錄，引入的作用主要有兩個：①不需要增加輔助空間：保存當前待插入的記錄R[i]，R[i]會因為記錄的后移而被占用；②保證查找插入位置的內(nèi)循環(huán)總可以在超出循環(huán)邊界之前找到一個等于當前記錄的記錄，起“哨兵監(jiān)視”作用，避免在內(nèi)循環(huán)中每次都要判斷j是否越界。4

算法分析⑴最好情況：若待排序記錄按關(guān)鍵字從小到大排列(正序)，算法中的內(nèi)循環(huán)無須執(zhí)行，則一趟排序時：關(guān)鍵字比較次數(shù)1次，記錄移動次數(shù)2次(R[i]→R[0],R[0]→R[j+1])。則整個排序的關(guān)鍵字比較次數(shù)和記錄移動次數(shù)分別是：比較次數(shù)：∑1=n-1ni=2移動次數(shù)：∑2=2(n-1)ni=2⑵最壞情況：若待排序記錄按關(guān)鍵字從大到小排列(逆序)，則一趟排序時：算法中的內(nèi)循環(huán)體執(zhí)行i-1，關(guān)鍵字比較次數(shù)i次，記錄移動次數(shù)i+1。則就整個排序而言：比較次數(shù)：∑i=ni=2(n-1)(n+1)2移動次數(shù)：∑(i+1)=ni=2(n-1)(n+4)2

一般地，認為待排序的記錄可能出現(xiàn)的各種排列的概率相同，則取以上兩種情況的平均值，作為排序的關(guān)鍵字比較次數(shù)和記錄移動次數(shù)，約為n2/4，則復(fù)雜度為O(n2)。10.2.2其它插入排序1折半插入排序

當將待排序的記錄R[i]插入到已排好序的記錄子表R[1…i-1]中時，由于R1,R2,…,Ri-1已排好序，則查找插入位置可以用“折半查找”實現(xiàn)，則直接插入排序就變成為折半插入排序。⑴算法實現(xiàn)voidBinary_insert_sort(Sqlist*L){inti,j,low,high,mid;for(i=2;i<=L->length;i++){L->R[0]=L->R[i];/*設(shè)置哨兵*/low=1;high=i-1;while(low<=high){if(LT(L->R[0].key,L->R[mid].key))high=mid-1;elselow=mid+1;}

/*查找插入位置*/for(j=i-1;j>=high+1;j--)L->R[j+1]=L->R[j];L->R[high+1]=L->R[0];/*插入到相應(yīng)位置*/}}

從時間上比較，折半插入排序僅僅減少了關(guān)鍵字的比較次數(shù)，卻沒有減少記錄的移動次數(shù)，故時間復(fù)雜度仍然為O(n2)。⑵

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

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

1

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

201------i=3MAXINT4938651397277649

231

0-----i=4MAXINT4938651397277649

4310

2----i=5MAXINT4938651397277649

43152

0---

和直接插入排序相比，不同的是修改2n次指針值以代替移動記錄，而關(guān)鍵字的比較次數(shù)相同，故時間復(fù)雜度為O(n2)。表插入排序得到一個有序鏈表，對其可以方便地進行順序查找，但不能實現(xiàn)隨即查找。根據(jù)需要，可以對記錄進行重排，記錄重排詳見P268。i=6MAXINT4938651397277649

43156

02--i=7MAXINT4938651397277649

43176

025-i=8MAXINT4938651397277649

48176

0253圖10-4表插入排序過程10.2.3希爾排序

希爾排序(ShellSort，又稱縮小增量法)是一種分組插入排序方法。1排序思想①先取一個正整數(shù)d1(d1<n)作為第一個增量，將全部n個記錄分成d1組，把所有相隔d1的記錄放在一組中，即對于每個k(k=1,2,…d1)，R[k],R[d1+k],R[2d1+k],…分在同一組中，在各組內(nèi)進行直接插入排序。這樣一次分組和排序過程稱為一趟希爾排序；②取新的增量d2<d1，重復(fù)①的分組和排序操作；直至所取的增量di=1為止，即所有記錄放進一個組中排序為止。2排序示例設(shè)有10個待排序的記錄，關(guān)鍵字分別為9,13,8,2,5,13,7,1,15,11，增量序列是5,3,1，希爾排序的過程如圖10-5所示。97125131381511第一趟排序后:25197131181513第二趟排序后:12578911131315第三趟排序后:圖10-5希爾排序過程9138251371151171318初始關(guān)鍵字序列:第一趟排序過程:3算法實現(xiàn)先給出一趟希爾排序的算法，類似直接插入排序。voidshell_pass(Sqlist*L,intd)/*對順序表L進行一趟希爾排序,增量為d*/{intj,k;for(j=d+1;j<=L->length;j++){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+j]=L->R[0];}}

然后在根據(jù)增量數(shù)組dk進行希爾排序。voidshell_sort(Sqlist*L,intdk[],intt)/*按增量序列dk[0…t-1],對順序表L進行希爾排序*/{intm;for(m=0;m<=t;m++)shll_pass(L,dk[m]);}

希爾排序的分析比較復(fù)雜，涉及一些數(shù)學上的問題，其時間是所取的“增量”序列的函數(shù)。希爾排序特點子序列的構(gòu)成不是簡單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列。

希爾排序可提高排序速度，原因是：◆分組后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了；◆關(guān)鍵字較小的記錄跳躍式前移，在進行最后一趟增量為1的插入排序時，序列已基本有序。增量序列取法◆無除1以外的公因子；◆最后一個增量值必須為1。10.3

快速排序

是一類基于交換的排序，系統(tǒng)地交換反序的記錄的偶對，直到不再有這樣一來的偶對為止。其中最基本的是冒泡排序(BubbleSort)。10.3.1冒泡排序1排序思想

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

設(shè)有9個待排序的記錄，關(guān)鍵字分別為23,38,22,45,23,67,31,15,41，冒泡排序的過程如圖10-6所示。3算法實現(xiàn)#defineFALSE0#defineTRUE1圖10-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

67voidBubble_Sort(Sqlist*L){intj,k,flag;for(j=0;j<L->length;j++)/*共有n-1趟排序*/{flag=TRUE;for(k=1;k<=L->length-j;k++)/*一趟排序*/if(LT(L->R[k+1].key,L->R[k].key)){flag=FALSE;L->R[0]=L->R[k];L->R[k]=L->R[k+1];L->R[k+1]=L->R[0];}if(flag==TRUE)break;}}故時間復(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)210.3.2快速排序1排序思想通過一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，再分別對這兩部分記錄進行下一趟排序，以達到整個序列有序。2排序過程設(shè)待排序的記錄序列是R[s…t]，在記錄序列中任取一個記錄(一般取R[s])作為參照(又稱為基準或樞軸)，以R[s].key為基準重新排列其余的所有記錄，方法是：◆

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

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

從序列的兩端交替掃描各個記錄，將關(guān)鍵字小于基準關(guān)鍵字的記錄依次放置到序列的前邊；而將關(guān)鍵字大于基準關(guān)鍵字的記錄從序列的最后端起，依次放置到序列的后邊，直到掃描完所有的記錄。設(shè)置指針low，high，初值為第1個和最后一個記錄的位置。

設(shè)兩個變量i，j，初始時令i=low，j=high，以R[low].key作為基準(將R[low]保存在R[0]中)。①從j所指位置向前搜索：將R[0].key與R[j].key進行比較：◆

若R[0].key≤R[j].key：令j=j-1，然后繼續(xù)進行比較，直到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進行比較：◆

若R[0].key≥R[i].key：令i=i+1，然后繼續(xù)進行比較，直到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](基準)所應(yīng)放置的位置。4一趟排序示例

設(shè)有6個待排序的記錄，關(guān)鍵字分別為29,38,22,45,23,67，一趟快速排序的過程如圖10-7所示。5算法實現(xiàn)⑴

一趟快速排序算法的實現(xiàn)intquick_one_pass(Sqlist*L,intlow,inthigh){inti=low,j=high;圖10-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的位置重合:L->R[0]=L->R[i];/*R[0]作為臨時單元和哨兵*/do{while(LQ(L->R[0].key,L->R[j].key)&&(j>i))j--;if(j>i){L->R[i]=L->R[j];i++;}while(LQ(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];return(i);}⑵

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

當進行一趟快速排序后，采用同樣方法分別對兩個子序列快速排序，直到子序列記錄個為1為止。①遞歸算法

voidquick_Sort(Sqlist*L,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);}/*序列分為兩部分后分別對每個子序列排序*/}②

非遞歸算法#defineMAX_STACK100voidquick_Sort(Sqlist*L,intlow,inthigh){intk,stack[MAX_STACK],top=0;do{while(low<high){k=quick_one_pass(L,low,high);stack[++top]=high;stack[++top]=k+1;

/*第二個子序列的上,下界分別入棧*/high=k-1;}if(top!=0){low=stack[top--];high=stack[top--];}}while(top!=0&&low<high);}6算法分析

快速排序的主要時間是花費在劃分上，對長度為k的記錄序列進行劃分時關(guān)鍵字的比較次數(shù)是k-1。設(shè)長度為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)，當n/2h=1時排序結(jié)束。即C(n)≤n×㏒2n+n×C(1)，C(1)看成常數(shù)因子，即C(n)≤O(n×㏒2n)

；◆

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

一般情況：對n個記錄進行快速排序所需的時間T(n)組成是：①對n個記錄進行一趟劃分所需的時間是：n×C，C是常數(shù)；②對所得到的兩個子序列進行快速排序的時間：Tavg(n)=C(n)+Tavg(k-1)+Tavg(n-k)……⑴

若記錄是隨機排列的，k取值在1~n之間的概率相同，則：Tavg(n)=n×C+∑[Tavg(k-1)+Tavg(n-k)]nk=01n=n×C+∑Tavg(k)……⑵n-1k=02n

當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ù)，∴快速排序的平均時間復(fù)雜度是：T(n)=O(n㏒2n)

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

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

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

選擇排序

選擇排序(SelectionSort)的基本思想是：每次從當前待排序的記錄中選取關(guān)鍵字最小的記錄表，然后與待排序的記錄序列中的第一個記錄進行交換，直到整個記錄序列有序為止。

10.4.1

簡單選擇排序

簡單選擇排序(SimpleSelectionSort

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

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

192算法實現(xiàn)voidsimple_selection_sort(Sqlist*L){intm,n,k;for(m=1;m<L->length;m++){k=m;for(n=m+1;n<=L->length;n++)if(LT(L->R[n].key,L->R[k].key))k=n;if(k!=m)/*記錄交換*/{L->R[0]=L->R[m];L->R[m]=L->R[k];L->R[k]=L->R[0];}}}3算法分析整個算法是二重循環(huán)：外循環(huán)控制排序的趟數(shù)，對n個記錄進行排序的趟數(shù)為n-1趟；內(nèi)循環(huá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)定的。10.4.2樹形選擇排序

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

n/2

個較小者；然后這

n/2

個較小者兩兩進行比較，選取

n/4

個較小者…

如此重復(fù)，直到只剩1個關(guān)鍵字為止。該過程可用一棵有n個葉子結(jié)點的完全二叉樹表示，如圖10-9所示。每個枝結(jié)點的關(guān)鍵字都等于其左、右孩子結(jié)點中較小的關(guān)鍵字，根結(jié)點的關(guān)鍵字就是最小的關(guān)鍵字。

輸出最小關(guān)鍵字后，根據(jù)關(guān)系的可傳遞性，欲選取次小關(guān)鍵字，只需將葉子結(jié)點中的最小關(guān)鍵字改為“最大值”，然后重復(fù)上述步驟即可。含有n個葉子結(jié)點的完全二叉樹的深度為

㏒2n

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

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

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

i=1,2,…,

n/2

由堆的定義知，堆是一棵以k1為根的完全二叉樹。若對該二叉樹的結(jié)點進行編號(從上到下，從左到右)，得到的序列就是將二叉樹的結(jié)點以順序結(jié)構(gòu)存放，堆的結(jié)構(gòu)正好和該序列結(jié)構(gòu)完全一致。2堆的性質(zhì)①堆是一棵采用順序存儲結(jié)構(gòu)的完全二叉樹，k1是根結(jié)點；②堆的根結(jié)點是關(guān)鍵字序列中的最小(或最大)值，分別稱為小(或大)根堆；③從根結(jié)點到每一葉子結(jié)點路徑上的元素組成的序列都是按元素值(或關(guān)鍵字值)非遞減(或非遞增)的；堆中的任一子樹也是堆。利用堆頂記錄的關(guān)鍵字值最小(或最大)的性質(zhì)，從當前待排序的記錄中依次選取關(guān)鍵字最小(或最大)的記錄，就可以實現(xiàn)對數(shù)據(jù)記錄的排序，這種排序方法稱為堆排序。3堆排序思想①對一組待排序的記錄，按堆的定義建立堆；②將堆頂記錄和最后一個記錄交換位置，則前n-1個記錄是無序的，而最后一個記錄是有序的；③堆頂記錄被交換后，前n-1個記錄不再是堆，需將前n-1個待排序記錄重新組織成為一個堆，然后將堆頂記錄和倒數(shù)第二個記錄交換位置，即將整個序列中次小關(guān)鍵字值的記錄調(diào)整(排除)出無序區(qū)；④重復(fù)上述步驟，直到全部記錄排好序為止。

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

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

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

堆調(diào)整算法實現(xiàn)voidHeap_adjust(Sqlist*H,ints,intm)/*H->R[s…m]中記錄關(guān)鍵字除H->R[s].key均滿足堆定義*//*調(diào)整H->R[s]的位置使之成為小根堆*/{intj=s,k=2*j;/*計算H->R[j]的左孩子的位置*/H->R[0]=H->R[j];/*臨時保存H->R[j]*/

for(k=2*j;k<=m;k=2*k){if((k<m)&&(LT(H->R[k+1].key,H->R[k].key))k++;/*選擇左、右孩子中關(guān)鍵字的最小者*/if(LT(H->R[k].key,H->R[0].key)){H->R[j]=H->R[k];j=k;k=2*j}elsebreak;}H->R[j]=H->R[0];}5堆的建立

利用篩選算法，可以將任意無序的記錄序列建成一個堆，設(shè)R[1],R[2],…,R[n]是待排序的記錄序列。將二叉樹的每棵子樹都篩選成為堆。只有根結(jié)點的樹是堆。第?n/2?個結(jié)點之后的所有結(jié)點都沒有子樹，即以第

n/2

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

n/2

個記錄到第1個記錄依次進行篩選就可以建立堆?？捎孟铝姓Z句實現(xiàn)：for(j=n/2;j>=1;j--)Heap_adjust(R,j,n);6堆排序算法實現(xiàn)

堆的根結(jié)點是關(guān)鍵字最小的記錄，輸出根結(jié)點后，是以序列的最后一個記錄作為根結(jié)點，而原來堆的左、右子樹都是堆，則進行一次篩選就可以成為堆。voidHeap_Sort(Sqlist*H){intj;for(j=H->length/2;j>0;j--)Heap_adjust(H,j,H->length);/*初始建堆*/for(j=H->length/2;j>=1;j--){H->R[0]=H->R[1];H->R[1]=H->R[j];H->R[j]=H->R[0];/*堆頂與最后一個交換*/Heap_adjust(H,1,j-1);}}7算法分析

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

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

㏒2n

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

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

㏒2(n-i+1)

+1，則進行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)。10.5

歸并排序

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

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

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

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

①初始時，將每個記錄看成一個單獨的有序序列，則n個待排序記錄就是n個長度為1的有序子序列；②對所有有序子序列進行兩兩歸并，得到

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個待排序的記錄，關(guān)鍵字分別為23,38,22,45,23,67,31,15,41，歸并排序的過程如圖10-11所示。圖10-11歸并排序過程[23][38][22][45][23][67][31][15][41]初始關(guān)鍵字:[2338][2245][2367][1531][41]一趟歸并后:[22233845][15233167][41]二趟歸并后:[152223233138

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

414567四趟歸并后:歸并的算法voidMerge(RecTypeR[],RecTypeDR[],intk,intm,inth){intp,q,n;p=n=k,q=m+1;while((p<=m)&&(q<=h)){if(LQ(R[p].key,R[q].key))/*比較兩個子序列*/DR[n++]=R[p++];elseDR[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后移動2d個位置，即j=j+2d；若剩下的元素不足兩個子序列時，分以下兩種情況處理：①剩下的元素個數(shù)>d：再調(diào)用一次上述過程，將一個長度為d的子序列和不足d的子序列進行歸并；②剩下的元素個數(shù)≤d：將剩下的元素依次復(fù)制到歸并后的序列中。⑴一趟歸并排序算法voidMerge_pass(RecTypeR[],RecTypeDR[],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);elseMerge(R,DR,j,n,n);/*剩余子序列復(fù)制*/}⑵

歸并排序的算法

開始歸并時，每個記錄是長度為1的有序子序列，對這些有序子序列逐趟歸并，每一趟歸并后有序子序列的長度均擴大一倍；當有序子序列的長度與整個記錄序列長度相等時，整個記錄序列就成為有序序列。算法是：voidMerge_sort(Sqlist*L,RecTypeDR[]){intd=1;while(d<L->length){Merge_pass(L->R,DR,d,L->length);Merge_pass(DR,L->R,2*d,L->length);d=4*d;}}3算法分析

具有n個待排序記錄的歸并次數(shù)是㏒2n，而一趟歸并的時間復(fù)雜度為O(n)，則整個歸并排序的時間復(fù)雜度無論是最好還是最壞情況均為O(n㏒2n)。在排序過程中，使用了輔助向量DR，大小與待排序記錄空間相同，則空間復(fù)雜度為O(n)。歸并排序是穩(wěn)定的。10.6

基數(shù)排序

基數(shù)排序(RadixSorting)

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

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

i,j∈[1,n]，i<j，若記錄的關(guān)鍵字滿足：{Ki1,Ki2,…Kid}<{Kj1,Kj2,…Kjd}，即Kip≤Kjp(p=1,2,…d)多關(guān)鍵字排序思想先按第一個關(guān)鍵字K1進行排序，將記錄序列分成若干個子序列，每個子序列有相同的K1值；然后分別對每個子序列按第二個關(guān)鍵字K2進行排序，每個子序列又被分成若干個更小的子序列；如此重復(fù)，直到按最后一個關(guān)鍵字Kd進行排序。最后，將所有的子序列依次聯(lián)接成一個有序的記錄序列，該方法稱為最高位優(yōu)先(MostSignificantDigitfirst)。另一種方法正好相反，排序的順序是從最低位開始，稱為最低位優(yōu)先(LeastSignificantDigitfirst)。10.6.2鏈式基數(shù)排序

若記錄的關(guān)鍵字由若干確定的部分(又稱為“位”)組成，每一位(部分)都有確定數(shù)目的取值。對這樣的記錄序列排序的有效方法是基數(shù)排序。設(shè)有n個待排序記錄{R1,R2,…,Rn}，(單)關(guān)鍵字是由d位(部分)組成，每位有r種取值，則關(guān)鍵字R[i].key可以看成一個d元組：R[i].key={Ki1,Ki2,…,Kid}。基數(shù)排序可以采用前面介紹的MSD或LSD方法。以下以LSD方法討論鏈式基數(shù)排序。1排序思想⑴首先以靜態(tài)鏈表存儲n個待排序記錄，頭結(jié)點指針指向第一個記錄結(jié)點；⑵一趟排序的過程是：①分配：按Kd值的升序順序，改變記錄指針，將鏈表中的記錄結(jié)點分配到r個鏈表(桶)中，每個鏈表中所有記錄的關(guān)鍵字的最低位(Kd)的值都相等，用f[i]、e[i]作為第i個鏈表的頭結(jié)點和尾結(jié)點；②收集：改變所有非空鏈表的尾結(jié)點指針，使其指向下一個非空連表的第一個結(jié)點，從而將r個鏈表中的記錄重新鏈接成一個鏈表；⑶如此依次按Kd-1,Kd-2,…K1分別進行，共進行d趟排序后排序完成。2排序示例設(shè)有關(guān)鍵字序列為1039,2121,3355,4382,66,118的一組記錄，采用鏈式基數(shù)排序的過程如下圖10-12所示。103921213355438200660118∧head初始鏈表f[1]f[0]f[2]f[4]f[3]f[5]f[7]f[6]f[8]f[9]e[1]e[0]e[2]e[4]e[3]e[5]e[7]e[6]e[8]e[9]212143823355006601181039分配：212143823355006601181039∧head第一趟收集結(jié)果：01182121f[1]f[0]f[2]f[4]f[3]f[5]f[7]f[6]f[8]f[9]e[1]e[0]e[2]e[4]e[3]e[5]e[7]e[6]e[8]e[9]3355006643821039分配：011821211039335500664382∧head第二趟收集結(jié)果：103900660118212133554382∧head第三趟收集結(jié)果：01182121f[1]f[0]f[2]f[4]f[3]f[5]f[7]f[6]f[8]f[9]e[1]e[0]e[2]e[4]e[3]e[5]e[7]e[6]e[8]e[9]分配：3355438210390066006601181039212133554382∧head第四趟收集結(jié)果：1039f[1]f[0]f[2]f[4]f[3]f[5]f[7]f[6]f[8]f[9]e[1]e[0]e[2]e[4]e[3]e[5]e[7]e[6]e[8]e[9]分配：00660118212133554382圖10-12以LSD方法進行鏈式基數(shù)排序的過程3鏈式基數(shù)排序算法為實現(xiàn)基數(shù)排序，用兩個指針數(shù)組來分別管理所有的緩存(桶)，同時對待排序記錄的數(shù)據(jù)類型進行改造，相應(yīng)的數(shù)據(jù)類型定義如下：#defineBIT_key8/*指定關(guān)鍵字的位數(shù)d*/#defineRADIX10/*指定關(guān)鍵字基數(shù)r*/typedefstructRecType{charkey[BIT_key];/*關(guān)鍵字域*/infoTypeotheritems;structRecType*next;}SRecord,*f[RADIX],*e[RADIX];/*桶的頭尾指針數(shù)組*/voidRadix_sort(SRecord*head){intj,k,m;SRecord*p,*q,*f[RADIX],*e[RADIX];for(j=BIT_key-1;j>=0;j--)/*關(guān)鍵字的每位一趟排序*/{for(k=0;k<RADIX;k++)f[k]=e[k]=NULL;/*頭尾指針數(shù)組初始化*/p=head;while(p!=NULL)/*一趟基數(shù)排序的分配*/{m=ord(p->key[j]);/*取關(guān)鍵字的第j位kj*/if(f[m]==NULL)f[m]=p;elsee[m]->next=p;p=p->next;}head=NULL;/*以head作為頭指針進行收集*/q=head;/*q作為收集后的尾指針*/for(k=0;k<RADIX;k++){if(f[k]!=NULL)/*第k個隊列不空則收集*/{if(head!=NULL)q->next=f[k];elsehead=f[k];q=e[k];}}

/*完成一趟排序的收集

*/q->next=NULL;/*修改收集鏈尾指針

*/}}4算法分析

設(shè)有n個待排序記錄，關(guān)鍵字位數(shù)為d，每位有r種取值。則排序的趟數(shù)是d；在每一趟中：◆鏈表初始化的時間復(fù)雜度：O(r)；◆分配的時間復(fù)雜度：O(n)；◆分配后收集的時間復(fù)雜度：O(r)；則鏈式基數(shù)排序的時間復(fù)雜度為：O(d(n+r))

在排序過程中使用的輔助空間是：2r個鏈表指針，n個指針域空間，則空間復(fù)雜度為：O(n+r)

基數(shù)排序是穩(wěn)定的。10.7

各種內(nèi)部排序的比較

各種內(nèi)部排序按所采用的基本思想(策略)可分為：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序，它們的基本策略分別是：1插入排序：依次將無序序列中的一個記錄，按關(guān)鍵字值的大小插入到已排好序一個子序列的適當位置，直到所有的記錄都插入為止。具體的方法有：直接插入、表插入、2-路插入和shell排序。2交換排序：對于待排序記錄序列中的記錄，兩兩比較記錄的關(guān)鍵字，并對反序的兩個記錄進行交換，直到整個序列中沒有反序的記錄偶對為止。具體的方法有：冒泡排序、快速排序。3選擇排序：不斷地從待排序的記錄序列中選取關(guān)鍵字最小的記錄，放在已排好序的序列的最后，直到所有記錄都被選取為止。具體的方法有：簡單選擇排序、堆排序。4歸并排序：利用“歸并”技術(shù)不斷地對待排序記錄序列中的有序子序列進行合并，直到合并為一個有序序列為止。5基數(shù)排序：按待排序記錄的關(guān)鍵字的組成成分(“位”)從低到高(或從高到低)進行。每次是按記錄關(guān)鍵字某一“位”的值將所有記錄分配到相應(yīng)的桶中，再按桶的編號依次將記錄進行收集，最后得到一個有序序列。各種內(nèi)部排序方法的性能比較如下表。方法平均時間最壞所需時間附加空間穩(wěn)定性直接插入O(n2)O(n2)O(1)穩(wěn)定的Shell排序O(n1.3)O(1)不穩(wěn)定的直接選擇O(n2)O(n2)O(1)不穩(wěn)定的堆排序O(n㏒2n)O(n㏒2n)O(1)不穩(wěn)定的冒泡排序O(n2)O(n2)O(1)穩(wěn)定的快速排序O(n㏒2n)O(n2)O(㏒2n)不穩(wěn)定的歸并排序O(n㏒2n)O(n㏒2n)O(n)穩(wěn)定的基數(shù)排序O(d(n+r))O(d(n+r))O(n+r)穩(wěn)定的表7-1主要內(nèi)部排序方法的性能

講稿中討論的排序方法是在順序存儲結(jié)構(gòu)上實現(xiàn)的，在排序過程中需要移動大量記錄。當記錄數(shù)很多、時間耗費很大時，可以采用靜態(tài)鏈表作為存儲結(jié)構(gòu)。但有些排序方法，若采用靜態(tài)鏈表作存儲結(jié)構(gòu)，則無法實現(xiàn)表排序。選取排序方法的主要考慮因素：◆

待排序的記錄數(shù)目n；◆

每個記錄的大??；◆

關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；◆

是否要求排序的穩(wěn)定性；◆

語言工具的特性；◆

存儲結(jié)構(gòu)的初始條件和要求；◆時間復(fù)雜度、空間復(fù)雜度和開發(fā)工作的復(fù)雜程度的平衡點等。習題十⑴回答下列各題：①從未排序序列中挑選元素，并將其依次放入到已排序序列中(初始時為空)的一端的方法是什么？②在待排序的元素基本有序的前提下，效率最高的排序方法是什么?③從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素進行比較，將其放入已排序序列的正確位置方法是什么？④設(shè)有1000個元素，希望采用最快的速度挑選出其中前10個最大的元素，最好的方法是什么?⑵若對關(guān)鍵字序列為(54,37,93,25,17,68,58,41,76)的一組記錄進行快速排序時，遞歸調(diào)用使用的棧所能到達的最大深度是多少?共需遞歸調(diào)用多少次?其中第二次遞歸調(diào)用是對哪組記錄進行排序?⑶在堆排序，快速排序和歸并排序中，若只從存儲空間考慮，應(yīng)選擇哪種方法；若只從排序結(jié)果的穩(wěn)定性考慮，應(yīng)選擇哪種方法；若只從平均情況下排序最快考慮，應(yīng)選擇哪種方法；⑷設(shè)有關(guān)鍵字序列為(14,17,53,35,9,32,