數(shù)據(jù)結(jié)構(gòu)第十章內(nèi)部排序

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

概

述

插

入

■一??

/?

、-

快

速?

一B

，

Mian

選

擇u

J.

Jd

L

wnU

歸

并M

4U

J1

，

nU

、

小

結(jié)

概述

■排座：將一組雜亂無(wú)章的記錄按一定的

規(guī)律順友排列施來(lái)。

?關(guān)鍵字（的0：通常數(shù)據(jù)記錄有多個(gè)屬性

域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)

屬性域可用來(lái)區(qū)分記錄，作為排序依據(jù)。

該域即為關(guān)鍵字。

■主關(guān)鍵字:如果在待排序記錄序列中各個(gè)記錄的

關(guān)鍵字互不相同，這種關(guān)鍵字即主關(guān)鍵字。按照

主關(guān)鍵字進(jìn)行排序，排序的結(jié)果是唯一的。

■次關(guān)鍵字:待排序記錄序列中有些記錄的關(guān)鍵字

可能相同，這種關(guān)鍵字稱(chēng)為次關(guān)鍵字。按照次關(guān)

鍵字進(jìn)行排序，排序的結(jié)果可能不唯一。

■排序算法的穩(wěn)定性:如果在記錄序列中有兩個(gè)

記錄A團(tuán)和A*它們的關(guān)鍵字即］==即］,且在排序

之前，記錄Km排在A團(tuán)前面。如果在排序之后，記

錄即］仍在記錄與的前面，則稱(chēng)這個(gè)排序方法是穩(wěn)

定的，否則稱(chēng)這個(gè)排序方法是不穩(wěn)定的。

■內(nèi)排序與外排序:內(nèi)排序是指在排序期間數(shù)據(jù)記錄

全部存放在內(nèi)存的排序；外排序是指在排序期間全部

記錄個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序

過(guò)程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。

■排序的時(shí)間開(kāi)銷(xiāo):排序的時(shí)間開(kāi)銷(xiāo)是衡量算法好壞

的最重要的標(biāo)志。排序的時(shí)間開(kāi)銷(xiāo)可用算法執(zhí)行中的

記錄比較次數(shù)與記錄移動(dòng)次數(shù)來(lái)衡量。各節(jié)給出算法

運(yùn)行時(shí)間代價(jià)的大略估算一般都按平均情況進(jìn)行估算。

對(duì)于那些受記錄關(guān)鍵字序列初始排列及記錄個(gè)數(shù)影響

較大的，需要按最好情況和最壞情況進(jìn)行估算。

■算法執(zhí)行時(shí)所需的附加存儲(chǔ):評(píng)價(jià)算法好壞的

另一標(biāo)準(zhǔn)。

■待排序記錄的存儲(chǔ)方式：

?以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，排序時(shí)必須實(shí)

際移動(dòng)記錄；

?以鏈表（動(dòng)態(tài)鏈表或靜態(tài)鏈表）作為存儲(chǔ)結(jié)

構(gòu)，排序時(shí)不用物理移動(dòng)記錄，只需修改

指針；

?有的排序方法難于在鏈表上實(shí)現(xiàn)，且需要

避免排序過(guò)程中的記錄移動(dòng)，可將待排序

記錄本身存儲(chǔ)在一組地址連續(xù)的存儲(chǔ)單元

內(nèi)，同時(shí)附設(shè)一個(gè)指示記錄存儲(chǔ)位置的地

址向量，排序過(guò)程中不移動(dòng)記錄，而移動(dòng)

地址向量中這些記錄的地址。

待排序記錄的數(shù)據(jù)類(lèi)型說(shuō)明:

#defineMAXSIZE20

typedefintKeyType;

typedefstruct{

KeyTypekey;

InfoTypeotherinfo;

};

typedefstruct{

RedTyper[MAXSIZE];

intlength;

};

插入排序(InsertSorting)

基本方法：每步將一個(gè)待排序的記錄，按其

關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組

記錄的適當(dāng)位置上，直到記錄全部插入為止。

直接插入排序(InsertSort)

■直接插入排序的基本思想是：當(dāng)插入第4的1)個(gè)

記錄時(shí)，前面的R[l],R[2],…,已經(jīng)排好序。

這時(shí)，用R[i]的關(guān)鍵字與R[i?l],R[R2b…的關(guān)鍵字

順序進(jìn)行比較，找到插入位置即將R7]插入，原來(lái)

位置上的記錄向后順移。

456

OUH25*

123

5國(guó)?即

123

6

123

完成

123456

i=5時(shí)的排序過(guò)程

123456temp

123456temp

456

12-------3?456temp

-1----2--?3456temp

對(duì)順序表直接插入排序的算法：

voidInsertSort(SqList&L){

inti,j;

for(i=2;i<=L.length;++i)

if(L.r[i].key<L.r[i-l].key)需將工明插入有序子表

(

L.r[0]=L.r[i];〃復(fù)制為哨兵

L.r[i]=L.r[i-1];

for(j=i-2;L.r[O].key<L.r[j].key;-j)

L.r[j+l]=L.r[j];//記錄后移

L.r[j+l]=L.r[0];//插入到正確位置

說(shuō)明：監(jiān)視哨L.r[O]的作用：

-保存記錄L.r[i]的副本；

-監(jiān)視下標(biāo)j是否越界，自動(dòng)控制循環(huán)

結(jié)束

算法分析：

-直接插入排序的算法簡(jiǎn)潔，容易實(shí)現(xiàn)。從時(shí)間來(lái)

看，排序的基本操作為：比較兩個(gè)記錄的大小和

移動(dòng)記錄。其中：

?最小比較次數(shù)：Cmin=n-1=O(n)

?最大比較次數(shù)：Cmax=(2+3+...+n)=(n+2)(n-l)/2=O(n2)

?最小移動(dòng)次數(shù)：Mmin=0

.最大移動(dòng)次數(shù):Mmax=(2+1+3+1+.??+n+l)=O(n2)

■若待排序記錄序列中出現(xiàn)各種可能排列的概率相

同，則可取上述最好情況和最壞情況的平均情況。

在平均情況下的關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)

約為刀2/4。因此，直接插入排序的時(shí)間復(fù)雜度為

2

o(n)o

-關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)與記

錄關(guān)鍵字的初始排列有關(guān)。

■從空間看，直接插入排序算法只需一

個(gè)記錄的輔助空間。

■直接插入排序是一種穩(wěn)定的排序方法。

折半插入排序(BinaryInsertsort)

■基本思想：

-設(shè)在順序表中有一個(gè)記錄序列R[l],

R[2],R[n]o其中，R[1],R[2],R[i-

1]是已經(jīng)排好序的記錄。

-在插入R團(tuán)時(shí)，利用折半搜索法尋找

R國(guó)的插入位置。

■折半插入排序的算法:

voidBInsertSort(SqList&L){

inti,j,m,low,high;

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

L.r[O]=L.r[iJ;//將L.r[i]暫存到L.r[0]

low=l;

high=i-l;

while(low<=high){//在r[low..high]中折半查找有序插入的位置

m=(low+high)/2;〃折半

if(L.r[O].key<L.r[m].key)

high=m-1;//癌人點(diǎn)在低半?yún)^(qū)

else

low=m+1;//插入點(diǎn)在高半?yún)^(qū)

}

for(j=i-l;j>=high+l;-j)

L.r[j+l]=L.r[j];//記泉后移

L.r[high+l]=L.r[O];//插入

算法分析:

■折半插入排序所需要的關(guān)鍵字比較次數(shù)與待排序

記錄序列的初始排列無(wú)關(guān)，僅依賴(lài)于記錄個(gè)數(shù)。

在插入第i個(gè)記錄時(shí)，需要經(jīng)過(guò)次關(guān)鍵

字比較，才能確定它應(yīng)插入的位置。將〃個(gè)記錄

用折半插入排序所進(jìn)行的關(guān)鍵字比較次數(shù)為

O(nlog2n).

■折半插入排序的時(shí)間復(fù)雜度仍為O(IP)

■當(dāng)〃較大時(shí)，總的關(guān)鍵字比較次數(shù)比直接插入排

序的最壞情況要好得多，但比其最好情況要差。

■在記錄的初始排列已經(jīng)按關(guān)鍵字排好序或接近有

序時(shí)，直接插入排序比折半插入排序執(zhí)行的關(guān)鍵

字比較次數(shù)要少。折半插入排序的記錄移動(dòng)次數(shù)

與直接插入排序相同，依賴(lài)于記錄的初始排列。

■折半插入排序是一個(gè)穩(wěn)定的排序方法。

希爾排序(ShellSort)

■從對(duì)直接插入排序的分析可知，其時(shí)間復(fù)雜度為

O(n2),但是當(dāng)待排序記錄處于“基本有序”狀態(tài)

或當(dāng)n值較小時(shí)，直接插入排序的效率可大大提高。

Shell排序方法正是基于這兩點(diǎn)考慮對(duì)直接插入排

序加以改進(jìn)而提出的一種插入排序算法。

■Shell排序方法是一種“逐漸縮小插入間隔”的插

入排序方法，在時(shí)間效率上較直接插入排序有較

大的改進(jìn)。

Shell排序的基本做法:

先確定一個(gè)小于n的整數(shù)4作為第一個(gè)增量，把

記錄序列分為由個(gè)組，所有距離為由倍數(shù)的記錄

放在同一個(gè)組中，在各組內(nèi)進(jìn)行直接插入排序；

■然后，取第二個(gè)增量d2((I2<4),重復(fù)上述分

組和排序，直至所取的增量4=1(dtVdyV…Vd2V

由)，即所有記錄處在同一組中進(jìn)行直接插入排序

為止。

ZD

B

z

■開(kāi)始時(shí)增量值較大，子序列中的記錄較

少，排序速度就快；隨著排序進(jìn)展，增

量值逐漸變小，子序列中記錄個(gè)數(shù)逐漸

變多，由于前面工作的基礎(chǔ)，大多數(shù)記

錄已基本有序，所以排序速度仍然很快。

希爾排序的算法:

voidShelllnsert(SqList&L,intdk){

for(i=dk+l;i<=L.Length;i++)

if(L.r[i].key<L.r[i-dk].key){//需將L.r川插入有序增量子表

L.r[0]=L.r[i];//暫存在L.r[0],但不是哨兵。

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

L.r[j+dk]=L.r[j];〃記錄后移，查找插入位置

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

}

}

voidShellSort(SqList&L,intdlta[]9intt){

〃按增量序列對(duì)順序袤L作希爾排序

for(k=0;k<t;t++){

Shelllnsert(L,dltafk]);//一趟增量為dlta[k]的插入排序

■奢量的取法有多種。最初shell提出取心=

,d2=Ldx/2j,直到dt=L后來(lái)knuth

提出取4+1=Ldi/3J+1o還有人提出都取奇

數(shù)為好，也有人提出各磨量互質(zhì)為好。

算法分析：

對(duì)特定的待排序記錄序列，可以準(zhǔn)確地估算

關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù)。

但想要弄清關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)

與增量選擇之間的依賴(lài)關(guān)系，并給出完整的

數(shù)學(xué)分析，還沒(méi)有人能夠做到。

快速排序(ExchangeSort)

基本思想：是兩兩比較待排序記錄的關(guān)鍵字，如

果發(fā)生逆序(即排列順序與排序后的次序正好相反),

則交換之，直到所有記錄都排好序?yàn)橹埂?/p>

起泡排序(BubbleSort)

基本方法：比較相鄰兩個(gè)記錄的關(guān)鍵字，若

R[i].key>R[i+l].key,則交換之，其中i從0到n-

pass-1(pass的初值為1)春之為一趟起泡排序，其

結(jié)果是使最大關(guān)鍵字的記錄被交換到n-pass的位置

上，如果某一趟起泡排序過(guò)程中沒(méi)有進(jìn)行一次記錄

的交換，則排序過(guò)程結(jié)束。最壞情況下需n-l趟排序。

IIII

zzz

/=4

a81noSwap=0

012345

起泡排序的算法：

voidBubbleSort(SqList&L){

〃從下往上掃描的起泡排序

for(i=0;i<n-2;i++){//做n-l趟排序

noSwap=TRUE;//置未交換標(biāo)志

for(j=n-l;j>=i;j-)〃從下往上掃描

if(L.r[j+l].key<L.r[j].key)

(

temp=L.r[j+l];〃交換記錄

L.r[j+l]=L.r[j];

L.r[j]=temp;

noSwap=FALSE;

}

if(noSwap)break;〃本趟掃描未發(fā)生交換，則終止算法

}

算法分析：

在記錄的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí)，此算法只

執(zhí)行一趟起泡，做次關(guān)鍵字比較，不移動(dòng)記錄。這是最好

的情形。

■最壞的情形是算法執(zhí)行了1趟起泡，第，趟

做了〃-i次關(guān)鍵字比較，執(zhí)行了〃T次記錄交換。這

樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和記錄移

動(dòng)次數(shù)AMN為：

〃一11

KCN=>(〃_，)=-n(n—1)

-2

n-1

RMN=3V(〃—2)=一〃(〃一1)

-2

■起泡排序需要一個(gè)附加記錄以實(shí)現(xiàn)記錄值的對(duì)換。

■起泡排序是一個(gè)穩(wěn)定的排序方法。

快速排序（QuickSort）

■基本思想：

-是任取待排序記錄序列中的某個(gè)記錄（例如取第一個(gè)

記錄）作為，按照該記錄的關(guān)鍵字大小，將整個(gè)

記錄序列劃分為左右兩個(gè)子序列：

?左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于基準(zhǔn)記錄的關(guān)

鍵字

?右側(cè)子序列中所有記錄的關(guān)鍵字都大于或等于基準(zhǔn)記錄的關(guān)

鍵字

-基準(zhǔn)記錄則排在這兩個(gè)子序列中間（這也是該記錄最終

應(yīng)安放的位置）。

-然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所

有的記錄都排在相應(yīng)位置上為止。

pivot

456

pivot

<--

--------------/

82卜

pivot

25*49

825*a

算法描述:

一趟劃分算法：

intPartition(SqList&L,intlow,inthigh){

L.r[O]=L.r[low];〃用子表的第一個(gè)記錄作基準(zhǔn)記錄

pivotkey=L.r[low].key;〃基準(zhǔn)記錄關(guān)鍵字

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[high]=L.r[low];

L.r[low]=L.r[OJ;//基準(zhǔn)記錄到位

returnlow;〃返回樞軸位置

voidQSort(SqList&L,intlow,inthigh)

intpivotloc;

if(low<high)

(〃長(zhǎng)度大于1

pivotloc=Partition(L,low,high);

QSort(L,low9pivotloc-l);//對(duì)低子表遞歸排序

QSort(L,pivotloc+l,high);//對(duì)高子表遞歸排序

算法夕〃無(wú)依是一個(gè)遞歸的算法，其

遞歸樹(shù)如圖所示。

/算法利用序列第一個(gè)記錄作為基準(zhǔn)，將整

個(gè)序列劃分為左右兩個(gè)子序列。算法中執(zhí)行了一個(gè)循

.'上W是關(guān)鍵字小于基準(zhǔn)記錄夾鍵字而記親都.到

序列左側(cè)，最后基準(zhǔn)記錄安放到彳立，函盛返回其位置

算法分析：

■從快速排序算法的遞歸樹(shù)可知，快速排序的趟數(shù)

取決于遞歸樹(shù)的深度。

■如果每次劃分對(duì)基準(zhǔn)記錄定位后，該記錄的左側(cè)

子序列與右側(cè)子序列的長(zhǎng)度相同，則下一步將是

對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序，這是最理想

的情況。

■在"個(gè)元素的序列中，對(duì)一個(gè)記錄定位所需時(shí)間

為05）。若設(shè)T.）是對(duì)黃個(gè)元素的序列進(jìn)行排

序所需的時(shí)間，而且每次對(duì)一個(gè)記錄正確定位后,

正好把序列劃分為長(zhǎng)度相等的兩個(gè)子序列，此時(shí),

總的計(jì)算時(shí)間為：

T(w)<n+2T(n/2)〃一趟劃分比較次數(shù)為n-1

次

<n+2(n/2+2T(n/4))=2n+4T(n/4)

<2n+4(H/4+2T(〃/8))=3/I+8T(n/8)

<nIog2/i+MT(1)=O(nlog2n)

■可以證明，函數(shù)夕〃ic依at的平均計(jì)算時(shí)間也

是0(〃10g2〃)。實(shí)息結(jié)果表明：就平均計(jì)算時(shí)

間而言，快速排序是我們所討論的所有內(nèi)排

序方法中最好的一個(gè)。

■最壞的情況下：

-即待排序記錄序列已經(jīng)按其關(guān)鍵字從小

到大排好序的情況下，其遞歸樹(shù)成為單

支樹(shù)，每次劃分只得到一個(gè)比上一次少

一個(gè)記錄的子序列。這樣，必須經(jīng)過(guò)〃

趟才能把所有記錄定位，而且第，趟需

要經(jīng)過(guò)n?i次關(guān)鍵字比較才能找到第i個(gè)

記錄的安放位置，總的關(guān)鍵字比較次數(shù)

將達(dá)到：

n-1.1n2

V(n-z)=-n(n-1)?----

一22

■其排序速度退化到簡(jiǎn)單排序的水平，比直接插入

排序還慢。

■若能更合理地選擇基準(zhǔn)記錄，使得每次劃分所得

的兩個(gè)子序列中的記錄個(gè)數(shù)盡可能地接近，可以

加速排序速度，但是由于記錄的初始排列次序是

隨機(jī)的，這個(gè)要求很難辦到。

■有一種改進(jìn)辦法：取每個(gè)待排序記錄序列的第一

個(gè)記錄、最后一個(gè)記錄和位置接近正中的3個(gè)記錄,

取其關(guān)鍵字居中者作為基準(zhǔn)記錄。

012345pivot

初始0816；212S：：25*4少121

i=1

i=2f

III-f'...^r-I^r—L^E__^HE.’

用居中關(guān)鍵字記錄作為基準(zhǔn)記錄

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

對(duì)于n較大的平均情況而言，快速排序是“

快速”的，但是當(dāng)m很小時(shí)，這種排序方法

往往比其它簡(jiǎn)單排序方法還要慢。

選擇排序

基本思想：每一趟(例如第i趟,力=1,2,…,〃-1)在

后面n-i+1個(gè)待排序記錄中選出關(guān)鍵字最小的記錄，

作為有序記錄序列的第，個(gè)記錄。待到第〃T趟作完

，待排序記錄只剩下1個(gè)，就不用再選了。

簡(jiǎn)單選擇排序(SelectSort)

■首先在所有記錄中選出關(guān)鍵字最小的記錄,

把它與第1個(gè)記錄交換，然后在其余的記錄中

再選出關(guān)鍵字次最小的記錄與第2個(gè)記錄交換,

以次類(lèi)推……，直到所有記錄排序完成。

iz導(dǎo)、。皙

91sz誨*

91導(dǎo)、r＞皙

804RW^?四

80導(dǎo)W皙

￡

8T|￥

最小者25*

無(wú)交換

012345

最小者25

無(wú)交換

25*49

各趟排序后的結(jié)果

i=1時(shí)選擇排序的過(guò)程

012345

//I>49>25

I;25*>25

/k^j16<25

49

2525*1621

012345

|,21>16

立指不當(dāng)前序列中最小者

簡(jiǎn)單選擇排序的算法:

voidSelectSort(SqList&L){

intij;

RedTypetemp;

for(i=0;i<L.length-l;i++){//做n-1趟選擇排序

k=j.

〃在&前無(wú)序區(qū)選關(guān)鍵字最小的記錄

for(j=i+l;j<L.length;j++)

if(L.r[j].key<L.r[k].key)k=j;

if(k!=i){

temp=L.r[i];

L.r[i]=L.r[k];

L.r[k]=temp;

}

}

算法分析:

簡(jiǎn)單選擇排序的關(guān)鍵字比較次數(shù)KCN與記錄

的初始排列無(wú)關(guān)。第，趟選擇具有最小關(guān)鍵

字記錄所需的比較次數(shù)總是〃T次，此處假

定整個(gè)待排序記錄序列有〃個(gè)記錄。因此，

總的關(guān)鍵字比較次數(shù)為：

n—2n(n—1)

KCN=Z(〃_=

z=o2

■記錄的移動(dòng)次數(shù)與記錄序列的初始排列有

關(guān)。當(dāng)這組記錄的初始狀態(tài)是按其關(guān)鍵字

從小到大有序的時(shí)候，記錄的移動(dòng)次數(shù)

RMN=O,達(dá)到最少。

■最壞情況是每一趟都要進(jìn)行交換，總的記

錄移動(dòng)次數(shù)為AMN=3(〃T)。

■簡(jiǎn)單選擇排序總的時(shí)間復(fù)雜度是O(M)

■簡(jiǎn)單選擇排序是一種不穩(wěn)定的排序方法。

堆排序（HeapSort）

堆著二個(gè)關(guān)鍵字序列｛k29…,kn｝，它具有如下特性：

ki<k2i或kj2k2i

及Wkzi+ikj2kzi+i（i=1,2,…，LD/2」）

堆的特性在完全二叉樹(shù)中解釋為：完全二叉樹(shù)中任一結(jié)點(diǎn)的

關(guān)鍵字都小于等于（或大于等于）它的左、右孩子的關(guān)鍵字

O

如下列關(guān)鍵字序列均是堆：

｛5,23,16,68,94,72,71,73｝（小頂堆）

｛96,83,27,38,11,9｝（大頂堆）

由堆定義可知：若關(guān)鍵字序列｛3,k2,…，凡｝是堆，則堆頂元

素是n個(gè)元素序列中的最?。ㄗ畲螅┰亍?/p>

■堆排序基本思想：

首先將初始待排序記錄序列建堆，則堆頂元素

必為含最大關(guān)鍵字或最小關(guān)鍵字的記錄，輸出該

記錄，然后將剩余記錄再調(diào)整為堆，如此反復(fù)，

直至排序結(jié)束。

在堆排序主要需解決兩個(gè)問(wèn)題：

①如何建堆？

在完全二叉樹(shù)中，所有序號(hào)i>Ln/2」的結(jié)點(diǎn)都是葉子，

因此，以這些結(jié)點(diǎn)為根的子樹(shù)均已是堆，這樣只需將以

序號(hào)為L(zhǎng)n/2」,Ln/2J-1,Ln/2J-2,…，1的結(jié)點(diǎn)為根的子樹(shù)都調(diào)

整為堆即可。在按此次序調(diào)整每個(gè)結(jié)點(diǎn)時(shí)，其左、右子

樹(shù)均已是堆。

②若K的左、右子樹(shù)已經(jīng)是堆，如何將以K為根的

完全二叉樹(shù)也調(diào)整為堆？

因,的左、右子樹(shù)已經(jīng)是堆，所以必須在&和

它的左、右孩子中選出最?。ɑ蜃畲螅┑慕Y(jié)點(diǎn)放

到I的位置上，不妨設(shè)k2i關(guān)鍵字最小，將I與k2i

交換位置，而交換之后有可能導(dǎo)致以kzi為根的子

樹(shù)不再為堆，于是可重復(fù)上述過(guò)程，將以1＜方為根

的子樹(shù)調(diào)整為堆，……，如此逐層下去，最多可

能一直調(diào)整到樹(shù)葉，此方法稱(chēng)為“篩選法”。

例子：關(guān)鍵字序列為42，13,91，23，24,

16,05,故從第四個(gè)結(jié)點(diǎn)開(kāi)始調(diào)

整

4213912324160588

不調(diào)整

co

建成的堆

調(diào)整算法：

//已知H.r[s.?m]中記錄的關(guān)鍵字除H.r[s].key之外均滿(mǎn)足堆

的定義，本算法調(diào)整H.r[s]的關(guān)鍵字，使H.r[s..m]成為一個(gè)

大頂堆.

typedefSqListHeapType;

voidHeapAdjust(HeapType&H,ints,intm){

RedTyperc;

rc=H.r[s];

for(j=2*s;jv=m;j*=2){//沿key較大的孩子結(jié)點(diǎn)向下篩選

if(j〈m&&H,r[j].key<H.r[j+l].key)j++;

if(rc.key>=H.r[j].key)break;//rc應(yīng)插入在位置s上

H.r[s]=H.r[j];

H.r[s]=rc;

上述算法只是對(duì)一個(gè)指定的結(jié)點(diǎn)進(jìn)行調(diào)整。

有了這個(gè)算法，則將初始的無(wú)序區(qū)R[l]到R[n]

建成一個(gè)大根堆，可用以下語(yǔ)句實(shí)現(xiàn)：

for(i=n/2;i>=1;i?)

HeapAdjust(H,i,H.length)

基于初始堆進(jìn)行堆排序

■大頂堆的第一個(gè)記錄R[l]具有最大的關(guān)鍵字,

將R[l]與R同對(duì)調(diào)，把具有最大關(guān)鍵字的記

錄交換到最后，再對(duì)前面的個(gè)記錄，使

用堆的調(diào)整算法HeapAdjust(H,1,w-l),重

新建立大頂堆。結(jié)果具有次最大關(guān)鍵字的記

錄又上浮到堆頂，即R[l]位置。

■再對(duì)調(diào)R[l]和調(diào)用HeapAdjust(H,l,

2),對(duì)前"-2個(gè)記錄重新調(diào)整，…。

■如此反復(fù)執(zhí)行，最后得到全部排序好的記錄

序列。這個(gè)算法即堆排序算法。

13

9188422324160513

(a)初始堆R[l]到R⑻

(b)第一趟排序之后

(c)重建的堆R⑴到R[7]

(d)第二趟排序之后

(e)重建的堆R⑴到R[6]

(f)第三趟排序之后

(g)重建的堆R⑴到R⑸

(h)第四趟排序之后

,05244288

/

2313160524428891

(i)重建的堆R⑴到R⑷

「5、

/,13、、/16、、

/\/\

,23244288

0513162324428891

(j)第五趟排序之后

(k)重建的堆R[l]到R[3]

「5、

/,13、、/16、、

/\/\

,23244288

0513162324428891

(1)第六趟排序之后

13"

,23244288

1305162324428891

(m)重建的堆R[l]到R⑵

s

、、、

、、、

—'、、、

、、、、

/,13、、/16、、

/\/\

,23244288

0513162324428891

(n)第七趟排序之后

堆排序的算法:

voidHeapSort(HeapType&H){

RedTypetemp;

inti;

for(i=H.length/2;i>0;i—)//把建成大頂堆

HeapAdjust(H,i,H.length);

for(i=H.length;i>l;i—){

temp=H.r[l];

H.r[l]=H.r[i];

H.r[i]=temp;

HeapAdjust(H,1,i-1);〃將重新調(diào)整為大頂堆

}

算法分析:

■堆排序的時(shí)間主要由建立初始堆和不斷重復(fù)調(diào)整

堆這兩部分的時(shí)間開(kāi)銷(xiāo)構(gòu)成。

■若設(shè)堆中有〃個(gè)結(jié)點(diǎn)，且2-4〃<23則對(duì)應(yīng)的

完全二叉樹(shù)有4層。在第i層上的結(jié)點(diǎn)數(shù)V2叔(，

=1,2,…,A)。在第一個(gè)建立初始堆的for循環(huán)中對(duì)

每一個(gè)非葉結(jié)點(diǎn)調(diào)用了一次堆調(diào)整算法

HeapAdjust。,因此該循環(huán)所用的計(jì)算時(shí)間為：

1

S"(A-/)

i=k—\

■其中，，是層序號(hào)，2閆是第，層的最大結(jié)點(diǎn)數(shù)，

(AT)是第，層結(jié)點(diǎn)能夠移動(dòng)的最大距離。

■堆排序過(guò)程中進(jìn)行n-l次重建堆所進(jìn)行的總比較次數(shù)

不超過(guò)下式：

2*(Llog2(n-1)J+Llog2(n-2)J+...+Llog22j)<2nLlog2nJ

=0(nlog2n)

■因此堆排序總的時(shí)間復(fù)雜度是0(n+nlogzn)=

0(nlog2n)o

■堆排序在最壞情況下的時(shí)間復(fù)雜度也是0(nlog2n),

相對(duì)于快速排序來(lái)說(shuō)，這是堆排序的最大優(yōu)點(diǎn)。

■堆排序是一個(gè)不穩(wěn)定的排序方法。

歸并排序(MergeSort)

■歸并排序是利用“歸并”技術(shù)來(lái)進(jìn)行排序，所謂

歸并是指將兩個(gè)有序的序列合并形成一個(gè)新的有序

序列。

■將待排序記錄序列R1，R2,…,Rn看成為n個(gè)長(zhǎng)度為I

的有序子序列，把這些子序列兩兩進(jìn)行歸并，便得

到廠n/21個(gè)長(zhǎng)度為2的有序子序列，然后再兩兩歸

并，……，如此重復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的

有序記錄序列為止，這種方法成為二路歸并方法。

歸并排序過(guò)程

len=l

2125254962930872163754/en=2

???????

???????

2125254908627293163754len=4

????

???

????

?.?

0821252549627293163754len=8

■M

0816212525374954627293len=16

歸并算法：

〃將有序的SR[i??m]和SR[m+L.n]歸并為有序的TR[i??n]算法

voidMerge(RedTypeSR[],RedTypeTR[],inti,intm,intn){

intj,k,1;

for(j=m+l,k=i;i<=m&&j<=n;++k)

if(SR[i].key<=SR[j].key)

TR[k]=SR[i++];

else

TR[k]=SR[j++];

if(i<=m)

for(1=0;l<=m-i;1++)

TR[k+l]=SR[i+l];〃將剩余的SR[i?.m]復(fù)制到TR

if(j<=n)

for(1=0;l<=n-j;1++)

TR[k+l]=SR[j+l];〃將乘U余的SR[j..n]復(fù)制至UTR

一趟歸并算法：

voidMergePass(RedTypeR[],RedTypeRI[],intlength)

{inti,j;

i=0;

while(i+2*length-l<n)

{MERGE(R,RI,i,i+length-1,i+2*lengthT);

i=i+2*length;

)

if(i+length-l<n-l)

MERGE(R,RI,i,i+length-1,n-1);

else

for(j=i;j<n;j++)Rl[j]=R[j];

歸并排序算法：

voidMergeSort(RedTypeR[]){

intlength=l;

while(length<n){

MERGEPASS(R,RI,length);

length=2*length;

MERGEPASS(RI,R,length);

length=2*length;

遞歸的歸并排序算法：

voidMSort(RedTypeSR[],RedTypeTR1[],int