第十章內部排序

第十章內部排序

10.1概述10.2插入排序10.3快速排序10.4選擇排序

學習要點理解排序的定義和各種排序方法的特點；了解各種方法的排序過程及其依據的原則；理解“穩定”或“不穩定”的含義；10.1概述

排序（Sorting）是數據處理中一種很重要的運算，同時也是很常用的運算，一般數據處理工作25%的時間都在進行排序。簡單地說，排序就是把一組記錄（元素）按照某個域的值的遞增（即由小到大）或遞減（即由大到小）的次序重新排列的過程。1.基本概念1)．排序碼（SortKey）

作為排序依據的記錄中的一個屬性。它可以是任何一種可比的有序數據類型，它可以是記錄的關鍵字，也可以是任何非關鍵字。2)．有序表與無序表一組記錄按排序碼的遞增或遞減次序排列得到的結果被稱之為有序表，相應地，把排序前的狀態稱為無序表。3)．正序表與逆序表若有序表是按排序碼升序排列的，則稱為升序表或正序表，否則稱為降序表或逆序表。不失普遍性，我們一般只討論正序表。4).排序定義若給定一組記錄的文件{r1，r2，…，rn},其相應的排序碼分別為{k1，k2，…，kn},需確定一種排列p1，

p2，

…

pn

，以使排序碼的序列滿足:kp1≤

kp2≤…≤kpn即使上述文件成為按排序碼線性有序{rp1，rp2，…，rpn

}，這一過程稱為排序。也可以說，將一組記錄按某排序碼遞增或遞減排列的過程，稱為排序。

5)．穩定與不穩定因為排序碼可以不是記錄的關鍵字，同一排序碼值可能對應多個記錄。對于具有同一排序碼的多個記錄來說，若采用的排序方法使排序后記錄的相對次序不變，則稱此排序方法是穩定的，否則稱為不穩定的。6)．內排序與外排序按照排序過程中使用內外存的不同將排序方法分為內排序和外排序。若排序過程全部在內存中進行，則稱為內排序；若排序過程需要不斷地進行內存和外存之間的數據交換，則稱為外排序。內排序大致可分為五類：插入排序、交換排序、選擇排序、歸并排序和分配排序。本章僅討論內排序。7)．排序的時間復雜性排序過程主要是對記錄的排序碼進行比較和記錄的移動過程。因此排序的時間復雜性可以算法執行中的數據比較次數及數據移動次數來衡量。當一種排序方法使排序過程在最壞或平均情況下所進行的比較和移動次數越少，則認為該方法的時間復雜性就越好，分析一種排序方法，不僅要分析它的時間復雜性，而且要分析它的空間復雜性、穩定性和簡單性等。

2.存貯方式

待排序的記錄序列通常有下列三種存貯方法：

1）順序表

2）靜態鏈表：在排序過程，只需修改指針，不需要移動記錄；

3）待排記錄本身存放在連續單元中，同時另建一索引表——用于存放各記錄存貯位置；排序時不移動記錄本身，而移動索引表中的記錄“地址”，在排序結束后再按地址調整記錄的存貯位置3約定在本章中1)為簡潔起見，對待排記錄只寫出其排序碼序列如對待排記錄（(09,10),(06,10.5),(033,9.8),(051,10))只寫出其關鍵字序列（10，10.5，9.8，10）2）將按關鍵字遞增的順序排序3)待排序記錄用順序表存儲順序表類型說明#defineMAXSIZE20//一個用作示例的小順序表的最大長度typedef

int

KeyType;//定義關鍵字類型為整數類型typedef

struct{

KeyTypekey;//關鍵字項

InfoType

otherinfo;//其它數據項}RedType;//記錄類型typedef

struct{

RedTyper[MAXSIZE+1];//r[0]閑置或用作哨兵單元

intlength;//順序表長度}SqList;//順序表類型插入排序（直插排序、二分排序、表插入排序、希爾排序）交換排序（冒泡排序、快速排序）選擇排序（直選排序、樹型排序、堆排序）排序10.2插入排序10.2.1直接插入排序1．基本思想直接插入排序（StraightInsertionSorting）的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。

例：待排記錄4938659776132749

（49）38659776132749

（3849）659776132749（384965）9776132749

（38496597）76132749（3849657697）132749（133849657697）27

49（13273849657697）49（1327384949657697）一趟直接插入排序voidInsertSort(SqList&L){//對順序表L作直接插入排序。for(i=2;i<=L.length;++i){

ifLT(L.r[i].key,L.r[i-1].key){//若L.r[i].key<L.r[i-1].key，需將L.r[i]插入有序子表，L.r[0]=L.r[i];//L.r[i]復制為哨兵for(j=i-1;LT(L.r(0).key,L.r[j].key);--j)//從后向前查找子表L.r[j+1]=L.r[j];//若L.r[i].key<L.r[j].key，L.r[j]記錄后移L.r[j+1]=L.r[0];//插入到正確位置}}//InsertSort

49386576971327490123456789初始時，有序子表中只有一個元素2．直接插入的算法實現

38496597761327490123456789L.r[0].key<L.r[4].key，L.r[4]記錄后移看一下外層For循環i=5時算法的執行的情況L.r[5]復制為哨兵

7638496597761327490123456789

7638496597

97

1327490123456789

7638496597

97

1327490123456789L.r[0].key

L.r[3].key找到插入位置

7638496597

97

1327490123456789L.r[5]為待插入元素插入！763．直接插入排序的效率分析從算法可以看出，直接插入排序算法十分簡單。那么它的效率如何呢？首先從空間來看，它只需要一個元素的輔助空間，用于元素的位置交換。從時間分析：基本正序，只比較，不移動元素，待插入元素傳送2次。總比較次數為(n-1),傳送次數為2(n-1)。O(T)=O(n)

基本逆序，對每個元素i,比較i次，總次數

i=2i=(n+2)(n+1)/2,移動i-1＋2次,

i=2(i+1)=(n+4)(n-1)/2。

O(T)=O(n2)綜合兩種情況，平均n2/4

特點：1)算法簡單

2)時間復雜度為O（n2）3）初始序列基本（正向）有序時，時間復雜度為O（n）4）穩定排序

該方法適用于記錄基本（正向）有序或n較少的情況

10.2.2其他插入排序1．二分插入排序1）基本思想二分插入排序（BinaryInsertSort）的基本思想是：在有序表中采用二分查找的方法查找待排元素的插入位置。其處理過程：先將第一個元素作為有序序列，進行n-1次插入，用二分查找的方法查找待排元素的插入位置，將待排元素插入。2）．算法實現見P267算法10.23)．效率分析二分插入算法與直接插入算法相比，需要輔助空間與直接插入排序基本一致；時間上，前者的比較次數比直接插入查找的最壞情況好，最好的情況下，兩種方法的元素的移動次數相同，因此二分插入排序的時間復雜度仍為O(n2）。二分插入算法與直接插入算法的元素移動一樣是順序的，因此該方法也是穩定的。2．表插入排序

1）基本思想

記錄放在靜態鏈表中，進行插入排序，可以不移動元素。#defineSIZE100Typedef

struct{

RcdType

rc;

intnext;}SLNode;Typedef

struct{

SLNoder[SIZE];

intlength;}SLinkListType;

以上述說明的靜態鏈表作為存儲結構，為了插入方便，設數組中下標為0的分量為表頭結點，并令表頭結點記錄的關鍵字取最大整數MAXINT。則表插入排序如下：首先將靜態鏈表中數組下標為1的分量與表頭結點構成一個循環鏈表，然后依次將下標為2到n的記錄插入到循環鏈表中。M4938659776132749’10M4938659776132749’201

0123456782）算法實現

見P270算法10.3是將排好序的靜態鏈表按指針順序進行記錄調整

3）性能分析

從算法可見，表插入排序的基本操作仍是將一個記錄插入到已排好序的有序表中，不同之處僅在于以修改2n次指針代替移動記錄，關鍵字比較次數相同，時間復雜度仍是O(n2)10.2.3希爾排序

1．希爾排序的基本思想

希爾排序（ShellSort）又稱為“縮小增量排序”。是1959年由D.L.Shell提出來的。該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。DonaldL.Shell博士(1924-)在計算機科學領域的貢獻是ShellSort

。1984年退休。1951年獲取碩士學位，1959年博士學位。24

希爾在1959年針對插入排序作了改進，提出了一個縮小增量排序方法。方法：先取一個正整數d1<n，把所有相隔d1的數據作為一組，組內進行直接插入排序；然后取d2<d1，重復上述分組和排序操作；直至di=1。取d3=1三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分組：49

38

65

97

76

13

27

48

55

4取d2=3二趟分組：13

27

48

55

4

49

38

65

97

763．希爾排序的性能分析希爾排序的性能分析是一個復雜的問題，是所取增量的函數。希爾排序的時間復雜性在O（nlog2n）和O（n2）之間，大致為O（n1.3）。2．希爾排序的算法實現見P272算法10.4,10.5特點

1）時間復雜度，取決于增量序列的選擇，選擇的好，效率優于直接插入排序，其時間復雜度為0（nlog2n）

2）不穩定排序方法

3）適用于n較大情況

10.3快速(交換)排序

將待排記錄中兩兩記錄關鍵字進行比較，若逆序則交換位置。例：4938659776132749若按關鍵字遞增的順序排序,則4938為逆序

不同的比較順序就得到不同的交換排序方法10.3.1起泡排序

1.起泡排序（BubbleSorting）的基本思想是：是通過對待排序序列從后向前（從下標較大的元素開始），依次比較相鄰元素的排序碼，若發現逆序則交換，使排序碼較小的元素逐漸從后部移向前部（從下標較大的單元移向下標較小的單元），就象水底下的氣泡一樣逐漸向上冒。因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，因此要在排序過程中設置一個標志flag判斷元素是否進行過交換。從而減少不必要的比較。2.冒泡排序的算法實現下面給出冒泡排序算法。voidBubblesort(int

a[],intn){

change=true;

for(i=n-1;change=true;i>1&&change;--i){

change=false;

for(j=0;j<i;++j)

if(a[j]>a[j+1]) {//發生逆序

{a[j]<-->a[j+1];

change=true;}//交換，并標記發生了交換}//for}//P273圖10.63．冒泡排序的效率分析從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進行一趟排序，比較次數為（n-1）次，移動元素次數為0；若待排序的元素為逆序，則需進行n-1趟排序，比較次數為(n2-n)/2，移動次數為3(n2-n)/2，因此冒泡排序算法的時間復雜度為O（n2）。由于其中的元素移動較多，所以屬于內排序中速度較慢的一種。因為冒泡排序算法只進行元素間的順序移動，所以是一個穩定的算法。10.3.2快速排序1962年Hoare（1934-）提出，是一位英國的計算機科學學家,Quicksort和CASE語句被廣泛應用。

1960年開始他的計算生涯,作為ElliottBrothers,一個小的科學計算機制造商的一名程序員。1968年成為Queen‘s

University一名計算機科學的教授,并在1977年轉到OxfordUniversity。Hoare教授1999從牛津退休后,繼續在英國劍橋的微軟研究院從事計算機研究.“因為在程序設計語言的定義和設計方面做出的基礎性貢獻”。獲得了1980年的圖靈獎。1．快速排序的基本思想快速排序（QuickSorting）是迄今為止所有內排序算法中速度最快的一種。它的基本思想是：任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個子序列繼續進行排序，直至整個序列有序。快速排序是對冒泡排序的一種改進方法，算法中元素的比較和交換是從兩端向中間進行的，排序碼較大的元素一次就能夠交換到后面單元，排序碼較小的記錄一次就能夠交換到前面單元，記錄每次移動的距離較遠，因而總的比較和移動次數較少。快速排序的過程為：把待排序區間按照第一個元素（即基準元素）的排序碼分為左右兩個子序列的過程叫做一次劃分。設待排序序列為R[left]～R[right]，其中left為下限，right為上限，left＜right，R[left]為該序列的基準元素，為了實現一次劃分，令i,j的初值分別為left和right。在劃分過程中，首先讓j從它的初值開始，依次向前取值，并將每一元素R[j]的排序碼同R[left]的排序碼進行比較，直到R[j]<R[left]時，交換R[j]與R[left]的值，使排序碼相對較小的元素交換到左子序列，然后讓i從i＋1開始，依次向后取值，并使每一元素R[i]的排序碼同R[j]的排序碼（此時R[j]為基準元素）進行比較，直到R[i]＞R[j]時，交換R[i]與R[j]的值，使排序碼大的元素交換到后面子區間；再接著讓j從j-1開始，依次向前取值，重復上述過程，直到i等于j,即指向同一位置為止，此位置就是基準元素最終被存放的位置。此次劃分得到的前后兩個待排序的子序列分別為R[left]～R[i-1]和R[i+1]～R[right]。例如，給定排序碼為：（46，55，13，42，94，05，17，70），具體劃分如圖所示。從圖可知，通過一次劃分，將一個區間以基準值分成兩個子區間，左子區間的值小于等于基準值，右子區間的值大于基準值。對剩下的子區間重復此劃分步驟，則可以得到快速排序的結果。2．快速排序的算法實現下面給出快速排序算法的遞歸算法如下：見講義P274算法10.6(a)和10.6(b)3．快速排序的效率分析

若快速排序出現最好的情形（左、右子區間的長度大致相等），則結點數n與二叉樹深度h應滿足log2n<h<log2n+1，所以總的比較次數不會超過(n+1)log2n。因此，快速排序的最好時間復雜度應為O（nlog2n）。而且在理論上已經證明，快速排序的平均時間復雜度也為O（nlog2n）。

若快速排序出現最壞的情形（每次能劃分成兩個子區間，但其中一個是空），則這時得到的二叉樹是一棵單分枝樹，得到的非空子區間包含有n-i個(i代表二叉樹的層數（1≤i≤n）元素，每層劃分需要比較n-i+2次，所以總的比較次數為（n2+3n-4）/2。因此，快速排序的最壞時間復雜度為O(n2)。快速排序所占用的輔助空間為棧的深度，故最好的空間復雜度為O（log2n），最壞的空間復雜度為O(n)。10.4選擇排序

基本思想:在待排記錄中依次選擇關鍵字最小的記錄，逐漸縮小范圍直至全部記錄選擇完畢。10.4.1簡單選擇排序1．直接選擇排序的基本思想直接選擇排序（straightselectsorting）也是一種簡單的排序方法。它的基本思想是：第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R[1]~R[n-1]中選取最小值，與R[1]交換，第三次從R[2]~R[n-1]中選取最小值，與R[2]交換，…，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，…,第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列。例如，給定n=8，數組R中的8個元素的排序碼為：（8，3，2，1，7，4，6，5），則直接選擇排序過程如圖所示。2．直接選擇排序的算法實現void

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

for(i=1;i<L.length;++i){

j=SelectMinKey(L,i);//在L.r[i..L.length]中選擇key最小的記錄

if(i!=j)L.r[i]←→L.r[j];//與第個i記錄交換}//for}//SelectSort

3．直接選擇排序的效率分析在直接選擇排序中，共需要進行n-1次選擇和交換，每次選擇需要進行n-i次比較（1≤i≤n-1），而每次交換最多需3次移動，因此，總的比較次數C==(n2-n)/2，總的移動次數M==3(n-1)。由此可知，直接選擇排序的時間復雜度為O(n2)數量級，所以當記錄占用的字節數較多時，通常比直接插入排序的執行速度要快一些。由于在直接選擇排序中存在著不相鄰元素之間的互換，因此，直接選擇排序是一種不穩定的排序方法。例如，給定排序碼為3，7，3，2，1，排序后的結果為1，2，3，3，7。

從直接選擇排序可知，在n個排序碼中，找出最小值需n-1次比較，找出第二小值需n-2次比較，找出第三小值需n-3次比較，其余依此類推。所以，總的比較次數為：(n-1)+(n-2)+…+3+2+1=(n2-n)/2，那么，能否對直接選擇排序算法加以改進，使總的比較次數比(n2-n)/2小呢？顯然，在n個排序碼中選出最小值，至少進行n-1次比較，但是，繼續在剩下的n-1個關鍵字中選第二小的值，就并非一定要進行n-2次比較，若能利用前面n-1次比較所得信息，則可以減少以后各趟選擇排序中所用的比較次數，比如8個運動員中決出前三名，不需要7+6+5=18場比賽（前提是，若甲勝乙，而乙勝丙，則認為甲勝丙），最多需要11場比賽即可（通過7場比賽產生冠軍后，第二名只能在輸給冠軍的三個對中產生，需2場比賽，而第三名只能在輸給亞軍的三個對中產生，也需2場比賽，總共11場比賽）。具體如圖所示。10.4.2樹形選擇排序從圖（a）可知，8個隊經過4場比賽，獲勝的4個隊進入半決賽，再經過2場半決賽和1場決賽即可知道冠軍屬誰（共7場比賽）按照錦標賽的傳遞關系，亞軍只能產生于分別在決賽，半決賽和第一輪比賽中輸給冠軍的選手中，于是亞軍只能在b、c、e這3個隊中產生（見圖（b）），即進行2場比賽（e與c一場，e與c的勝隊與b一場）后，即可知道亞軍屬誰。同理，第三名只需在c、f、g這3個隊產生（見圖（c））即進2場比賽（f與g一場，f與g的勝隊與c一場）即可知道第三名屬誰。樹形選擇排序（treeselectionsorting），又稱錦標賽排序（tournamentsorting），是一種按照錦標賽的思想進行選擇排序的方法。首先對n個記錄的排序碼進行兩兩比較，然后在其中

n/2

個較小者之間再進行兩兩比較，如此重復，直到選出最小排序碼為止。樹形選擇排序過程見圖。10.4.3堆排序1．堆的定義若有n個元素的排序碼k1，k2，k3，…，kn，當滿足如下條件：

ki≤k2iki≥k2i（1）ki≤k2i+1

或(2)ki≥k2i+1

其中i=1,2,…,

n/2

則稱此n個元素的排序碼k1，k2，k3，…，kn為一個堆。若將此排序碼按順序組成一棵完全二叉樹，則（1）稱為小根堆（二叉樹的所有根結點值小于或等于左右孩子的值），（2）稱為大根堆（二叉樹的所有根結點值大于或等于左右孩子的值）。若n個元素的排序碼k1，k2，k3，…，kn滿足堆，且讓結點按1、2、3、…、n順序編號，根據完全二叉樹的性質（若i為根結點，則左孩子為2i，右孩子為2i+1）可知，堆排序實際與一棵完全二叉樹有關。若將排序碼初始序列組成一棵完全二叉樹，則堆排序可以包含建立初始堆（使排序碼變成能符合堆的定義的完全二叉樹）和利用堆進行排序兩個階段。

2．堆排序的基本思想將排序碼k1，k2，k3，…，kn