數(shù)據(jù)結(jié)構(gòu)第9章 排序

第9章排序

數(shù)據(jù)結(jié)構(gòu)（C++描述）

目錄

9.1基本概念

9.2插入排序

9.4選擇排序

9.5歸并排序

*9.6分配排序

退出

9.1基本概念

9.1.1排序介紹

排序（Sorting）是數(shù)據(jù)處理中一種很重要的運(yùn)算，

同時(shí)也是很常用的運(yùn)算，一般數(shù)據(jù)處理工作25%的

時(shí)間都在進(jìn)行排序。簡(jiǎn)單地說，排序就是把一組記

錄（元素）按照某個(gè)域的值的遞增（即由小到大）

或遞減（即由大到小）的次序重新排列的過程。

表9-1學(xué)生檔案表

學(xué)號(hào)姓名年齡性別

99001王曉佳18男

99002林一鵬19男

99003謝寧17女

99004張麗娟18女

99005周濤20男

99006李小燕16女

千二例如，在表9-1中,若以每個(gè)記錄的學(xué)號(hào)為關(guān)鍵字，按

'排序碼年齡的遞增(由小到大)排序，則所有記錄的排

序結(jié)果可簡(jiǎn)記為：

{(99006,16),(99003,17),(99001,18),

(99004,18)，(99002,19)，(99005,20)｝；

*：也可能為：

|{(99006,16),(99003,17),(99004,18),

\(99001,18),(99002,19),(99005,20)}；

力這兩個(gè)結(jié)果都是表9-1按年齡的遞增排序結(jié)果。若按排序

(碼姓名來進(jìn)行遞增排序，則得到的排序結(jié)果為：

\{(99006,李小燕)，(99002,林一鵬)，(99001,

)王曉佳)，(99003,謝寧)，(99004,張麗娟)，

,(99005,周濤)}

?當(dāng)然，我們還可以按排序碼性別來進(jìn)行遞增排序，在此

］不再作進(jìn)一步的分析。

9/1,2基本概念

Y.*1.排序碼（SortKey）

第%作為排序依據(jù)的記錄中的一個(gè)屬性。它可以是任何一種

rI可比的有序數(shù)據(jù)類型，它可以是記錄的關(guān)鍵字，也可以

”是任何非關(guān)鍵字。如上例中的學(xué)生年齡。在此我們認(rèn)為

對(duì)任何一種記錄都可找到一個(gè)取得它排序碼的函數(shù)

|Skey（一個(gè)或個(gè)關(guān)鍵字的組合）。

\2.有序表與無序表

》二組記錄按排序碼的遞增或遞減次序排列得到的結(jié)果被

V稱之為有序表，相應(yīng)地，把排序前的狀態(tài)稱為無序表。

\3.正序表與逆序表

J若有序表是按排序碼升序排列的，則稱為升序表或正序

X表，否則稱為降序表或逆序表。不失普遍性，我們一般

7只討論正序表。

4.排序定義

若給定一組記錄序列[1,馬，…，。，其排序碼分別

為S],s2,,sn,將這些記錄排成順序?yàn)椤?

rk2,%的一個(gè)序列R"滿足條件SkiSSkzW…

獲得這些記錄排成順序?yàn)椋?r，…，％的一個(gè)序

列RL滿足條件.字/…卷項(xiàng)的過程稱為界序。

yAi_/1.±

也可以說，將一組記錄按某排序碼遞增或遞減排列的

過程，稱為排序。

穩(wěn)定與不穩(wěn)定

因?yàn)榕判虼a可以不是記錄的關(guān)鍵字，同一排序碼值可能對(duì)應(yīng)

多個(gè)記錄。對(duì)于具有同一排序碼的多個(gè)記錄來說，若采用的

排序方法使排序后記錄的相對(duì)次序不變，則稱此排序方法是

穩(wěn)定的，否則稱為不穩(wěn)定的。在上例中（見表9-1,按年齡排

序），如果一種排序方法使排序后的結(jié)果必為前一個(gè)結(jié)果，

則稱此方法是穩(wěn)定的；若一種排序方法使排序后的結(jié)果可能

為后一個(gè)結(jié)果，則稱此方法是不穩(wěn)定的。

U?，：、￡36內(nèi)排序與外排序

‘按照排序過程中使用內(nèi)外存的不同將排序方法分為內(nèi)排序

0A和外排序。若排序過程全部在內(nèi)存中進(jìn)行，則稱為內(nèi)排序;

Tf若排序過程需要不斷地進(jìn)行內(nèi)存和外存之間的數(shù)據(jù)交換，

；1則稱為外排序。內(nèi)排序大致可分為五類：插入排序、交換

排序、選擇排序、歸并排序和分配排序。本章僅討論內(nèi)排

G序。

X7.排序的時(shí)間復(fù)雜性

》排序過程主要是對(duì)記錄的排序碼進(jìn)行比較和記錄的移動(dòng)過

/程。因此排序的時(shí)間復(fù)雜性可以算法執(zhí)行中的數(shù)據(jù)比較次

A數(shù)及數(shù)據(jù)移動(dòng)次數(shù)來衡量。當(dāng)一種排序方法使排序過程在

\\最壞或平均情況下所進(jìn)行的比較和移動(dòng)次數(shù)越少，則認(rèn)為

\\該方法的時(shí)間復(fù)雜性就越好，分析一種排序方法，不僅要

\/分析它的時(shí)間復(fù)雜性，而且要分析它的空間復(fù)雜性、穩(wěn)定

A性和簡(jiǎn)單性等。

二々為了以后討論方便，我們直接將排序碼寫成一個(gè)一維數(shù)

<r組的形式，具體類型設(shè)為Elemtype,并且在沒有聲明的情

形下，所有排序都按排序碼的值遞增排列。

插入排序（直插排序、二分排序、希爾排序）

交換排序（冒泡排序、快速排序）

排序選擇排序（直選排序、樹型排序、堆排序）

歸并排序（二路歸并排序、多路歸并排序）

分配排序（多關(guān)鍵字排序、基數(shù)排序）

弋9.2插入排序

七7921直接插入排序

1.直接插入排序的基本思想

直接插入排序(StraightInsertionSorting)的基本思想是：把

；

■n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無序表，開始時(shí)

|有序表中只包含一個(gè)元素，無序表中包含有n-1個(gè)元素，排序

過程中每次從無序表中取出第一個(gè)元素，把它的排序碼依次

\與有序表元素的排序碼進(jìn)行比較，將它插入到有序表中的適

1當(dāng)位置，使之成為新的有序表。

2.直接插入的算法實(shí)現(xiàn)

voidinsertsort(ElemTypeR[],intn)

〃待排序元素用一個(gè)數(shù)組R表示，數(shù)組有n個(gè)元素

{for(inti=l;i<n;i++)〃i表示插入次數(shù)，共進(jìn)行n-1次

插入

{ElemTypetemp=R[i];〃把待排序元素賦給temp

intj=i-l;

while((j>=0)&&(temp<R[j]))

{R[j+l]=R[j];j--;}〃順序比較和移動(dòng)

R[j+l]=temp;}

例如，n=6,數(shù)組R的六個(gè)排序碼分別為：17,3,25,

14,20,9o它的直接插入排序的執(zhí)行過程如圖9-1所

Zj\O

R[0]R⑴R[2]R[3]R[4]R[5]

9

初始狀態(tài)

2O9

第一次插入

9

第二次插入

第三次插入2J0

259

第四次插入J

\

472O25!

第五次插入7

圖9-1直接插入排序示例

_1古撫人排岸占右方々奉益耕

,'從上面的'敘述可以看出了直接插入排序算法十分簡(jiǎn)單。

那么它的效率如何呢？首先從空間來看，它只需要一個(gè)

元素的輔助空間，用于元素的位置交換。從時(shí)間分析，

首先外層循環(huán)要進(jìn)行n-1次插入，每次插入最少比較一次

（正序），移動(dòng)兩次；最多比較i次，移動(dòng)i+2次（逆后）

（i=l,2,n-1）o若分別用,C和Cave表示

元素的總比較次數(shù)的最小值、最大值和平均值，用Mmm，

Mmax和Mave表示元素的總移動(dòng)次數(shù)的最小值、最大值和

平均值，則上述直接插入算法對(duì)應(yīng)的這些量為：

CminflMmi/2(n-1)

Cmdaxx=l+2+…+n-l=(n2-n)/2Mmdx=3+4+...+n+l=

(n2+3n-4)/2

22

Cave=(n+n-2)/4Mmax=(n+7n-8)/4

因此，直接插入排序的時(shí)間復(fù)雜度為O(#)。

直接插入算法的元素移動(dòng)是順序的，該方法是穩(wěn)定的。

922二分插入排序

1.三分插入排序的基本思想

二分插入排序(BinaryInsertSort)的基本思想是：

在有序表中采用二分查找的方法查找待排元素的插

入位置。

其處理過程：先將第一個(gè)元素作為有序序列，進(jìn)行n-

1次插入，用二分查找的方法查找待排元素的插入位

置，將待排元素插入。

3.二分插入排序的效率分析

二分插入算法與直接插入算法相比，需要輔助空間與直接

插入排序基本一致；時(shí)間上，前者的比較次數(shù)比直接插入

查找的最壞情況好，最好的情況壞，兩種方法的元素的移

動(dòng)次數(shù)相同，因此二分插入排序的時(shí)間復(fù)雜度仍為o

(M)。

二分插入算法與直接插入算法的元素移動(dòng)一樣是順序的,

因此該方法也是穩(wěn)定的。

2.二分插入排序的算法實(shí)現(xiàn)

其算法如下：

voidBinaryInsertSort(ElemTypeR[],intn)

{for(inti=l;i<n;i++)//共進(jìn)行n-1次插入

{intleft=O,right=i-1;ElemTypetemp=R[i];

while(left<=right)

{intmiddle=(left+right)/2;〃取中點(diǎn)

if(temp<R[middle])right=middle-l;〃取左區(qū)間

elseleft=middle+1;}〃取右區(qū)間

fbr(intj=i-l;j>=left;j-)

R[j+l>R[j]；〃元素后移空出插入位

R[left]=temp;}}

9.2.3希爾排序

1.希爾排序的基本思想

希爾排序(ShellSort)又稱為“縮小增量排序”。是

1959年由D.L.Shell提出來的。該方法的基本思想是：先

將整個(gè)待排元素序列分割成若干個(gè)子序列(由相隔某個(gè)

“增量”的元素組成的)分別進(jìn)行直接插入排序，待整

個(gè)序列中的元素基本有序(增量足夠小)時(shí)，再對(duì)全體

元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠?/p>

基本有序的情況下(接近最好情況)，效率是很高的，

因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。

3.希爾排序的效率分析

雖然我們給出的算法是三層循環(huán)，最外層循環(huán)為log2n數(shù)

量級(jí)，中間的for循環(huán)是n數(shù)量級(jí)的，內(nèi)循環(huán)遠(yuǎn)遠(yuǎn)低于n數(shù)

量級(jí)，因?yàn)楫?dāng)分組較多時(shí)，組內(nèi)元素較少；此循環(huán)次數(shù)

少；當(dāng)分組較少時(shí)，組內(nèi)元素增多，但已接近有序，循

環(huán)次數(shù)并不增加。因此，希爾排序的時(shí)間復(fù)雜性在0

213

(nlog2n)和0(n)之間，大致為0(n-)。

例如,n=8,數(shù)組R的八個(gè)元素分別為：17,3,30,

25,14,17,20,9o下面用圖9-2給出希爾排序算法

的執(zhí)行過程。

初始狀態(tài)，1=417330251417209

第一趟結(jié)果，1=214320917173025

第二趟結(jié)果，1=114317920173025

第三趟結(jié)果39141717202530

圖9-2希爾排序算法的執(zhí)行過程

由于希爾排序?qū)γ總€(gè)子序列單獨(dú)比較，在比較時(shí)進(jìn)行元

素移動(dòng)，有可能改變相同排序碼元素的原始順序，因此

希爾排序是不穩(wěn)定的。例如，給定排序碼3,4,2,2,

則希爾排序的結(jié)果變成2,2,3,4o

9.3交換排序

9.3.1冒泡排序

1.冒泡排序的基本思想

冒泡排序（BubbleSorting）的基本思想是：是通過對(duì)

待排序序列從后向前（從下標(biāo)較大的元素開始），依

次比較相鄰元素的排序碼，若發(fā)現(xiàn)逆序則交換，使排

序碼較小的元素逐漸從后部移向前部（從下標(biāo)較大的

單元移向下標(biāo)較小的單元），就象水底下的氣泡一樣

逐漸向上冒。

因?yàn)榕判虻倪^程中，各元素不斷接近自己的位置，如

果一趟比較下來沒有進(jìn)行過交換，就說明序列有序，

因此要在排序過程中設(shè)置一個(gè)標(biāo)志flag判斷元素是否進(jìn)

行過交換。從而減少不必要的比較。

「\.二72.冒泡排序的算法實(shí)現(xiàn)

‘下面給出冒泡排序算法。

voidBubblesort(ElemTypeR[],intn)

{intflag=l;〃當(dāng)flag為0則停止排序

for(inti=l;i<n;i++)

{〃i表示趟數(shù)，最多n-1趟

flag=O;〃開始時(shí)元素未交換

for(intj=n-l;j>=i;j-)

if(R[j]<R|j-l]){〃發(fā)生逆序ElemTypet=R[j];

RD]=RD-1];

R[j-l]=t;flag=l;}〃交換，并標(biāo)記發(fā)生了交換

if(flag=O)return;}}

J

q怎y例如，n=6,數(shù)組R的六個(gè)排序碼分別為：17,3,25,14,

<r20,9o卜面用圖9-3給出冒泡排序算法的執(zhí)行過程。

%XR[0]R[l]R[2]R[3]R[4]R[5]

'|初始狀態(tài)(1732514209)

1

,_________1,1

*?ii

1,第一趟排序3(179251420)

111

，第二趟排序39(17142520)

\，----------1，----------1

X第三三趟排序3914(172025)

第四趟排序3914172025

\圖9-3冒泡排序示例

'3.冒泡排序的效率分析

&從上面的例子可以看出，當(dāng)進(jìn)行完第三趟排序時(shí)，數(shù)

M組已經(jīng)有序，所以第四趟排序的交換標(biāo)志為0,即沒進(jìn)

I行交換，所以不必進(jìn)行第四趟排序。

從冒泡排序的算法可以看出，若待排序的元素為正序,

則只需進(jìn)行一趟排序，比較次數(shù)為(n-l)次，移動(dòng)元

素次數(shù)為0;若待排序的元素為逆序，則需進(jìn)行n-l趟

排序，比較次數(shù)為(n2-n)/2,移動(dòng)次數(shù)為3(n2-n)/2,因

此冒泡排序算法的時(shí)間復(fù)雜度為O(/)。由于其中的

元素移動(dòng)較多，所以屬于內(nèi)排序中速度較慢的一種。

因?yàn)槊芭菖判蛩惴ㄖ贿M(jìn)行元素間的順序移動(dòng)，所以是

一個(gè)穩(wěn)定的算法。

9.3.2快速排序

1.快速排序的基本思想

快速排序(QuickSorting)是迄今為止所有內(nèi)排序算

法中速度最快的一種。它的基本思想是：任取待排序

序列中的某個(gè)元素作為基準(zhǔn)(一般取第一個(gè)元素)，

通過一趟排序，將待排元素分為左右兩個(gè)子序列，左

子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼,

右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分

別對(duì)兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。

快速排序是對(duì)冒泡排序的一種改進(jìn)方法，算法中元素

的比較和交換是從兩端向中間進(jìn)行的，排序碼較大的

元素一次就能夠交換到后面單元，排序碼較小的記錄

一次就能夠交換到前面單元，記錄每次移動(dòng)的距離較

遠(yuǎn)，因而總的比較和移動(dòng)次數(shù)較少。

快速排序的過程為：把待排序區(qū)間按照第一個(gè)元素

（即基準(zhǔn)元素）的排序碼分為左右兩個(gè)子序列的過程

叫做一次劃分。設(shè)待排序序列為?R[right],其

中l(wèi)eft為下限，right為上限，left〈right,為該序

列的基準(zhǔn)元素，為了實(shí)現(xiàn)一次劃分，令i,j的初值分別

為left和right。在劃分過程中，首先讓j從它的初值開

始，依次向前取值，并將每一元素R[j]的排序碼同

的排序碼進(jìn)行比較，直到R[j]vR[left]時(shí)，交換

R[j]與R[le用的值，使排序碼相對(duì)較小的元素交換到左

子序列，然后讓i從i+1開始，依次向后取值，并使每

一元素R[i]的排序碼同RU]的排序碼（此時(shí)R[j]為基準(zhǔn)

元素）進(jìn)行比較，直到R[i]〉R[j]時(shí)，交換R[i]與R[j]

的值，使排序碼大的元素交換到后面子區(qū)間；再接著

讓j從j-1開始，依次向前取值，重復(fù)上述過程，直到i

等于j,即指向同一位置為止，此位置就是基準(zhǔn)元素最

終被存放的位置。此次劃分得到的前后兩個(gè)待排序的

子序列分別為?R[i-1]和R[i+1]~R[right]。

例如，給定排序碼為:(46,55,13,42,94,05,17,

'70),具體劃分如圖9-4所示。

[4655134294051770]

iAj木

[4655134294051770]

iAi4

[1755134294054670]

iA

[1746134294055570]

iAj木

[1705134294465570]

jl

口705134294465570]

j木

[1705134294465570]

iA

[1705134294]46[5570]

圖9-4快速排序的一次劃分

從圖9一4可知，通過一次劃分，將一個(gè)區(qū)間以基準(zhǔn)值分成

兩個(gè)子區(qū)間，左子區(qū)間的值小于等于基準(zhǔn)值，右子區(qū)間

的值大于基準(zhǔn)值。對(duì)剩下的子區(qū)間重復(fù)此劃分步驟，則

可以得到快速排序的結(jié)果。

，2.快速排序的算法實(shí)現(xiàn)

i下面給出快速排序算法的遞歸算法如下:

voidquicksort(ElemTypeR[],intleft,intright)

{inti=left,j=right;ElemTypetemp=R[i];

while(i<j)

{while

{R[i]=R[j];i=i+l;}

while((R[i]<=temp)&&(j>i))i=i+l;

if(i<j){RH=R[i]；j=j-l；})

〃一次劃分得到基準(zhǔn)值的正確位置

R[i]=temp;

if(left<i-1)quicksort(R,left,i-1);〃遞歸調(diào)用左子區(qū)間

if(i+l<right)quicksort?i+1,right);}〃遞歸調(diào)用右子區(qū)間

一<；,」3.快源排序的效率分析

若快速排序出現(xiàn)最好的情形(左、右子區(qū)間的長(zhǎng)度大致

I相等)，則結(jié)點(diǎn)數(shù)n與二叉樹深度h應(yīng)滿足

￡二log2n<h<log2n+l,所以總的比較次數(shù)不會(huì)超過(n+1)

log2no因此，快速排序的最好時(shí)間復(fù)雜度應(yīng)為0

\(nlog2n)o而且在理論上已經(jīng)證明，快速排序的平均

V時(shí)間復(fù)雜度也為O(nlog2n)。

(|若快速排序出現(xiàn)最壞的情形(每次能劃分成兩個(gè)子區(qū)間,

C\但其中一個(gè)是空)，則這時(shí)得到的二叉樹是一棵單分枝

飛樹，得到的非空子區(qū)間包含有n-i個(gè)(i代表二叉樹的層數(shù)

/?(l<i<n)元素，每層劃分需要比較n-i+2次，所以總的

A比較次數(shù)為(n2+3n-4)12。因此，快速排序的最壞時(shí)間

(\復(fù)雜度為0(#)。

\|快速排序所占用的輔助空間為棧的深度，故最好的空間

V復(fù)雜度為0(log2i!)，最壞的空間復(fù)雜度為o(n)。

快速排序是一種不穩(wěn)定的排序方法O

'y4選擇排序

腔二941直接選擇排序

TTi.直接選擇排序的基本思想

V、、…

7直接選擇排序(straightselectsorting)也是一種簡(jiǎn)單的

排序方法。它的基本思想是：第一次從R[0]?R[n-1]中選

A取最小值，與R[0]交換，第二次從R[l]?R[n-1]中選取最

飛小值，與R[l]交換，第三次從R⑵?R[n-1]中選取最小值,

/與R[2]交換，…，第i次從R[i-1]?R[n-1]中選取最小值，

X與交換，…，第n-1次從R[n-2]?R[n-1]中選取最小值,

A與R[n-2]交換，總共通過n-l次，得到一個(gè)按排序碼從小

I\到大排列的有序序列。

例如，給定n=8,數(shù)組R中的8個(gè)元素的排序碼為：(8,

3,2,1,7,4,6,5),則直接選擇排序過程如圖9-5

所示。

初始狀態(tài)[83217465]

第一次13287465]

第二次[12387465]

第三次[12387465]

第四次[12347865]

第五次[12345867]

LJ

第六次[12345687]

第七次[12345678]

圖9-5直接選擇排序的過程示例

3.直接選擇排序的效率分析

r^JT

、在直接選擇排序中，共需要進(jìn)行n-1次選擇和交換，每次

選擇需要進(jìn)行n-i次比較(14勺1-1),而每次交換最

多需3次移動(dòng)，因此/總的比較次數(shù)C=￡(〃-，)=(n2-n)/2,

〃T/-=!

■總的移動(dòng)次數(shù)M=^3=3(n-l)。由此可知，直接選擇

排序的時(shí)間復(fù)雜膜40(n2)數(shù)量級(jí)，所以當(dāng)記錄占用的字

節(jié)數(shù)較多時(shí)，通常比直接插入排序的執(zhí)行速度要快一些。

由于在直接選擇排序中存在著不相鄰元素之間的互換，

因此，直接選擇排序是一種不穩(wěn)定的排序方法。例如，

給定排序碼為3,7,3,2,1,排序后的結(jié)果為1,2,3,

3,7o

,942樹形選擇排序

從直接選擇排序可知，在n個(gè)排序碼中，找出最小值需n-

1次比較，找出第二小值需n-2次比較，找出第三小值需

n-3次比較，其余依此類推。所以，總的比較次數(shù)為：

(n-l)+(n-2)+...+3+2+1=(n2-n)/2,那么,能否對(duì)直接選擇

排序算法加以改進(jìn)，使總的比較次數(shù)比(n2-n)/2小呢？顯

然，在n個(gè)排序碼中選出最小值，至少進(jìn)行n-1次比較，

但是，繼續(xù)在剩下的n-1個(gè)關(guān)鍵字中選第二小的值，就并

非一定要進(jìn)行n-2次比較，若能利用前面n-1次比較所得

信息，則可以減少以后各趟選擇排序中所用的比較次數(shù),

比如8個(gè)運(yùn)動(dòng)員中決出前三名，不需要7+6+5=18場(chǎng)比賽

(前提是，若甲勝乙，而乙勝丙，則認(rèn)為甲勝丙)，最

多需要11場(chǎng)比賽即可(通過7場(chǎng)比賽產(chǎn)生冠軍后，第二

名只能在輸給冠軍的三個(gè)對(duì)中產(chǎn)生，需2場(chǎng)比賽，而第

三名只能在輸給亞軍的三個(gè)對(duì)中產(chǎn)生，也需2場(chǎng)比賽，

總共11場(chǎng)比賽)。具體見圖9-6所示。

「從圖9-6(a)可知，8個(gè)隊(duì)經(jīng)過4場(chǎng)比賽，獲勝的4個(gè)隊(duì)

以進(jìn)入半決賽，再經(jīng)過2場(chǎng)半決賽和1場(chǎng)決賽即可知道冠軍

,屬誰(共7場(chǎng)比賽)按照錦標(biāo)賽的傳遞關(guān)系，亞軍只能

；1產(chǎn)生于分別在決賽，半決賽和第一輪比賽中輸給冠軍的

選取手中，于是亞軍只能在b、c、e這3個(gè)隊(duì)中產(chǎn)生(見

圖9-6(b)),即進(jìn)行2場(chǎng)比賽(e與c一場(chǎng)，e與c的勝

I隊(duì)與b一場(chǎng))后，即可知道亞軍屬誰。同理，第三名只

A需在c、f、g這3個(gè)隊(duì)產(chǎn)生(見圖9-6(c))即進(jìn)2場(chǎng)比賽

q1與g一場(chǎng)，f與g的勝隊(duì)與c一場(chǎng))即可知道第三名屬誰。

V樹形選擇排序(treeselectionsorting),又稱錦標(biāo)賽排序

八(tournamentsorting),是一種按照錦標(biāo)賽的思想進(jìn)行

\\選擇排序的方法。首先對(duì)口個(gè)記錄的排序碼進(jìn)行兩兩比

\)較，然后在其中「n/21個(gè)較小者之間再進(jìn)行兩兩比較，如

V此重復(fù)，直到選出最小排序碼為止。

例如，給定排序碼頭50,37,66,98,75,12,26,49,

樹形選擇排序過程見圖9-7。

12

(b)輸出12后，經(jīng)過2次比較得到第二小值26

(a)經(jīng)過7次比較得到最小值12

c)輸出12,26后，經(jīng)過2次比較得到第三小值(d)輸出12,26,37后，經(jīng)過2次比較得到第四小值49

(f)輸出12,26,37,49,50后,經(jīng)過1次比較得到第六小值66

(h)輸出12,26,37,49,50,66,75后,經(jīng)過1次比較得到第八小值98

圖9-7樹形選擇排序示意過程

輸出12,26,37,49,50,66后，經(jīng)過1次比較得到第七小值75

'9.4.3堆排序

1.堆的定義

若有n個(gè)元素的排序碼占，k2,k3,kn,當(dāng)滿足如下

條”_

⑴；1*計(jì)1或⑵k>k21+1其中

i=l,2,...,Ln/2j

則稱此n個(gè)元素的排序碼k],k2,k3,kn為一個(gè)堆。

若將此排序碼按順序組成一棵完全二叉樹，則（1）稱為

小根堆（二叉樹的所有根結(jié)點(diǎn)值小于或等于左右孩子的

值），（2）稱為大根堆（二叉樹的所有根結(jié)點(diǎn)值大于或

等于左右孩子的值）。

'若n個(gè)元素的排序碼k],k2,k3,與滿足堆，且讓結(jié)

J點(diǎn)按1、2、3n順序編號(hào)，根據(jù)完全二叉樹的性質(zhì)

片/（若i為根結(jié)點(diǎn)，則左孩子為2i,右孩子為2i+l）可知，

1堆排序?qū)嶋H與一棵完全二叉樹有關(guān)。若將排序碼初始序

「列組成一棵完全二叉樹，則堆排序可以包含建立初始堆

4（使排序碼變成能符合堆的定義的完全二叉樹）和利用

1堆進(jìn)行排序兩個(gè)階段。

\2.堆排序的基本思想

）將排序碼I，k2,k3,I表示成一棵完全二叉樹，

V然后從第1n/2」個(gè)排序碼開始篩選，使由該結(jié)點(diǎn)作根結(jié)

\點(diǎn)組成的子二叉樹符合堆的定義，然后從第Ln/2」-1個(gè)排

\序碼重復(fù)剛才操作，直到第一個(gè)排序碼止。這時(shí)候，該

L）二叉樹符合堆的定義，初始堆已經(jīng)建立。

￡工：接著，可以按如下方法進(jìn)行堆排序：將堆中第一個(gè)結(jié)點(diǎn)

xs'（二叉樹根結(jié)點(diǎn)）和最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行交換（占與

I）,再將I?I1重新建堆，然后1和11交換，再將

I?I2重新建堆，然后I和交換，如此重復(fù)下去，每次

重新建堆的元素個(gè)數(shù)不斷減1,直到重新建堆的元素個(gè)數(shù)

僅剩一個(gè)為止。這時(shí)堆排序已經(jīng)完成，則排序碼占，k2,

■

k3,I已排成一個(gè)有序序列。

若排序是從小到大排列，則可以用建立大根堆實(shí)現(xiàn)堆排

序，若排序是從大到小排列，則可以用建立小根堆實(shí)現(xiàn)

堆排序。

例如,給定排序碼46,55,13,42,94,05,17,70,

建立初始堆的過程如圖9-8所示。

A久46

(a)初始無序的結(jié)點(diǎn)，從42開始調(diào)整

圖9-8建立初始大根堆的過程示意圖

對(duì)排序碼46,55,13,42,94,05,17,70,建成如圖9-

康；’8（e）所示的大根堆后，堆排序過程如圖9-9所示。

初始堆(b)94與42交換

（C）前7個(gè)排序碼重新建成堆（d）70和13交換

05

(e)前6個(gè)排序碼重新建成堆(f)55和05交換

(g)前5個(gè)排序碼重新建成塘(h)46和05交換

05

(k)前3個(gè)排序碼重新建成堆(1)17和05交換

*(m)前2個(gè)排序碼重新建成堆(n)13和05交換

*

(圖9-9堆排序過程示意圖

I從圖9-9(n)可知，將其結(jié)果按完全二叉樹形式輸出，

\則得到結(jié)果為：05,13,17,42,46,55,70,94,即

》為堆排序的結(jié)果。

/4.堆排序的效率分析

\在整個(gè)堆排序中，共需要進(jìn)行n+Ln/2」-1次篩選運(yùn)算，每次

\篩選運(yùn)算進(jìn)行雙親和孩子或兄弟結(jié)點(diǎn)的排序碼的比較和移動(dòng)

J次數(shù)都不會(huì)超過完全二叉樹的深度，所以，每次篩選運(yùn)算的

)時(shí)間復(fù)雜度為O(log2n)，故整個(gè)堆排序過程的時(shí)間復(fù)雜度為

〈O(nlog2n)0

；'堆排序占用的輔助空間為1（供交換元素用），故它

的空間復(fù)雜度為0（1）。

堆排序是一種不穩(wěn)定的排序方法，例如，給定排序碼:

2,1,2,它的排序結(jié)果為：1,2,2o

9.5歸并排序

9.5.1二路歸并排序

二路歸并排序的基本思想

二路歸并排序的基本思想是：將兩個(gè)有序子區(qū)間（有序表）

合并成一個(gè)有序子區(qū)間，一次合并完成后，有序子區(qū)間的

數(shù)目減少一半，而區(qū)間的長(zhǎng)度增加一倍，當(dāng)區(qū)間長(zhǎng)度從1

增加到n（元素個(gè)數(shù)）時(shí)，整個(gè)區(qū)間變?yōu)橐粋€(gè)，則該區(qū)間

中的有序序列即為我們所需的排序結(jié)果。

例如，給定排序碼46,55,13,42,94,05,17,70,

路歸并排序過程如圖9-10所示。

初始狀態(tài)：[46][55][13][42][94][05][17][70]

111_____1LJ.LJ

一趟歸并：[4655][1342][0594][1770]

L_____II

二趟歸并：[13424655][05177094]

LI

三趟歸并：[0513174246557094]

圖9-10二路歸并排序過程示意圖

r3.二路歸并排序的效率分析

工寮二路歸并排序的時(shí)間復(fù)雜度等于歸并趟數(shù)與每一趟時(shí)間復(fù)

n雜度的乘積。而歸并趟數(shù)為「1"2口〕(當(dāng)「1"2口】為奇數(shù)時(shí)，則

、:為「10g2ll1+1)。因?yàn)槊恳惶藲w并就是將兩兩有序子區(qū)間合并

\成一個(gè)有序子區(qū)間，而每一對(duì)有序子區(qū)間歸并時(shí)，記錄的

(]比較次數(shù)均小于等于記錄的移動(dòng)次數(shù)(即由一個(gè)數(shù)組復(fù)制

A到另一個(gè)數(shù)組中的記錄個(gè)數(shù))，而記錄的移動(dòng)次數(shù)等于這

'一對(duì)有序表的長(zhǎng)度之和，所以，每一趟歸并的移動(dòng)次數(shù)均

Q等于數(shù)組中記錄的個(gè)數(shù)n,即每一趟歸并的時(shí)間復(fù)雜度為

4O(n)o因此，二路歸并排序的時(shí)間復(fù)雜度為O(nlog2n)。

\\利用二路歸并排序時(shí)，需要利用與待排序數(shù)組相同的

\/輔助數(shù)組作臨時(shí)單元，故該排序方法的空間復(fù)雜度為

A0(n),比前面介紹的其它排序方法占用的空間大。

:’由于二路歸并排序中，每?jī)蓚€(gè)有序表合并成一個(gè)有序表

時(shí)，若分別在兩個(gè)有序表中出現(xiàn)有相同排序碼，則會(huì)使

前一個(gè)有序表中相同排序碼先復(fù)制，后一有序表中相同

排序碼后復(fù)制，從而保持它們的相對(duì)次序不會(huì)改變。所

以，二路歸并排序是一種穩(wěn)定的排序方法。

*9.5.2多路歸并排序

將三個(gè)或三個(gè)以上有序子區(qū)間合并成一個(gè)有序子區(qū)間

的排序，稱為多路歸并排序。常見的有三路歸并排序

（三個(gè)有序子區(qū)間合并成一個(gè)有序子區(qū)間）、四路歸

并排序（四個(gè)有序子區(qū)間合并成一個(gè)有序子區(qū)間）等,

具體實(shí)現(xiàn)的方法與二路歸并排序類似，在此，不再贅

述。

*9.6分配排序

9.6.1多關(guān)鍵字排序

在實(shí)際應(yīng)用中，有時(shí)的排序會(huì)需要按幾種不同排序碼來

排序。例如，描述一個(gè)單位的職工信息，既要按出生日

期排序，又要按工資排序，則是一種典型的多關(guān)鍵字排

序。又如，將一副撲克牌中52張牌按從小到大排列，

（規(guī)定花色大小為：梅花〈方塊〈紅桃〈黑桃二面值大小

規(guī)定為：2<3<4<...<10<J<Q<K<A）,則一副撲克牌的

排序也是多關(guān)鍵字排序。

對(duì)于多關(guān)鍵字排序（假設(shè)有d個(gè)關(guān)鍵字），則可以按第1、

2、…、d個(gè)關(guān)鍵字的順序排序，也可以按第d、d-1、d-

2.........2、1個(gè)關(guān)鍵字的順序排序。例如，剛才的撲克

牌排序，可以先按花色排成4堆，然后將每一堆再按面

值排序，則可以得到52張牌的有序序列。具體實(shí)現(xiàn)不再

介紹。

<'9,6.2鏈?zhǔn)交鶖?shù)排序

1.基數(shù)排序的基本思想

基數(shù)排序(radixsorting)是和前面所述各類排序方法完

全不同的一種排序方法。在前面幾節(jié)中，實(shí)現(xiàn)排序主要

是通過排序碼之間的比較和移動(dòng)兩項(xiàng)操作來進(jìn)行的，而

基數(shù)排序不需要進(jìn)行排序碼的比較，它是一種借助多關(guān)

鍵字(多個(gè)排序碼)排序的思想來實(shí)現(xiàn)單關(guān)鍵字排序的

排序方法。

具體實(shí)現(xiàn)時(shí)，假設(shè)每個(gè)元素有d個(gè)排序碼，則可以先按

第1個(gè)排序碼對(duì)每個(gè)元素排序，然后再按第2個(gè)排序碼排

序，…，最后再按第d個(gè)排序碼排序。最后的結(jié)果即為

基數(shù)排序的結(jié)果。

例如，給定排序碼序列123,78,65,9,108,7,8,3,

68,309,基數(shù)排序的步驟見圖9-H。

初始狀態(tài):1237865910878368309

一趟（按個(gè)位）：1233657781088689309

二趟（按十位）：3789108309123656878

三趟（按百位）：3789656878108123309

圖9-11基數(shù)排序的步驟

具體實(shí)現(xiàn)時(shí)，基數(shù)排序包含分配和收集，分配是將第k

（l<k<d）個(gè)排序碼相同的元素放到一個(gè)隊(duì)列中（按第k

個(gè)排序碼排序），收集是得到這一趟的排序結(jié)果。例如,

對(duì)剛才圖9-11的初始排序碼，分配和收集過程見圖9-12。

A123―>-78—>65—>9—108—>7—>8—>3—>^68->309

(a)初始狀態(tài)

e[0]e[l]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]

68

3309

1Q8A

657

1237S9

f[0]f[l]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]

(b)第一趟分配(按個(gè)位,有十個(gè)隊(duì)歹U)

>123=￡5>7_