排序的基本概念⑴排序(Sorting)排序是將一批(組)任意次序的記錄重新排列成按關鍵字有序的記錄序列的過程，其定義為：給定一組記錄序列：{R1,R2,…,Rn}，其相應的關鍵字序列是{K1,K2,…,Kn}。確定1,2,…n的一個排列p1,p2,…,pn，使其相應的關鍵字滿足如下非遞減(或非遞增)關系：Kp1≤Kp2≤…≤Kpn的序列{Kp1,Kp2,

…,Kpn}，這種操作稱為排序。關鍵字Ki可以是記錄Ri的主關鍵字，也可以是次關鍵字或若干數據項的組合。第1頁，共88頁。

◆

Ki是主關鍵字：排序后得到的結果是唯一的；

◆

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

比較兩個關鍵字的大小；◆

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

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

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

插入排序

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

直接插入排序1排序思想將待排序的記錄Ri，插入到已排好序的記錄表R1,R2,….,Ri-1中，得到一個新的、記錄數增加1的有序表。直到所有的記錄都插入完為止。設待排序的記錄順序存放在數組R[1…n]中，在排序的某一時刻，將記錄序列分成兩部分：◆R[1…i-1]：已排好序的有序部分；◆R[i…n]：未排好序的無序部分。顯然，在剛開始排序時，R[1]是已經排好序的。第8頁，共88頁。例：設有關鍵字序列為：7,4,-2,19,13,6，直接插入排序的過程如下圖9-1所示：初始記錄的關鍵字：[7]4-219136第一趟排序：[47]-219136第二趟排序：[-247]19136第三趟排序：[-24719]136第四趟排序：[-2471319]6第五趟排序：[-24671319]圖9-1直接插入排序的過程第9頁，共88頁。2算法實現voidstraight_insert_sort(Sqlist*L){inti,j;for(i=2;i<=L->length;i++){L->R[0]=L->R[i];j=i-1;/*設置哨兵*/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];/*插入到相應位置*/}}第10頁，共88頁。3算法說明算法中的R[0]開始時并不存放任何待排序的記錄，引入的作用主要有兩個：①不需要增加輔助空間：保存當前待插入的記錄R[i]，R[i]會因為記錄的后移而被占用；②保證查找插入位置的內循環總可以在超出循環邊界之前找到一個等于當前記錄的記錄，起“哨兵監視”作用，避免在內循環中每次都要判斷j是否越界。第11頁，共88頁。4

算法分析⑴最好情況：若待排序記錄按關鍵字從小到大排列(正序)，算法中的內循環無須執行，則一趟排序時：關鍵字比較次數1次，記錄移動次數2次(R[i]→R[0],R[0]→R[j+1])。則整個排序的關鍵字比較次數和記錄移動次數分別是：比較次數：∑1=n-1ni=2移動次數：∑2=2(n-1)ni=2第12頁，共88頁。⑵最壞情況：若待排序記錄按關鍵字從大到小排列(逆序)，則一趟排序時：算法中的內循環體執行i-1，關鍵字比較次數i次，記錄移動次數i+1。則就整個排序而言：比較次數：∑i=ni=2(n-1)(n+1)2移動次數：∑(i+1)=ni=2(n-1)(n+4)2一般地，認為待排序的記錄可能出現的各種排列的概率相同，則取以上兩種情況的平均值，作為排序的關鍵字比較次數和記錄移動次數，約為n2/4，則復雜度為O(n2)。第13頁，共88頁。9.2.2其它插入排序1折半插入排序

當將待排序的記錄R[i]插入到已排好序的記錄子表R[1…i-1]中時，由于R1,R2,…,Ri-1已排好序，則查找插入位置可以用“折半查找”實現，則直接插入排序就變成為折半插入排序。⑴算法實現voidBinary_insert_sort(Sqlist*L){inti,j,low,high,mid;for(i=2;i<=L->length;i++){L->R[0]=L->R[i];/*設置哨兵*/第14頁，共88頁。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];/*插入到相應位置*/}}第15頁，共88頁。從時間上比較，折半插入排序僅僅減少了關鍵字的比較次數，卻沒有減少記錄的移動次數，故時間復雜度仍然為O(n2)。⑵

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

是對折半插入排序的改進，以減少排序過程中移動記錄的次數。附加n個記錄的輔助空間，方法是：①另設一個和L->R同類型的數組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]之后的有序表中；第18頁，共88頁。關鍵點：實現時將向量d看成是循環向量，并設兩個指針first和final分別指示排序過程中得到的有序序列中的第一個和最后一個記錄。排序示例設有初始關鍵字集合{49,38,65,13,97,27,76}，采用2-路插入排序的過程如右圖9-3所示。在2-路插入排序中，移動記錄的次數約為n2/8。但當L->R[1]是待排序記錄中關鍵字最大或最小的記錄時，2-路插入排序就完全失去了優越性。第19頁，共88頁。2776d49firstfirstfirstfirstfinalfinalfinalfinal653897971313圖9-32-路插入排序過程3表插入排序前面的插入排序不可避免地要移動記錄，若不移動記錄就需要改變數據結構。附加n個記錄的輔助空間，記錄類型修改為：第20頁，共88頁。typedefstructRecNode{KeyTypekey;infotypeotherinfo;int*next;}RecNode;初始化：下標值為0的分量作為表頭結點，關鍵字取為最大值，各分量的指針值為空；①將靜態鏈表中數組下標值為1的分量(結點)與表頭結點構成一個循環鏈表；②i=2，將分量R[i]按關鍵字遞減插入到循環鏈表；③增加i，重復②，直到全部分量插入到循環鏈表。第21頁，共88頁。例：設有關鍵字集合{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---第22頁，共88頁。和直接插入排序相比，不同的是修改2n次指針值以代替移動記錄，而關鍵字的比較次數相同，故時間復雜度為O(n2)。表插入排序得到一個有序鏈表，對其可以方便地進行順序查找，但不能實現隨機查找。根據需要，可以對記錄進行重排，記錄重排詳見P247。i=6MAXINT4938651397277649

43156

02--i=7MAXINT4938651397277649

43176

025-i=8MAXINT4938651397277649

48176

0253圖9-4表插入排序過程第23頁，共88頁。9.2.3希爾排序

希爾排序(ShellSort，又稱縮小增量法)是一種分組插入排序方法。1排序思想①先取一個正整數d1(d1<n)作為第一個增量，將全部n個記錄分成d1組，把所有相隔d1的記錄放在一組中，即對于每個k(k=1,2,…d1)，R[k],R[d1+k],R[2d1+k],…分在同一組中，在各組內進行直接插入排序。這樣一次分組和排序過程稱為一趟希爾排序；②取新的增量d2<d1，重復①的分組和排序操作；直至所取的增量di=1為止，即所有記錄放進一個組中排序為止。第24頁，共88頁。2排序示例設有10個待排序的記錄，關鍵字分別為9,13,8,2,5,13,7,1,15,11，增量序列是5,3,1，希爾排序的過程如圖9-5所示。97125131381511第一趟排序后:25197131181513第二趟排序后:12578911131315第三趟排序后:圖9-5希爾排序過程9138251371151171318初始關鍵字序列:第一趟排序過程:第25頁，共88頁。3

算法實現先給出一趟希爾排序的算法，類似直接插入排序。voidshell_pass(Sqlist*L,intd)/*對順序表L進行一趟希爾排序,增量為d*/{intj,k;for(j=d+1;j<=L->length;j++){L->R[0]=L->R[j];/*設置監視哨兵*/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];}}第26頁，共88頁。然后在根據增量數組dk進行希爾排序。voidshell_sort(Sqlist*L,intdk[],intt)/*按增量序列dk[0…t-1],對順序表L進行希爾排序*/{intm;for(m=0;m<=t;m++)shll_pass(L,dk[m]);}希爾排序的分析比較復雜，涉及一些數學上的問題，其時間是所取的“增量”序列的函數。希爾排序特點子序列的構成不是簡單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列。第27頁，共88頁。希爾排序可提高排序速度，原因是：◆分組后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了；◆

關鍵字較小的記錄跳躍式前移，在進行最后一趟增量為1的插入排序時，序列已基本有序。增量序列取法◆無除1以外的公因子；◆最后一個增量值必須為1。第28頁，共88頁。

交換排序

是一類基于交換的排序，系統地交換反序的記錄的偶對，直到不再有這樣的偶對為止。其中最基本的是冒泡排序(BubbleSort)。第29頁，共88頁。9.3.1冒泡排序1排序思想

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

設有9個待排序的記錄，關鍵字分別為23,38,22,45,23,67,31,15,41，冒泡排序的過程如圖9-6所示。3算法實現#defineFALSE0#defineTRUE1第31頁，共88頁。圖9-6冒泡排序過程233822452367311541初始關鍵字序列:第一趟排序后: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

67第32頁，共88頁。voidBubble_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;}}第33頁，共88頁。故時間復雜度：T(n)=O(n2)空間復雜度：S(n)=O(1)4算法分析時間復雜度◆

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

最壞情況(逆序)：比較次數：∑(n-i)=n-1i=1n(n-1)2移動次數：3∑(n-i)=n-1i=13n(n-1)2第34頁，共88頁。9.3.2快速排序1排序思想通過一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，再分別對這兩部分記錄進行下一趟排序，以達到整個序列有序。2排序過程設待排序的記錄序列是R[s…t]，在記錄序列中任取一個記錄(一般取R[s])作為參照(又稱為基準或樞軸)，以R[s].key為基準重新排列其余的所有記錄，方法是：第35頁，共88頁。◆

所有關鍵字比基準小的放R[s]之前；◆

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

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

設兩個變量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，然后繼續進行比較，直到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，然后繼續進行比較，直到i=j或R[0].key<R[i].key為止；第37頁，共88頁。◆

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

設有6個待排序的記錄，關鍵字分別為29,38,22,45,23,67，一趟快速排序的過程如圖9-7所示。第38頁，共88頁。圖9-7一趟快速排序過程j前移2個位置后,R[j]放R[i]的位置:29

23382245

6731ij初始關鍵字序列:2929382245236731ij029

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

23

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

23

22

2945386731iji后前移1個位置后,i和j的位置重合:第39頁，共88頁。5算法實現⑴

一趟快速排序算法的實現intquick_one_pass(Sqlist*L,intlow,inthigh){inti=low,j=high;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);}第40頁，共88頁。⑵

快速排序算法實現

當進行一趟快速排序后，采用同樣方法分別對兩個子序列快速排序，直到子序列記錄個為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);}/*序列分為兩部分后分別對每個子序列排序*/}第41頁，共88頁。②

非遞歸算法#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--];}第42頁，共88頁。}while(top!=0&&low<high);}6算法分析

快速排序的主要時間是花費在劃分上，對長度為k的記錄序列進行劃分時關鍵字的比較次數是k-1。設長度為n的記錄序列進行排序的比較次數為C(n)，則C(n)=n-1+C(k)+C(n-k-1)。◆

最好情況：每次劃分得到的子序列大致相等，則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時排序結束。第43頁，共88頁。即C(n)≤n×㏒2n+n×C(1)，C(1)看成常數因子，即C(n)≤O(n×㏒2n)

；◆

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

一般情況：對n個記錄進行快速排序所需的時間T(n)組成是：①對n個記錄進行一趟劃分所需的時間是：n×C，C是常數；②對所得到的兩個子序列進行快速排序的時間：Tavg(n)=C(n)+Tavg(k-1)+Tavg(n-k)……⑴第44頁，共88頁。若記錄是隨機排列的，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第45頁，共88頁。=(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個記錄的排序時間是一個常數，∴快速排序的平均時間復雜度是：T(n)=O(n㏒2n)

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

。∴快速排序的空間復雜度是：S(n)=O(㏒2n)從排序的穩定性來看，快速排序是不穩定的。第46頁，共88頁。9.4

選擇排序

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

第47頁，共88頁。

簡單選擇排序

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

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

19第49頁，共88頁。算法實現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];}}}第50頁，共88頁。3算法分析整個算法是二重循環：外循環控制排序的趟數，對n個記錄進行排序的趟數為n-1趟；內循環控制每一趟的排序。進行第i趟排序時，關鍵字的比較次數為n-i，則：比較次數：∑(n-i)=n-1i=1n(n-1)2

∴時間復雜度是：T(n)=O(n2)空間復雜度是：S(n)=O(1)從排序的穩定性來看，直接選擇排序是不穩定的。第51頁，共88頁。9.4.2樹形選擇排序

借助“淘汰賽”中的對壘就很容易理解樹形選擇排序的思想。首先對n個記錄的關鍵字兩兩進行比較，選取n/2個較小者；然后這n/2個較小者兩兩進行比較，選取n/4個較小者…如此重復，直到只剩1個關鍵字為止。該過程可用一棵有n個葉子結點的完全二叉樹表示，如圖9-9所示。每個枝結點的關鍵字都等于其左、右孩子結點中較小的關鍵字，根結點的關鍵字就是最小的關鍵字。第52頁，共88頁。輸出最小關鍵字后，根據關系的可傳遞性，欲選取次小關鍵字，只需將葉子結點中的最小關鍵字改為“最大值”，然后重復上述步驟即可。含有n個葉子結點的完全二叉樹的深度為㏒2n+1，則總的時間復雜度為O(n㏒2n)

。492525372828196519153415251515圖9-９“淘汰賽”過程示意圖第53頁，共88頁。9.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為根的完全二叉樹。若對該二叉樹的結點進行編號(從上到下，從左到右)，得到的序列就是將二叉樹的結點以順序結構存放，堆的結構正好和該序列結構完全一致。第54頁，共88頁。2堆的性質①堆是一棵采用順序存儲結構的完全二叉樹，k1是根結點；②堆的根結點是關鍵字序列中的最小(或最大)值，分別稱為小(或大)根堆；③從根結點到每一葉子結點路徑上的元素組成的序列都是按元素值(或關鍵字值)非遞減(或非遞增)的；堆中的任一子樹也是堆。利用堆頂記錄的關鍵字值最小(或最大)的性質，從當前待排序的記錄中依次選取關鍵字最小(或最大)的記錄，就可以實現對數據記錄的排序，這種排序方法稱為堆排序。第55頁，共88頁。重復上述操作，直到是葉子結點或其關鍵字值小于等于左、右子樹的關鍵字的值，將得到新的堆。{if(f[k]!=NULL)/*第k個隊列不空則收集*/{R[k],R[k+1],…,R[m]}和{R[m+1],R[m+2],…,R[h]}，將它們歸并為一個有序的子序列：然后比較L->R[2]與L->R[3]的關鍵字，依此類推，直到L->R[n-1]與L->R[n]的關鍵字比較后為止，稱為一趟冒泡排序，L->R[n]為關鍵字最大的記錄。232238234531154167for(m=1;m<L->length;m++)/*桶的頭尾指針數組*/設長度為n的記錄序列進行排序的比較次數為C(n)，則C(n)=n-1+C(k)+C(n-k-1)。◆一般情況：對n個記錄進行快速排序所需的時間T(n)組成是：k++;/*選擇左、右孩子中關鍵字的最小者*/97125131381511◆存儲結構的初始條件和要求；3堆排序思想①對一組待排序的記錄，按堆的定義建立堆；②將堆頂記錄和最后一個記錄交換位置，則前n-1個記錄是無序的，而最后一個記錄是有序的；③堆頂記錄被交換后，前n-1個記錄不再是堆，需將前n-1個待排序記錄重新組織成為一個堆，然后將堆頂記錄和倒數第二個記錄交換位置，即將整個序列中次小關鍵字值的記錄調整(排除)出無序區；④重復上述步驟，直到全部記錄排好序為止。

結論：排序過程中，若采用小根堆，排序后得到的是非遞減序列；若采用大根堆，排序后得到的是非遞增序列。第56頁，共88頁。堆排序的關鍵①如何由一個無序序列建成一個堆？②

如何在輸出堆頂元素之后，調整剩余元素，使之成為一個新的堆？

4堆的調整——篩選⑴堆的調整思想

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

堆調整算法實現voidHeap_adjust(Sqlist*H,ints,intm)/*H->R[s…m]中記錄關鍵字除H->R[s].key均滿足堆定義*//*調整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++;/*選擇左、右孩子中關鍵字的最小者*/if(LT(H->R[k].key,H->R[0].key)){H->R[j]=H->R[k];j=k;k=2*j}elsebreak;}第59頁，共88頁。H->R[j]=H->R[0];}5堆的建立

利用篩選算法，可以將任意無序的記錄序列建成一個堆，設R[1],R[2],…,R[n]是待排序的記錄序列。將二叉樹的每棵子樹都篩選成為堆。只有根結點的樹是堆。第?n/2?個結點之后的所有結點都沒有子樹，即以第n/2個結點之后的結點為根的子樹都是堆。因此，以這些結點為左、右孩子的結點，其左、右子樹都是堆，則進行一次篩選就可以成為堆。同理，只要將這些結點的直接父結點進行一次篩選就可以成為堆…。

只需從第n/2個記錄到第1個記錄依次進行篩選就可以建立堆。第60頁，共88頁。可用下列語句實現：for(j=n/2;j>=1;j--)Heap_adjust(R,j,n);6堆排序算法實現

堆的根結點是關鍵字最小的記錄，輸出根結點后，是以序列的最后一個記錄作為根結點，而原來堆的左、右子樹都是堆，則進行一次篩選就可以成為堆。voidHeap_Sort(Sqlist*H){intj;for(j=H->length/2;j>0;j--)Heap_adjust(H,j,H->length);/*初始建堆*/第61頁，共88頁。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算法分析

主要過程：初始建堆和重新調整成堆。設記錄數為n，所對應的完全二叉樹深度為h。◆

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

篩選調整：每次篩選要將根結點“下沉”到一個合適位置。第i次篩選時：堆中元素個數為n-i+1；堆的深度是㏒2(n-i+1)+1，則進行n-1次“篩選”的比較次數C2(n)為：C2(n)≤∑(2×㏒2(n-i+1))n-1i=1∴C2(n)<2n㏒2n∴

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

歸并排序

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

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

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

重復上述過程，直到某一堆已抽完，然后將剩下一堆中的所有牌轉移到新堆中。第64頁，共88頁。1排序思想

①初始時，將每個記錄看成一個單獨的有序序列，則n個待排序記錄就是n個長度為1的有序子序列；②對所有有序子序列進行兩兩歸并，得到n/2個長度為2或1的有序子序列——一趟歸并；③重復②，直到得到長度為n的有序序列為止。上述排序過程中，子序列總是兩兩歸并，稱為2-路歸并排序。其核心是如何將相鄰的兩個子序列歸并成一個子序列。設相鄰的兩個子序列分別為：{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]}第65頁，共88頁。例：設有9個待排序的記錄，關鍵字分別為23,38,22,45,23,67,31,15,41，歸并排序的過程如圖9-11所示。圖9-11歸并排序過程[23][38][22][45][23][67][31][15][41]初始關鍵字:[2338][2245][2367][1531][41]一趟歸并后:[22233845][15233167][41]二趟歸并后:[152223233138

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

414567四趟歸并后:第66頁，共88頁。歸并的算法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)/*將剩余子序列復制到結果序列中*/DR[n++]=R[p++];while(q<=h)DR[n++]=R[q++];}第67頁，共88頁。2一趟歸并排序一趟歸并排序都是從前到后，依次將相鄰的兩個有序子序列歸并為一個，且除最后一個子序列外，其余每個子序列的長度都相同。設這些子序列的長度為d，則一趟歸并排序的過程是：從j=1開始，依次將相鄰的兩個有序子序列R[j…j+d-1]和R[j+d…j+2d-1]進行歸并；每次歸并兩個子序列后，j后移動2d個位置，即j=j+2d；若剩下的元素不足兩個子序列時，分以下兩種情況處理：①剩下的元素個數>d：再調用一次上述過程，將一個長度為d的子序列和不足d的子序列進行歸并；②剩下的元素個數≤d：將剩下的元素依次復制到歸并后的序列中。第68頁，共88頁。⑴一趟歸并排序算法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)/*剩余元素個數超過一個子序列長度d*/Merge(R,DR,j,j+d-1,n);elseMerge(R,DR,j,n,n);/*剩余子序列復制*/}第69頁，共88頁。⑵

歸并排序的算法

開始歸并時，每個記錄是長度為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;}}第70頁，共88頁。3算法分析

具有n個待排序記錄的歸并次數是㏒2n，而一趟歸并的時間復雜度為O(n)，則整個歸并排序的時間復雜度無論是最好還是最壞情況均為O(n㏒2n)。在排序過程中，使用了輔助向量DR，大小與待排序記錄空間相同，則空間復雜度為O(n)。歸并排序是穩定的。第71頁，共88頁。利用堆頂記錄的關鍵字值最小(或最大)的性質，從當前待排序的記錄中依次選取關鍵字最小(或最大)的記錄，就可以實現對數據記錄的排序，這種排序方法稱為堆排序。一趟歸并排序都是從前到后，依次將相鄰的兩個有序子序列歸并為一個，且除最后一個子序列外，其余每個子序列的長度都相同。q->next=NULL;/*修改收集鏈尾指針*/{intj,k,m;為實現基數排序，用兩個指針數組來分別管理所有的緩存(桶)，同時對待排序記錄的數據類型進行改造，相應的數據類型定義如下：for(k=2*j;k<=m;k=2*k)圖9-10堆的篩選過程{if(f[k]!=NULL)/*第k個隊列不空則收集*/infoTypeotherinfo;/*其他域*/{if(LQ(R[p].而②、③則適合記錄數較多的情況。每次是按記錄關鍵字某一“位”的值將所有記錄分配到相應的桶中，再按桶的編號依次將記錄進行收集，最后得到一個有序序列。第五趟排序：-24671319前面的插入排序不可避免地要移動記錄，若不移動記錄就需要改變數據結構。初始記錄的關鍵字：74-219136#defineMAX_SIZE1009.6

基數排序

基數排序(RadixSorting)

又稱為桶排序或數字排序：按待排序記錄的關鍵字的組成成分(或“位”)進行排序。基數排序和前面的各種內部排序方法完全不同，不需要進行關鍵字的比較和記錄的移動。借助于多關鍵字排序思想實現單邏輯關鍵字的排序。第72頁，共88頁。9.6.1多關鍵字排序

設有n個記錄{R1,R2,…,Rn}，每個記錄Ri的關鍵字是由若干項(數據項)組成，即記錄Ri的關鍵字Key是若干項的集合：{Ki1,Ki2,…,Kid}(d>1)。記錄{R1,R2,…,Rn}有序的，指的是i,j∈[1,n]，i<j，若記錄的關鍵字滿足：{Ki1,Ki2,…Kid}<{Kj1,Kj2,…Kjd}，即Kip≤Kjp(p=1,2,…d)第73頁，共88頁。多關鍵字排序思想先按第一個關鍵字K1進行排序，將記錄序列分成若干個子序列，每個子序列有相同的K1值；然后分別對每個子序列按第二個關鍵字K2進行排序，每個子序列又被分成若干個更小的子序列；如此重復，直到按最后一個關鍵字Kd進行排序。最后，將所有的子序列依次聯接成一個有序的記錄序列，該方法稱為最高位優先(MostSignificantDigitfirst)。另一種方法正好相反，排序的順序是從最低位開始，稱為最低位優先(LeastSignificantDigitfirst)。第74頁，共88頁。9.6.2鏈式基數排序若記錄的關鍵字由若干確定的部分(又稱為“位”)組成，每一位(部分)都有確定數目的取值。對這樣的記錄序列排序的有效方法是基數排序。設有n個待排序記錄{R1,R2,…,Rn}，(單)關鍵字是由d位(部分)組成，每位有r種取值，則關鍵字R[i].key可以看成一個d元組：R[i].key={Ki1,Ki2,…,Kid}。基數排序可以采用前面介紹的MSD或LSD方法。以下以LSD方法討論鏈式基數排序。第75頁，共88頁。1排序思想⑴首先以靜態鏈表存儲n個待排序記錄，頭結點指針指向第一個記錄結點；⑵一趟排序的過程是：①分配：按Kd值的升序順序，改變記錄指針，將鏈表中的記錄結點分配到r個鏈表(桶)中，每個鏈表中所有記錄的關鍵字的最低位(Kd)的值都相等，用f[i]、e[i]作為第i個鏈表的頭結點和尾結點；②

收集：改變所有非空鏈表的尾結點指針，使其指向下一個非空連表的第一個結點，從而將r個鏈表中的記錄重新鏈接成一個鏈表；⑶如此依次按Kd-1,Kd-2,…K1分別進行，共進行d趟排序后排序完成。第76頁，共88頁。2排序示例設有關鍵字序列為1039,2121,3355,4382,66,118的一組記錄，采用鏈式基數排序的過程如下圖9-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第一趟收集結果：第77頁，共88頁。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第二趟收集結果：103900660118212133554382∧head第三趟收集結果：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]分配：3355438210390066第78頁，共88頁。006601181039