數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序

第10章內(nèi)排序數(shù)據(jù)結(jié)構(gòu)主講教師：祝建華數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第1頁。210.1概述1.排序：將文件或表中的記錄，通過某種方法整理成按關(guān)鍵字大小次序排列的處理過程。假定n個(gè)記錄的文件為

(R1,R2,...,Rn)

對應(yīng)的關(guān)鍵字為

(K1,K2,...,Kn)

則排序是確定如下一個(gè)排列

p1,p2,...,pn

使得:Kp1≤Kp2≤...≤Kpn

從而得到一個(gè)有序文件

(Rp1,Rp2,...Rpn)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第2頁。320051劉大海807520042王偉908320066吳曉英828820038劉偉807020052王洋607012345學(xué)

號

姓

名

數(shù)學(xué)

外語20038劉偉807020042王偉908320051劉大海807520052王洋607020066吳曉英8288學(xué)

號

姓

名

數(shù)學(xué)

外語20052王洋607020051劉大海807520038劉偉807020066吳曉英828820042王偉908320042王偉908317320066吳曉英828817020051劉大海807515520038劉偉807015020052王洋607013012345學(xué)

號

姓

名

數(shù)學(xué)

外語學(xué)

號

姓

名

數(shù)學(xué)

外語總分1234512345(a)無序表(b)按學(xué)號排列的有序表(c)按數(shù)學(xué)成績排列的有序表(d)按總分成績排列的有序表學(xué)生成績表數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第3頁。4穩(wěn)定的排序不穩(wěn)定的排序20051劉大海807520042王偉908320066吳曉英828820038劉偉807020052王洋607012345學(xué)

號

姓

名

數(shù)學(xué)

外語20052王洋607020038劉偉807020051劉大海807520066吳曉英828820042王偉9083學(xué)

號

姓

名

數(shù)學(xué)

外語12345(e)按數(shù)學(xué)成績排列的有序表不穩(wěn)定的排序2.什么是排序的穩(wěn)定性假設(shè)在待排序的文件中，存在兩個(gè)具有相同關(guān)鍵字的記錄R(i)與R(j),其中R(i)位于R(j)之前。在用某種排序法排序之后,R(i)仍位于R(j)之前，則稱這種排序方法是穩(wěn)定的；否則，稱這種排序方法是不穩(wěn)定的。例數(shù)列(10,25,22,42,25,30,18)(10,18,22,25,25,30,42)(10,25,22,42,25,30,18)(10,18,22,25,25,30,42)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第4頁。53.內(nèi)部排序(內(nèi)排序)----在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序外部排序(外排序)----借助計(jì)算機(jī)外存進(jìn)行的排序4.待排序的記錄和順序表(文件)的數(shù)據(jù)類型

#defineMAXSIZE20//最大長度

typedefintKeyType；//關(guān)鍵字類型

typedefstruct//記錄類型

{KeyTypekey；//關(guān)鍵字

InfoTypeotherinfo；//其它數(shù)據(jù)類型

}RecType；//記錄類型名數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第5頁。6typedefstruct{RecTyper[MAXSIZE+1]；//r[0]用作監(jiān)視哨

intlength;//實(shí)際表長

}SeqList；//記錄表類型或表和表長分別定義和說明

RecTyper[MAXSIZE+1]；//r[0]用作監(jiān)視哨

intlength；//實(shí)際表長

length≤MAXSIZE數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第6頁。75.排序算法分析(1)時(shí)間復(fù)雜度對n個(gè)記錄排序，所需比較關(guān)鍵字的次數(shù)；最好情況；最壞情況；平均情況對n個(gè)記錄排序，所需移動記錄的次數(shù)；最好情況；最壞情況；平均情況(2)空間復(fù)雜度排序過程中，除文件中的記錄所占的空間外，所需的輔助存儲空間的大小。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第7頁。86.內(nèi)排序方法(1)對順序表的排序插入排序：

直接插入排序；折半插入排序；

2-路插入排序；表插入排序；希爾(Shell)排序；

交換排序:

冒泡排序：單向冒泡排序，雙向冒泡排序

快速排序選擇排序：簡單選擇/選擇排序；樹形選擇排序；

堆排序數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第8頁。9

歸并排序:2-路歸并排序

k-路歸并排序基數(shù)排序:

多關(guān)鍵字排序最高位優(yōu)先法最低位優(yōu)先法鏈?zhǔn)交鶖?shù)排序(2)對單鏈表的排序:

直接插入,簡單選擇,冒泡排序,基數(shù)排序數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第9頁。1010.2插入排序算法基本思想將待排序的記錄插入到已排序的子文件中去，使得插入之后得到的子文件仍然是有序子文件。插入一個(gè)記錄，首先要對有序子文件進(jìn)行查找，以確定這個(gè)記錄的插入位置。按查找方式的不同，插入排序又可以分為線性插入排序和折半插入排序，前者使用順序查找，后者使用折半查找。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第10頁。111.直接插入排序(線性插入排序)

設(shè)待排序的文件為：(r[1],r[2],...,r[n])

關(guān)鍵字為：(r[1].key,r[2].key,...,r[n].key)

首先,將初始文件中的記錄r[1]看作有序子文件；第1遍：將r[2]插入有序子文件中，若：

r[2].key<r[1].key，則r[2]插在r[1]之前；否則，插在r[1]的后面。第2遍：將記錄r[3]插入前面已有2個(gè)記錄的有序子文件中，得到3個(gè)記錄的有序子文件。以此類推，依次插入r[4],...,r[n],最后得到n個(gè)記錄的遞增有序文件。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第11頁。12例.直接插入排序,設(shè)K0為"監(jiān)視哨”

K0K1K2K3K4K5K6初始關(guān)鍵字：(43)2189154328第1遍排序后：21(2143)89154328(43后移)第2遍排序后：89(214389)154328(不后移)第3遍排序后：15(15214389)4328(89,43,21后移)第4遍排序后：43(152143

4389)28(89后移)第5遍排序后：28(15212843

4389)(89,43,43后移)2189154328數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第12頁。13直接插入排序算法（對數(shù)組r[1..n]中的n個(gè)記錄作插入排序）voidInsertSort(RecTyper[],intn）{inti,j；

for(i=2；i<=n；i++){r[0]=r[i]；//待插記錄r[i]存入監(jiān)視哨中

j=i-1；//已排序的范圍1－i-1//從r[i-1]開始向左掃描

while(r[0].key<r[j].key){r[j+1]=r[j]；//記錄后移

j--；//繼續(xù)向左掃描

}r[j+1]=r[0]；//插入記錄r[0],即原r[i]}}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第13頁。14rir1r2………ri-1ri…rnr[0]r[1]r[2]r[i-1]r[i]r[n]直接插入排序算法分析：(1)最好情況，原n個(gè)記錄遞增有序：比較關(guān)鍵字n-1次移動記錄2(n-1)次,(將數(shù)據(jù)復(fù)制到r[0]后又復(fù)制回來）數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第14頁。15rir1r2………ri-1ri…rnr[0]r[1]r[2]r[i-1]r[i]r[n]rir1’r2’………ri-1’ri…rnr[0]r[1]r[2]r[i-1]r[i]r[n](2)最壞情況，原n個(gè)記錄遞減有序：比較關(guān)鍵字的次數(shù):n

∑i=2+3+...+n=(n-1)(n+2)/2=O(n2)i=2

移動記錄的次數(shù)(個(gè)數(shù)):n

∑(i-1+2)=3+4+...+(n+1)i=2=(n-1)(n+4)/2次=O(n2)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第15頁。16平均移動記錄的次數(shù)約為:(3)平均比較關(guān)鍵字的次數(shù)約為:故,時(shí)間復(fù)雜度為O(n2)。

(4)只需少量中間變量作為輔助空間。

(5)算法是穩(wěn)定的。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第16頁。172.折半插入排序（對數(shù)組r[1..n]中的n個(gè)記錄作折半插入排序）voidBInsertSort(RecTyper[],intn）{inti,j；

for(i=2；i<=n；i++){r[0]=r[i]；//待插記錄r[i]存入監(jiān)視哨中

low=1；high=i-1；

while(low<=high){m=(low+high)/2;if(r[0].key<r[m].key)high=m-1；//插入位置可能在high之后

elselow=m+1；//插入位置可能在low之前

}//結(jié)束時(shí)表示插入在high和low之間

for(j=i–1;j>=high+1;--j)r[j+1]=r[j]；

r[high+1]=r[0];}}減少了記錄的比較次數(shù)，記錄的移動次數(shù)不變。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第17頁。1810.3交換排序10.3.1冒泡排序基本思想:

設(shè)待排序的文件為r[1..n]第1趟(遍)：從r[1]開始,依次比較兩個(gè)相鄰記錄的關(guān)鍵字r[i].key和r[i+1].key,若r[i].key>r[i+1].key，則交換記錄r[i]和r[i+1]的位置；否則,不交換。(i=1,2,...n-1)第1趟之后,n個(gè)關(guān)鍵字中最大的記錄移到了r[n]的位置上。第2趟：從r[1]開始,依次比較兩個(gè)相鄰記錄的關(guān)鍵字r[i].key和r[i+1].key,若r[i].key>r[i+1].key，則交換記錄r[i]和r[i+1]的位置；否則,不交換。(i=1,2,...n-2)第2趟之后,前n-1個(gè)關(guān)鍵字中最大的記錄移到了r[n-1]的位置上。

......作完n-1趟,或者不需再交換記錄時(shí)為止。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第18頁。19一般情況：第1遍:10378521496[0—10-1)第2遍：37852149610[0—10-2)第3遍：37521486910[0—10-3)第4遍：35214768

910[0—10-4)第5遍：32145678

910[0—10-5)第6遍：213456

78

910[0—10-6)第7遍：12345

6

78

910[0—10-7)第8遍：1234

5

6

78

910[0—10-8)第9遍：

12345678910[0—10-9)

12

345678910交換范圍數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第19頁。20算法分析:最好情況:待排序的文件已是有序文件，只需要進(jìn)行1趟排序,共計(jì)比較關(guān)鍵字的次數(shù)為

n－1不交換記錄。最壞情況:要經(jīng)過n-1趟排序，所需總的比較關(guān)鍵字的次數(shù)為

(n-1)+(n-2)+...+1＝n(n-1)/2

交換記錄的次數(shù)最多為

(n-1)+(n-2)+...+1＝n(n-1)/2

移動記錄次數(shù)最多為

3n(n-1)/2。只需要少量中間變量作為輔助空間。算法是穩(wěn)定的。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第20頁。21冒泡排序算法(對n個(gè)整數(shù)按遞增次序作冒泡排序)voidbubble1(inta[],intn){inti,j,temp；

for(i=0；i<n-1；i++)//作n-1趟排序

for(j=0；j<n-1-i；j++)if(a[j]>a[j+1]){temp=a[j]；//交換記錄

a[j]=a[j+1]；

a[j+1]=temp；

}for(i=0；i<n；i++)printf("%d",a[i])；//輸出排序后的元素

}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第21頁。22改進(jìn)的冒泡排序算法voidbubblesort(RecTyper[],intn){inti,j,swap；RecTypetemp；

j=1；//置比較的趟數(shù)為1do{swap=0；//置交換標(biāo)志為0for(i=1；i<=n-j；i++){if(r[i].key>r[i+1].key){temp=r[i]；//交換記錄`r[i]=r[i+1]；

r[i+1]=temp；

swap=1；//置交換標(biāo)志為1}j++；//作下一趟排序

}}while(j<n&&swap)；

}//未作完n-1趟,且標(biāo)志為1數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第22頁。2310.3.2快速排序基本思想：首先在r[1..n]中，確定一個(gè)r[i]，經(jīng)過比較和移動，將r[i]放到"中間"某個(gè)位置上，使得r[i]左邊所有記錄的關(guān)鍵字小于等于r[i].key，r[i]右邊所有記錄的關(guān)鍵字大于等于r[i].key。以r[i]為界,將文件劃分為左、右兩個(gè)子文件。用同樣的方法分別對這兩個(gè)子文件進(jìn)行劃分,得到4個(gè)更小的子文件。繼續(xù)進(jìn)行下去,使得每個(gè)子文件只有一個(gè)記錄為止,便得到原文件的有序文件。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第23頁。2420053708631259154408xij08053708631259154408xij2020例.給定文件(20,05,37,08,63,12,59,15,44,08)，選用第1個(gè)元素20進(jìn)行劃分:數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第24頁。2508053708631259154408xij08053708631259154437xij08051508631259154437xijii20jj2020數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第25頁。2608051508631259154437xij08051508631259634437xij08051508121259634437xij2008051508122059634437xij左子文件右子文件20ii20jji20數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第26頁。27voidquksort(RecTyper[],intlow,inthigh){RecTypex；inti,j；

if(low<high)//有兩個(gè)以上記錄

{i=low；j=high；x=r[i]；//保存記錄到變量x中

do{//此時(shí)i指示位置可用

while(i<j&&r[j].key>=x.key)j--；//j從右向左端掃描通過key不小于x.key的元素

if(i<j)//i,j未相遇

{r[i]=r[j]；i++；//此時(shí)j指示位置可用

while(i<j&&r[i].key<=x.key)i++；//i從左向右端掃描通過key不大于x.key的元素

if(i<j){r[j]=r[i]；j--；}}}while(i!=j)；//i,j未相遇

}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第27頁。28//劃分結(jié)束，i經(jīng)過的是key不大于x.key的元素；

j經(jīng)過的是key不小于x.key的元素。

i,j至少有一個(gè)指示的位置可用

r[i]=x；

quksort(r,low,i-1)；//遞歸處理左子文件

quksort(r,i+1,high)；//遞歸處理右子文件

}}對文件r[1..n]快速排序：

voidquicksort(RecTyper[],intn){quksort(r,1,n)；}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第28頁。29算法分析就平均速度而言，快速排序是已知內(nèi)部排序方法中最好的一種排序方法,其時(shí)間復(fù)雜度為O(nlog(n))。但是，在最壞情況下（基本有序時(shí)），快速排序所需的比較次數(shù)和冒泡排序的比較次數(shù)相同,其時(shí)間復(fù)雜度為O(n2)。快速排序需要一個(gè)棧作輔助空間，用來實(shí)現(xiàn)遞歸處理左、右子文件。在最壞情況下,遞歸深度為n，因此所需棧的空間大小為O(n)數(shù)量級?？焖倥判蚴遣环€(wěn)定的。

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第29頁。3010.4選擇排序10.4.1.簡單選擇(選擇排序)

算法思想:設(shè)待排序的文件為(r[1],r[2],...,r[n]),關(guān)鍵字為

(r[1].key,r[2].key,...,r[n].key),

第1趟(遍)：在(r[1],r[2],...,r[n])中,選出關(guān)鍵字最小的記錄r[min].key，若min<>1,則交換r[1]和r[min]；需要進(jìn)行n-1次比較。第2趟(遍)：在n-1個(gè)記錄(r[2],...,r[n])中,選出關(guān)鍵字最小的記錄r[min].key，若min<>2,則交換r[2]和r[min]；需要進(jìn)行n-2次比較。

......

第n-1趟(遍)：在最后的2個(gè)記錄記錄(r[n-1],r[n])中,選出關(guān)鍵字最小的記錄r[min].key，若min<>n-1,則交換r[n-1]

和min]；需要進(jìn)行1次比較。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第30頁。31例:k1k2k3k4k5k6初始關(guān)鍵字：（438921432815

）第1遍排序后：15（8921

432843

）第2遍排序后：1521（8943

28

43

）第3遍排序后：152128（438943

）第4遍排序后：15212843

（8943

）第5遍排序后：15212843

4389數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第31頁。32簡單選擇排序算法:(

對數(shù)組r[1..n]中的記錄作簡單選擇排序)voidSelectSort(RecTyper[],intn){inti,j,min;RecTypex;//交換記錄的中間變量

for(i=1;i<n;i++)//共n-1趟(遍){min=i;//r[i]為最小記錄r[min]for(j=i+1;j<=n;j++)if(r[j].key<r[min].key)min=j;//修改minif(min!=i)//若r[min]不是r[i]{x=r[min];//交換r[min]和r[i]r[min]=r[i];r[i]=x;}}}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第32頁。33算法分析：(1)比較次數(shù)，在任何情況下,均為

n-1∑(n－i)＝(n-1)+(n-2)+...+1i=1

＝n(n-1)/2＝O(n2)(2)交換記錄的次數(shù)

在最好情況下,原n個(gè)記錄遞增有序：不移動記錄。

在最壞情況下,每次都要交換數(shù)據(jù)（不是遞減有序）共交換記錄n-1對,移動記錄數(shù)3(n-1)次。故,時(shí)間復(fù)雜度為O(n2)。(3)只需少量中間變量作為輔助空間。(4)算法是不穩(wěn)定的。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第33頁。3410.4.2.堆排序（HeapSort)

堆的定義：n個(gè)元素的序列{k1,k2,…,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時(shí)，稱之為堆。

ki≤k2iki≥k2i

或

ki≤k2i+1ki≥k2i+1(i=1,2,…,

n/2)

其中：前面一種稱為小頂堆；后面一種稱為大頂堆。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第34頁。35n個(gè)元素的序列{k1,k2,…,kn}可看成是一個(gè)結(jié)點(diǎn)個(gè)數(shù)為n的完全二叉數(shù)，若其為大頂堆，則k1最大；若其為小頂堆，則k1最小。例：序列1：{96，83，27，38，11，09}

序列2：{12，36，24，85，47，30，53，91}9683273811093685479124305312序列2的二叉樹(小頂)堆序列1的二叉樹(大頂堆)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第35頁。36

通常，n個(gè)元素的序列{k1,k2,…,kn}不符合堆的定義，所以，面臨的第一個(gè)問題：問題1：如何將序列{k1,k2,…,kn}處理成（大頂）堆（初始化）？問題1一旦解決，得到規(guī)模為n的堆，則k1最大，將k1與kn互換，則最大的數(shù)已放置到最后，同時(shí)，剩下的序列{k1,k2,…,kn-1}不是堆，如何將其重新處理成規(guī)模為n-1的堆，求取第二大的數(shù)據(jù)，以此類推，堆的規(guī)模逐步減小，直到求出第n-1大的數(shù)據(jù)，完成遞增排序。所以，面臨的第二個(gè)問題是：數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第36頁。37問題2：如何在堆頂元素被替換后，調(diào)整剩余元素成為一個(gè)新的堆。提示：根據(jù)上述過程描述，借助大頂堆可實(shí)現(xiàn)序列的遞增排序；借助小頂堆可實(shí)現(xiàn)序列的遞減排序。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第37頁。389683271138252209問題2方法：某序列的堆形式：{96，27，83，25，22，11，38，09}098327113825229609832711382522960983271138252296除頂以外，其它都符合堆的定義83=max(83,27)38=max(38,11)sssjjjsjs數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第38頁。39typedefSqListHeapType;//采用順序表存儲表示voidHeapAdjust(HeapType&H，

ints,intm)//已知H.r[s…m]中記錄的關(guān)鍵字除H.r[s].key之外均滿足堆的定義，本函數(shù)調(diào)整H.r[s]的關(guān)鍵字,使H.r[s…m]成大頂堆。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第39頁。40voidHeapAdjust(HeapType&H，ints,intm){rc=H.r[s];//保存需調(diào)整的數(shù)據(jù)元素，空出s的記錄位置

for(j=2*s;j<=m;j*=2){//j<=m表示s有左孩子序號j=2*sif(j<m&&H.r[j].key<H.r[j+1].key)//j<m表示s有右孩子j+1j++;//計(jì)算s的具有較大關(guān)鍵字的孩子的序號jif(rc.key>H.r[j].key)//rc在s的結(jié)點(diǎn)時(shí)滿足結(jié)點(diǎn)定義,調(diào)整完畢

break;H.rs[s]=H.r[j];s=j;//s的較大孩子上移，修改s下移

}//正常結(jié)束時(shí)，s的結(jié)點(diǎn)無孩子結(jié)點(diǎn)。

H.r[s]=rc;}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第40頁。413897764965139849問題1方法:建立序列：{49,38,65,49,76,13,98,97}的初始堆。1。對以最后一個(gè)結(jié)點(diǎn)（序號n）的雙親結(jié)點(diǎn)（序號i=n/2

）為根的二叉樹，進(jìn)行堆調(diào)整。38977649651398492。對以序號序號i=i-1的結(jié)點(diǎn)為雙親結(jié)點(diǎn)為根的二叉樹，進(jìn)行堆調(diào)整。65數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第41頁。4238977649651398493。對以序號序號i=i-1的結(jié)點(diǎn)為雙親結(jié)點(diǎn)為根的二叉樹，進(jìn)行堆調(diào)整。9738764965139849973876496513984938數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第42頁。439738764965139849973876496513499897387649491365984。對以序號序號i=i-1的結(jié)點(diǎn)為雙親結(jié)點(diǎn)為根的二叉樹，進(jìn)行堆調(diào)整。此時(shí)i已等于1，調(diào)整完后，初始大頂堆建成。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第43頁。449798764949136538763849491365979876384997136549984938499713657698選擇較小范圍選擇較小范圍調(diào)整調(diào)整數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第44頁。45i>0真假堆排序結(jié)束H.r[1]H.r[i]調(diào)整以i為根的二叉樹i--n/2inii>1真假i--調(diào)整剩余i-1個(gè)結(jié)點(diǎn)的二叉樹初始化堆選擇、調(diào)整n-1次數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第45頁。46算法分析與評價(jià)：對深度為k的堆，調(diào)整算法進(jìn)行的關(guān)鍵字比較次數(shù)至多為2(k-1)次，建立n個(gè)元素的初始堆，調(diào)用HeapAdjust算法n/2次，總共進(jìn)行的關(guān)鍵字比較次數(shù)不超過4n次。

n個(gè)結(jié)點(diǎn)的完全二叉樹深度為h=log2n+1

需要調(diào)整的層為h-1層至1層，以第i層某結(jié)點(diǎn)為根的二叉樹深度對應(yīng)為h-i+1,第i層結(jié)點(diǎn)最多為2i-1個(gè)，故調(diào)整時(shí)比較關(guān)鍵字最多為：

2i-1*2*(h-i+1-1)=2i*(h-i)令j=h-i,當(dāng)i=h-1時(shí)j=1當(dāng)i=1時(shí)j=h-12h-j*j=2h-1*1+2h-2*2+…+21*(h-1)=2h+1-2h-2<2h+1=2

log2n+2<=4*2

log2n=4n數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第46頁。47算法分析與評價(jià)(續(xù)）：n個(gè)結(jié)點(diǎn)的完全二叉樹深度為log2n+1，選擇調(diào)整過程n-1次，總共比較次數(shù)至多為：

2（log2(n-1)+log2(n-2)+…+log22)<2n(log2n)最壞情況下，算法的時(shí)間復(fù)雜度為O(4n+nlogn)O(nlogn)

；僅需要一個(gè)記錄大小供交換用的輔助存儲空間；堆排序是不穩(wěn)定排序；堆排序?qū)τ涗涊^少的文件不提倡，對較大的文件很有效。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第47頁。4810.5歸并排序基本思想：把k(k≥2)個(gè)有序子文件合并在一起，形成一個(gè)新的有序文件。同時(shí)歸并k個(gè)有序子文件的排序過程稱為k-路歸并排序。

2-路歸并排序：歸并2個(gè)有序子文件的排序。例.將有序文件A和A歸并為有序文件C。

A＝(2,10,15,18,21,30)B＝(5,20,35,40)

按從小至大的次序從A或B中依次取出

2,5,10,15,...,40,順序歸并到C中,得:C＝(2,5,10,15,18,20,21,30,35,40)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第48頁。490608154007092022r[9..16]910111213141516y[9..16]9101112131415162-路歸并有序文件(表)i→j→k→例有序子表有序子表0607080915202240一般地，2-路歸并過程為：假定文件r[low..high]中的相鄰子文件(子表)(r[low],r[low+1],...,r[mid])和(r[mid+1],...,r[high])為有序子文件,其中:low≤mid<high。將這兩個(gè)相鄰有序子文件歸并為有序文件y[low..high],即：

(y[low],y[low+1],...,y[high])數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第49頁。50將兩個(gè)有序子文件歸并為有一個(gè)有序文件的算法voidmerge(r,y,low,mid,high)RecTyper[],y[]；intlow,mid,high；{intk=i=low,j=mid+1；

while(i<=mid&&j<=high){if(r[i].key<=r[j].key){y[k]=r[i]；//歸并前一個(gè)子文件的記錄

i++；}else

{y[k]=r[j]；//歸并后一個(gè)子文件的記錄

j++；}

k++；

}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第50頁。51while(j<=high)//歸并后一個(gè)子文件余下的記錄

{y[k]=r[j]；

j++；k++；

}while(i<=mid)

//歸并前一個(gè)子文件余下的記錄

{y[k]=r[i]；

i++；k++；

}}//merge數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第51頁。522-路歸并排序假定文件(r[1],r[2],...,r[n])中記錄是隨機(jī)排列的,進(jìn)行2-路歸并排序，首先把它劃分為長度均為1的n個(gè)有序子文件，然后對它們逐步進(jìn)行2－路歸并排序。其步驟如下：第1趟：從r[1..n]中的第1個(gè)和第2個(gè)有序子文件開始,調(diào)用算法merge,每次歸并兩個(gè)相鄰子文件,歸并結(jié)果放到y(tǒng)[1..n]中。在y中形成n/2個(gè)長度為2的有序子文件。若n為奇數(shù),則y中最后一個(gè)子文件的長度為1。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第52頁。53第2趟：把y[1..n]看作輸入文件,將n/2個(gè)有序子文件兩兩歸并,歸并結(jié)果回送到r[1..n]中,在r中形成n/2/2個(gè)長度為4的有序子文件。若y中有奇數(shù)個(gè)子文件，則r中最后一個(gè)子文件的長度為2。

......共計(jì)經(jīng)過log2n趟歸并,最后得到n個(gè)記錄的有序文件。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第53頁。54064420100220080706441020022007080610204402070820１２３４５６７８r[1..８]１２３４５６７８y[1..８]１２３４５６７８r[1..８]１２３４５６７８y[1..８]第1趟第3趟第2趟例1.對8個(gè)記錄作2路歸并排序,共進(jìn)行l(wèi)og28＝3趟歸并。0206070810202044數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第54頁。5506442010022008070532141234567891011r[1..11]0644102002200708053214y[1..11]0610204402070820051432r[1..11]0206070810202044051432y[1..11]1234567891011123456789101112345678910110205060708101420203244r[1..11]1234567891011第1趟第3趟第2趟第4趟例2.對11個(gè)記錄作2-路歸并排序,進(jìn)行l(wèi)og211＝4趟歸并。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第55頁。56。。。。11+s1+2s1+3s。。。。ii+si+2sni+2s-1一趟歸并排序算法：假設(shè)：s為子文件的長度,將r中的子文件歸并到y(tǒng)中（1）兩等長子文件合并條件：i+2s-1<=n。。。。11+2s。。。。ii+2sn數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏排序全文共65頁，當(dāng)前為第56頁。57。。。11+s1+2s1+3s。。。。i-2si-sini+s-1（2）長度為S的子文件與長度為[1，s)子文件合并條件：i+2s-1>n并且i+s-1<n。。。11+s1+2s1+3s。。。。