數據結構：第10章 內部排序

第10章排序10.1概述

排序(Sorting)是計算機程序設計中的一種重要操作，它的功能是將一個數據元素(或記錄)的任意序列，重新排列成一個按關鍵字有序的序列。

為了便于討論，在此首先要對排序下一個確切的定義：假設含n個記錄的序列為{R1，R2，…，Rn}(10-1)

其相應的關鍵字序列為{K1，K2，…，Kn}(10-2)

需確定1，2，…，n的一種排列p1，p2，…，pn，使其相應的關鍵字滿足如下的非遞減(或非遞增)關系

Kp1≤Kp2≤…≤Kpn

即使式（10-1）的序列成為一個按關鍵字有序的序列{Rp1，Rp2，…，Rpn}

這樣一種操作稱為排序。如果在序列中有兩個元素r[i]和r[j],r[i]==r[j],且在排序之前,r[i]排在r[j]前面。如果在排序之后,r[i]仍在r[j]的前面,則稱這個排序方法是穩(wěn)定的,否則稱這個排序方法是不穩(wěn)定的。

由于待排序的記錄數量不同，使得排序過程中涉及的存儲器不同，可將排序方法分為兩大類：一類是內部排序，指的是待排序記錄存放在計算機隨機存儲器中進行的排序過程；另一類是外部排序，指的是待排序記錄的數量很大，以致內存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。

本章集中討論內部排序。

內部排序的過程是一個逐步擴大記錄的有序區(qū)序列程度的過程。如果按排序過程中依據的不同原則對內部排序方法進行分類，則可分為插入排序、交換排序、選擇排序、歸并排序和計數排序等五類。有序區(qū)R[1..i-1]無序區(qū)R[i..n]有序區(qū)R[1..i]無序區(qū)R[i+1..n]排序基本操作比較：比較元素的大小移動：將元素從一個位置移動至另一個位置排序的時間復雜度可用算法執(zhí)行中的數據元素比較次數與移動次數來衡量。10.2插入排序

一、直接插入排序直接插人排序(StraightInsertionSort)是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數增1的有序表。

有序區(qū)R[1..i-1]無序區(qū)R[i..n]R[i]有序區(qū)R[1..i]無序區(qū)R[i+1..n]直接插入算法步驟：第1步：取出K1不用插入，作為有序子序列；第2步：K2與K1比較，如果K2<K1，

K2插入到K1的前面，否則K2插入到K1的后面第j步：將Kj插入到K1、K2…Kj-1中（Kj從后向前順序比較，并依次后移）。第n步：將Kn插入到K1、K2…Kn-1中。直接插入排序舉例9已知待序的一組記錄的初始排列為：21,25,49,25*,16,0821254925*160812345610123456temp21254925*160825i=2123456temp21254925*160849i=31121254925*1608123456tempi=425*123456temp21254925*1608i=51612123456temp21254925*1608i=60821254925*1608123456完成直接插人排序算法描述：voidInsertSort(SqList&L){

//對順序表L作直接插入排序。

for(i=2；i<=L.length；++i)ifLT(L.r[i].key，L.r[i-1].key){//“<”，需將L.r[i]插入有序子表

L.r[0]=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[j+1]=L.r[0]//插入到正確位置}}//Insertsort

算法10.1[初始關鍵字]：(49)38659776132749’

i=2(38)(3849)659776132749’i=3(65)(384965)9776132749’i=4(97)(38496597)76132749’i=5(76)(3849657697)132749’i=6(13)(133849657697)2749’i=7(27)(13273849657697)49’

i=8(49)(1327384949’657697)

監(jiān)視哨L.r[0]

圖10.1直接插入排序示例直接插入排序算法分析直接插入排序的基本操作是比較和移動元素，比較的次數和數據元素移動次數與序列的初始排列有關。最好情況下,排序前元素已按從小到大排序,每一步只需與前面有序序列的最后一個元素比較1次,不需要移動元素,總的比較次數為n-1。最壞情況下,第i步插入時，序列的第i+1個元素必須與前面i個元素比較,并且每做1次比較就要做1次數據移動。則總比較次數KCN和移動次數RMN分別為在平均情況下的比較次數和數據移動次數約為：n2/4。

二、其它插人排序從上一節(jié)的討論中可見，直接插入排序算法簡便，且容易實現。當待排序記錄的數量n很小時，這是一種很好的排序方法。但是，通常待排序序列中的記錄數量n很大，則不宜采用直接插入排序。由此需要討論改進的辦法。在直接插入排序的基礎上，從減少“比較”和“移動”這兩種操作的次數著眼，可實現其他的插入排序的方法。1、折半插入排序由于插入排序的基本操作是在一個有序表中進行查找和插入，則從9.1節(jié)的討論中可知，這個“查找”操作可利用“折半查找”來實現，由此進行的插入排序稱之為折半插入排序(BinarylnsertionSort)，其算法如算法10.2所示。

voidBInsertSort(SqList&L){

//對順序表L作折半插入排序。

for(i=2；i<L.length；++i){L.r[0]=L.r[i]//L.r[i]暫存到L.r[0]low=1;high=i-1;//在r[low..high]中折半查找有序插入的位置

while(low<=high){m=(low+high)/2//折半

ifLT(L.r[0].key,L.r[m].key)high=m-1；

//插入點在低半區(qū)

elselow=m+1;//插入點在高半區(qū)}//whilefor(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//記錄后移

L.r[high+1]=L.r[0];//插入}//for}//BInsertSort

算法10.2折半插入排序所需附加存儲空間和直接插入排序相同，從時間上比較，折半插入排序僅減少了關鍵字間的比較次數，而記錄的移動次數不變。因此，折半插入排序的時間復雜度仍為O(n2)。三、希爾排序希爾排序(Shell’sSort)又稱“縮小增量排序”(DiminishingIncrementSort)，它也是一種屬插入排序類的方法，但在時間效率上較前述幾種排序方法有較大的改進。從對直接插入排序的分析得知，其算法時間復雜度為O(n2)，但是，若待排記錄序列為“正序”時，其時間復雜度可提高至O(n)。由此可設想，若待排記錄序列按關鍵字“基本有序”，即序列中具有下列特性

L.r[i].key<Max{L.r[j].key}(10-7)1≤j<i

的記錄較少時，直接插入排序的效率就可大大提高，從另一方面來看，由于直接插入排序算法簡單，則在n值很小時效率也比較高。希爾排序正是從這兩點分析出發(fā)對直接插入排序進行改進得到的一種插入排序方法。

它的基本思想是：

先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。[初始關鍵字]：4938659776132749*5504一趟排序結果：132749*55044938659776二趟排序結果：130449*38274955659776三趟排序結果：0413273849*4955657697從上述排序過程可見，希爾排序的一個特點是：子序列的構成不是簡單地“逐段分割”，而是將相隔某個“增量”的記錄組成一個子序列。如上例中，第一趟排序時的增量為5，第二趟排序時的增量為3，由于在前兩趟的插入排序中記錄的關鍵字是和同一子序列中的前一個記錄的關鍵字進行比較，因此關鍵字較小的記錄就不是一步一步地往前挪動，而是跳躍式地往前移，從而使得在進行最后一趟增量為1的插入排序時，序列已基本有序，只要作記錄的少量比較和移動即可完成排序，因此希爾排序的時間復雜度較直接插入排序低。

下面用算法語言描述上述希爾排序的過程，為此先將算法10.1改寫成如算法10.4所示的一般形式。希爾排序算法如算法10.5所示。voidShellInsert(SqList&L，intdk){

//對順序表L作一趟希爾插入排序。//本算法是和一趟直接插入排序相比，作了以下修改：//1、前后記錄位置的增量是dk，而不是1；//2、r[0]只是暫存單元，不是哨兵。當j<=0時，插入位置已找到。

for(i=dk+1；i<=L.length；++i)ifLT(L.r[i].key，L.r[i-dk].key){

//需將L.r[i]插入有序增量子表

L.r[0]=L.r[i]；

//暫存在L.r[0]

for(j=i-dk；j>0&<(L.r[0].key，L.r[j].key)；j-=dk)

L.r[j+dk]=L.r[j]；

//記錄后移，查找插入位置

L.r[j+dk]=L.r[0]；

//插入

}//if}//ShellInsert

算法10.4voidShellSort(Sqlist&L，intdlta[]，intt){

//按增量序列dlta[0..t-1]對順序表L作希爾排序。

for(k=0；k<t；++k)ShellInsert(L，dlta[k])；

//一趟增量為dlta[k]的插入排序

}//ShellSort

算法10.5

增量序列可以有各種取法，但需注意應使增量序列中的值沒有除1之外的公因子，并且最后一個增量值必須等于1。10.3快速排序這一節(jié)討論一類借助“交換”進行排序的方法，其中最簡單的一種就是人們所熟知的起泡排序(BubbleSort)。

起泡排序的過程很簡單。首先將第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序(即L.r[1].key>L.r[2].key)，則將兩個記錄交換之，然后比較第二個記錄和第三個記錄的關鍵字。依次類推，直至第n-1個記錄和第n個記錄的關鍵字進行過比較為止。上述過程稱作第一趟起泡排序，其結果使得關鍵字最大的記錄被安置到最后一個記錄的位置上。然后進行第二趟起泡排序，對前n-1個記錄進行同樣操作，其結果是使關鍵字次大的記錄被安置到第n-1個記錄的位置上?！?

一般地，第i趟起泡排序是從L.r[1]到L.r[n-i+1]依次比較相鄰兩個記錄的關鍵字，并在“逆序”時交換相鄰記錄，其結果是這n-i+1個記錄中關鍵字最大的記錄被交換到第n-i+1的位置上。整個排序過程需進行k(1<=k<n)趟起泡排序，顯然，判別起泡排序結束的條件應該是“在一趟排序過程中沒有進行過交換記錄的操作”。49383838381313384949491327276565651327383897761327494976132749*49*132749*652749*7649*97

圖10.6展示了起泡排序的一個實例Voidbublesort(ElemR[],intn){ inti=n; while(i>1){lastexchange=1;For(j=1;j<i;j++){if(A[j+1]<A[j]){swap(A[j],A[j+1]);lastexchange=j;}//ifi=lastexchange;}//for}//while}Lastexchange為一個下表值，其后是有序序列分析起泡排序的效率，容易看出，若初始序列為“正序”序列，則只需進行一趟排序，在排序過程中進行n-1次關鍵字間的比較，且不移動記錄；反之，若初始序列為“逆序”序列，則需進行n-1趟排序，需進行n(n-1)/2次比較，并作等數量級的記錄移動。因此，總的時間復雜度為O(n2)。

快速排序(QuickSort)是對起泡排序的一種改進。它的基本思想是，通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。假設待排序的序列為{L.r[s]，L.r[s+1]，…，L.r[t]}，首先任意選取一個記錄(通?？蛇x第一個記錄L.r[s]作為樞軸(或支點)(pivot)，然后按下述原則重新排列其余記錄：將所有關鍵字較它小的記錄都安置在它的位置之前，將所有關鍵字較它大的記錄都安置在它的位置之后。這個過程稱作一趟快速排序(或一次劃分)。一趟快速排序的具體做法是：附設兩個指針low和high，它們的初值分別為low和high，設樞軸記錄的關鍵字為pivotkey，則首先從high所指位置起向前搜索找到第一個關鍵字小于pivotkey的記錄和樞軸記錄互相交換，然后從low所指位置起向后搜索，找到第一個關鍵字大于pivotkey的記錄和樞軸記錄互相交換，重復這兩步直至low=high為止。其算法如算法10.6(a)所示。

intPartition(SqList&L，intlow，inthigh){

//交換順序表L中子表L.r[low..high]的記錄，使樞軸記錄到位，//并返回其所在位置，此時在它之前(后)的記錄均不大(小)于它。

pivotkey=L.r[low].key；//用子表的第一個記錄作樞軸記錄

while(low<high){

//從表的兩端交替地向中間掃描

while(low<high&&L.r[high].key>pivotkey)

--high;

L.r[low]

L.r[high];

//將比樞軸記錄小的記錄交換到低端

while(low<high&&L.r[low].key<pivotkey)++low;

L.r[low]

L.r[high];

//將比樞軸記錄大的記錄交換到高端

}

returnlow;

//返回樞軸所在位置

}//partition

算法10.6(a)

改寫上述算法，先將樞軸記錄暫存在r[0]的位置上，排序過程中只作r[low]或r[high]的單向移動，直至一趟排序結束后再將樞軸記錄移至正確位置上。intPartition(SqList&L，intlow，inthigh){

//交換順序表L中子表r[low．．high]的記錄，//樞軸記錄到位，并返回其所在位置，//此時在它之前(后)的記錄均不大(小)于它。

L.r[0]=L.r[low]；pivotkey=L.r[low].key；//樞軸記錄關鍵字

while(low<high){//從表的兩端交替地向中間掃描

while(low<high&&L.r[high].key>pivotkey)--high;L.r[low]=L.r[high];//將比樞軸記錄小的記錄移到低端lowwhile(low<high&&L.r[low].key<pivotkey)++low;L.r[high]=L.r[low];//將比樞軸記錄大的記錄移到高端}

L.r[low]=L.r[0];//樞軸記錄到位

returnlow；//返回樞軸位置

}//Partition快速排序示例：初始關鍵字：4938659776132749*

lowhigh進行1次交換之后：27386597761349*

lowhigh進行2次交換之后：27389776136549*

lowhigh進行3次交換之后：27381397766549*

lowhigh進行4次交換之后：27381376976549*

lowhighhigh完成一趟排序2738134976976549*初始狀態(tài)：{4938659776132749*}一次劃分之后：{273813}49{76976549*}分別進行快速排序：{13}27{38}{49*65}76{97}

49*{65}有序序列：{1327384949*657697}排序的全過程遞歸形式的快速排序算法如算法10.7和算法10.8所示。

voidQSort(SqList&L，intlow，inthigh){

//對順序表l中的子序列L.r[low．．high]作快速排序

if(low<high){

//長度大于1

pivotloc=Partition(L，low，high);

QSort(L，low，pivotloc-1);//對低子表遞歸排序

QSort(L，pivotloc+1，high)；//對高于表遞歸排序

}//QSort

算法10.7voidQuickSort(SqList&L){

//對順序表L作快速排序

QSort(L，1，L.length)；}//QuickSort

算法10.810.4選擇排序

選擇排序(SelectionSort)的基本思想是：每一趟在n-i+1(i=1，2，…，n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。其中最簡單、且為讀者最熟悉的是簡單選擇排序。(SimpleSelectionSort)。10.4.1簡單選擇排序

一趟簡單選擇排序的操作為：通過n-i次關鍵字間的比較，從n-i+1個記錄中選出關鍵字最小的記錄，并和第i(1≤i≤n)個記錄交換之。顯然，對L.r[1..n]中記錄進行簡單選擇排序的算法為：令i從1至n-1，進行n-1趟選擇操作，如算法10.9所示。

voidSelectSort(SqList&L){

//對順序表L作簡單選擇排序。

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

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

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

if(i!=j)L.r[i]

L.r[j]；//與第i個記錄交換

}}

算法10.9

容易看出，簡單選擇排序過程中，所需進行記錄移動的操作次數較少，其最小值為“0”，最大值為3(n-1)。

然而，無論記錄的初始排列如何，所需進行的關鍵字間的比較次數相同，均為n(n-1)/2。因此，總的時間復雜度也是O(n2)。

那末，能否加以改進呢?改進簡單選擇排序應從如何減少“比較”出發(fā)考慮。顯然，在n個關鍵字中選出最小值，至少進行n-1次比較，然而，繼續(xù)在剩余的n-1個關鍵字中選擇次小值就并非一定要進行n-2次比較，若能利用前n-1次比較所得信息，則可減少以后各趟選擇排序中所用的比較次數。實際上，體育比賽中的錦標賽便是一種選擇排序。

10.4.2樹形選擇排序

樹形選擇排序(TreeSelectionSort)，又稱錦標賽排序(TournamentSort)，是一種按照錦標賽的思想進行選擇排序的方法。首先對n個記錄的關鍵字進行兩兩比較，然后在其中ceil(n/2)個較小者之間再進行兩兩比較，如此重復，直至選出最小關鍵字的記錄為止。這個過程可用一棵有n個葉子結點的完全二叉樹表示。131338386513274938659713762749*(a)

輸出13之后輸出13、27之后

(b)(c)

由于含有n個葉子結點的完全二叉樹的深度為[log2n]+1，則在樹形選擇排序中，除了最小關鍵字之外，每選擇一個次小關鍵字僅需進行[log2n]次比較，因此，它的時間復雜度為，O(nlog2n)。但是，這種排序方法尚有輔助存儲空間較多、和“最大值”進行多余的比較等缺點。273827386576274938659776∞2749*383849*38657649*4938659776∞∞49*10.4.3堆排序

堆排序(HeapSort)只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。堆的定義如下：n個元素的序列{k1,k2,…,kn}當且僅當滿足下關系時，稱之為堆。

ki≤k2iki≥k2i

或

ki≤k2i+1，ki≥k2i+1(i=1,2,…,[n/2])若將和此序列對應的一維數組(即以一維數組作此序列的存儲結構)看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大于(或不小于)其左、右孩子結點的值。由此，若序列{k1，k2，…，kn}是堆，則堆頂元素(或完全二叉樹的根)必為序列中n個元素的最小值(或最大值)。例如，下列兩個序列為堆，對應的完全二叉樹如圖10.10所示。{96，83，27，38，11，09}{12，36，24，85，47，30，53，91}

圖10.10堆的示例9683273811091236248547305391

若在輸出堆頂的最小值之后，使得剩余n-1個元素的序列重又建成一個堆，則得到n個元素中的次小值。如此反復執(zhí)行，便能得到一個有序序列，這個過程稱之為堆排序。

由此，實現堆排序需要解決兩個問題：(1)如何由一個無序序列建成一個堆?(2)如何在輸出堆頂元素之后，調整剩余元素成為一個新的堆?

先討論第二個問題，如何在輸出堆頂元素之后，調整剩余元素成為一個新的堆?例如，圖10.11(a)是個堆，假設輸出堆頂元素之后，以堆中最后一個元素替代之，如圖10.11(b)所示。此時根結點的左、右子樹均為堆，則僅需自上至下進行調整即可。(a)(b)(c)(d)

我們稱這個自堆頂至葉子的調整過程為“篩選”。13382749*7665499797382749*7665491327384949*766597133849*499776652713如何由一個無序序列建成一個堆?從一個無序序列建堆的過程就是一個反復“篩選”的過程。若將此序列看成是一個完全二叉樹，則最后一個非終端結點是第n/2個元素，由此“篩選”只需從第n/2個元素開始。例如，圖10.12(a)中的二叉樹表示一個有8個元素的無序序列則篩選從第4個元素開始

123