数据结构严蔚敏排序.pptx

《数据结构严蔚敏排序.pptx》由会员分享，可在线阅读，更多相关《数据结构严蔚敏排序.pptx（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、110.1 10.1 概述1.1.排序：将文件或表中的记录，通过某种方法整理成按关 键字大小次序排列的处理过程。假定n n个记录的文件为 (R(R1 1,R,R2 2,.,R,.,Rn n)对应的关键字为 (K(K1 1,K,K2 2,.,K,.,Kn n)则排序是确定如下一个排列 p p1 1,p,p2 2,.,p,.,pn n 使得:Kp:Kp1 1KpKp2 2.Kp.Kpn n 从而得到一个有序文件 (Rp(Rp1 1,Rp,Rp2 2,.Rp,.Rpn n)第1页/共65页22005120051刘大海刘大海 80 80 75 752004220042王王 伟伟 90 90 83 83

2、 2006620066吴晓英吴晓英 82 82 88 8820038 20038 刘刘 伟伟 80 80 70 702005220052王王 洋洋 60 60 70 70 1 12 23 34 45 5学 号 姓 名 数学 外语20038 20038 刘刘 伟伟 80 80 70 702004220042王王 伟伟 90 90 83 83 2005120051刘大海刘大海 80 80 75 752005220052王王 洋洋 60 60 70 70 2006620066吴晓英吴晓英 82 82 88 88学 号 姓 名 数学 外语2005220052王王 洋洋 60 60 70 70 2005

3、120051刘大海刘大海 80 80 75 7520038 20038 刘刘 伟伟 80 80 70 702006620066吴晓英吴晓英 82 82 88 882004220042王王 伟伟 90 90 83 83 2004220042王王 伟伟 90 90 83 83 1731732006620066吴晓英吴晓英 82 82 88 881701702005120051刘大海刘大海 80 80 75 7515515520038 20038 刘刘 伟伟 80 80 70 701501502005220052王王 洋洋 60 60 70 70 1301301 12 23 34 45 5学 号 姓

4、 名 数学 外语学 号 姓 名 数学 外语 总分1 12 23 34 45 51 12 23 34 45 5(a)(a)无序表(b)(b)按学号排列的有序表(c)(c)按数学成绩排列的有序表(d)(d)按总分成绩排列的有序表学生成绩表第2页/共65页3稳定的排序不稳定的排序2005120051刘大海刘大海 80 80 75 752004220042王王 伟伟 90 90 83 83 2006620066吴晓英吴晓英 82 82 88 8820038 20038 刘刘 伟伟 80 80 70 702005220052王王 洋洋 60 60 70 70 1 12 23 34 45 5学 号 姓 名

5、 数学 外语2005220052王王 洋洋 60 60 70 70 20038 20038 刘刘 伟伟 80 80 70 702005120051刘大海刘大海 80 80 75 752006620066吴晓英吴晓英 82 82 88 882004220042王王 伟伟 90 90 83 83 学 号 姓 名 数学 外语1 12 23 34 45 5(e)(e)按数学成绩排列的有序表不稳定的排序2.2.什么是排序的稳定性 假设在待排序的文件中，存在两个具有相同关键字的记录R(i)R(i)与R(j),R(j),其中R(i)R(i)位于R(j)R(j)之前。在用某种排序法排序之后,R(i),R(i)

6、仍位于R(j)R(j)之前，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。例 数列(10,25,22,42,(10,25,22,42,2525,30,18)(10,18,22,25,30,18)(10,18,22,25,2525,30,42),30,42)(10,25,22,42,(10,25,22,42,2525,30,18)(10,18,22,30,18)(10,18,22,2525,25,30,42),25,30,42)第3页/共65页43.3.内部排序(内排序)-)-在计算机内存中进行的排序 外部排序(外排序)-)-借助计算机外存进行的排序4.4.待排序的记录和顺序表(文件

7、)的数据类型#define MAXSIZE 20 /#define MAXSIZE 20 /最大长度 typedef int KeyTypetypedef int KeyType；/关键字类型 typedef struct /typedef struct /记录类型 KeyType key KeyType key；/关键字 InfoType otherinfoInfoType otherinfo；/其它数据类型 RecTypeRecType；/记录类型名第4页/共65页5typedef structtypedef struct RecType rMAXSIZE+1 RecType rMAXSI

8、ZE+1；/r0/r0用作监视哨 int length;/int length;/实际表长 SeqListSeqList；/记录表类型 或表和表长分别定义和说明 RecType rMAXSIZE+1RecType rMAXSIZE+1；/r0/r0用作监视哨 int lengthint length；/实际表长 lengthlengthMAXSIZEMAXSIZE第5页/共65页65.5.排序算法分析(1)(1)时间复杂度 对n n个记录排序，所需比较关键字的次数；最好情况；最坏情况；平均情况 对n n个记录排序，所需移动记录的次数；最好情况；最坏情况；平均情况(2)(2)空间复杂度 排序过程

9、中，除文件中的记录所占的空间外，所需的辅助存储空间的大小。第6页/共65页76.6.内排序方法(1)(1)对顺序表的排序 插入排序：直接插入排序；折半插入排序；2-路插入排序；表插入排序；希尔(Shell)排序；交换排序:冒泡排序：单向冒泡排序，双向冒泡排序 快速排序 选择排序：简单选择/选择排序；树形选择排序；堆排序第7页/共65页8 归并排序:2-路归并排序 k-路归并排序基数排序:多关键字排序 最高位优先法 最低位优先法 链式基数排序(2)(2)对单链表的排序:直接插入,简单选择,冒泡排序,基数排序第8页/共65页910.2 10.2 插入排序算法基本思想 将待排序的记录插入到已排序的子

10、文件中去，使得插入之后得到的子文件仍然是有序子文件。插入一个记录，首先要对有序子文件进行查找，以确定这个记录的插入位置。按查找方式的不同，插入排序又可以分为线性插入排序和折半插入排序，前者使用顺序查找，后者使用折半查找。第9页/共65页101.1.直接插入排序(线性插入排序)设待排序的文件为：(r1,r2,.,rn)(r1,r2,.,rn)关键字为：(r1.key,r2.key,.,rn.key)(r1.key,r2.key,.,rn.key)首先,将初始文件中的记录r1r1看作有序子文件；第1 1遍：将r2r2插入有序子文件中，若：r2.keyr1.keyr2.keyr1.key，则r2r2

11、插在r1r1之前；否则，插在r1r1的后面。第2 2遍：将记录r3r3插入前面已有2 2个记录的有序子文件中，得到3 3个记录的有序子文件。以此类推，依次插入r4,.,rn,r4,.,rn,最后得到n n个记录的递增有序文件。第10页/共65页11例.直接插入排序,设K0K0为 监视哨”K0 K1 K2 K3 K4 K5 K6K0 K1 K2 K3 K4 K5 K6初始关键字：(4343)21 89 15 )21 89 15 4343 28 28第1 1遍排序后：21(21 21(21 4343)89 15 )89 15 4343 28 28(43(43后移)第2 2遍排序后：89(21 89

12、(21 4343 89)15 89)15 4343 28 28(不后移)第3 3遍排序后：15(15 21 15(15 21 43 43 89)89)4343 28 28(89,43,21(89,43,21后移)第4 4遍排序后：4343(15 21 (15 21 4343 4343 89)28 89)28(89(89后移)第5 5遍排序后：28(15 21 28 28(15 21 28 4343 4343 89)89)(89,43,43(89,43,43后移)21218989151543432828第11页/共65页12直接插入排序算法（对数组r1.nr1.n中的n n个记录作插入排序）vo

13、id InsertSort(RecType r,int nvoid InsertSort(RecType r,int n）int i,j int i,j；for(i=2for(i=2；i=ni=n；i+)i+)r0=ri r0=ri；/待插记录riri存入监视哨中 j=i-1j=i-1；/已排序的范围1 1 i-1i-1 /从ri-1ri-1开始向左扫描 while(r0.keyrj.key)while(r0.keyrj.key)rj+1=rj rj+1=rj；/记录后移 j-j-；/继续向左扫描 rj+1=r0 rj+1=r0；/插入记录r0,r0,即原riri 第12页/共65页13r r

14、i ir r1 1r r2 2r ri-1i-1r ri ir rn nr0r0r1r1r2r2ri-1ri-1ririrnrn直接插入排序算法分析：(1)(1)最好情况，原n n个记录递增有序：比较关键字n-1n-1次 移动记录2(n-1)2(n-1)次,(,(将数据复制到r0r0后又复制回来）第13页/共65页14r ri ir r1 1r r2 2r ri-1i-1r ri ir rn nr0r0 r1r1 r2r2 ri-ri-11riri rnrn r ri ir r1 1r r2 2 r ri-1 i-1 r ri ir rn nr0r0 r1r1 r2r2 ri-ri-11rir

15、i rnrn(2)(2)最坏情况，原n n个记录递减有序：比较关键字的次数:n n i=2+3+.+n=(n-1)(n+2)/2=O(n i=2+3+.+n=(n-1)(n+2)/2=O(n2 2)i=2 i=2 移动记录的次数(个数):):n n (i-1+2)=3+4+.+(n+1)(i-1+2)=3+4+.+(n+1)i=2 i=2 =(n-1)(n+4)/2 =(n-1)(n+4)/2 次 =O(n=O(n2 2)第14页/共65页15平均移动记录的次数约为:(3)(3)平均比较关键字的次数约为:故,时间复杂度为O(nO(n2 2)。(4)(4)只需少量中间变量作为辅助空间。(5)(5

16、)算法是稳定的。第15页/共65页162.2.折半插入排序（对数组r1.nr1.n中的n n个记录作折半插入排序）void BInsertSort(RecType r,int nvoid BInsertSort(RecType r,int n）int i,j int i,j；for(i=2for(i=2；i=ni=n；i+)i+)r0=ri r0=ri；/待插记录riri存入监视哨中 low=1 low=1；high=i-1high=i-1；while(low=high)while(low=high)m=(low+high)/2;m=(low+high)/2;if(r0.key rm.key)

17、if(r0.key=high+1;-j)rj+1=rj 1;j =high+1;-j)rj+1=rj；rhigh+1=r0;rhigh+1=r0;减少了记录的比较次数，记录的移动次数不变。第16页/共65页1710.3 10.3 交换排序10.3.1 10.3.1 冒泡排序基本思想:设待排序的文件为r1.nr1.n第1 1趟(遍)：从r1r1开始,依次比较两个相邻记录的关键字ri.keyri.key和ri+1.key,ri+1.key,若ri.keyri+1.keyri.keyri+1.key，则交换记录riri和ri+1ri+1的位置；否则,不交换。(i=1,2,.n-1)(i=1,2,.n

18、-1)第1 1趟之后,n,n个关键字中最大的记录移到了rnrn的位置上。第2 2趟：从r1r1开始,依次比较两个相邻记录的关键字ri.keyri.key和ri+1.key,ri+1.key,若ri.keyri+1.keyri.keyri+1.key，则交换记录riri和ri+1ri+1的位置；否则,不交换。(i=1,2,.n-2)(i=1,2,.n-2)第2 2趟之后,前n-1n-1个关键字中最大的记录移到了rn-1rn-1的位置上。.作完n-1n-1趟,或者不需再交换记录时为止。第17页/共65页18一般情况：第1 1遍:10 3 7 8 5 2 1 4 9 6 010-1):10 3 7

19、8 5 2 1 4 9 6 010-1)第2 2遍：3 7 8 5 2 1 4 9 6 3 7 8 5 2 1 4 9 6 1010 010-2)010-2)第3 3遍：3 7 5 2 1 4 8 6 3 7 5 2 1 4 8 6 9 109 10 010-3)010-3)第4 4遍：3 5 2 1 4 7 6 3 5 2 1 4 7 6 8 8 9 109 10 010-4)010-4)第5 5遍：3 2 1 4 5 6 3 2 1 4 5 6 7 8 7 8 9 109 10 010-5)010-5)第6 6遍：2 1 3 4 5 2 1 3 4 5 6 6 7 8 7 8 9 109

20、10 010-6)010-6)第7 7遍：1 2 3 4 1 2 3 4 5 5 6 6 7 8 7 8 9 109 10 010-7)010-7)第8 8遍：1 2 3 1 2 3 4 4 5 5 6 6 7 8 7 8 9 109 10 010-8)010-8)第9 9遍：1 2 1 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 010-9)010-9)1 1 2 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 交换范围第18页/共65页19算法分析:最好情况:待排序的文件已是有序文件，只需要进行1 1趟 排序,共计比较关键字的次数为 n

21、n1 1 不交换记录。最坏情况:要经过n-1n-1趟排序，所需总的比较关键字的次 数为 (n-1)+(n-2)+.+1(n-1)+(n-2)+.+1n(n-1)/2 n(n-1)/2 交换记录的次数最多为 (n-1)+(n-2)+.+1(n-1)+(n-2)+.+1n(n-1)/2 n(n-1)/2 移动记录次数最多为 3n(n-1)/2 3n(n-1)/2。只需要少量中间变量作为辅助空间。算法是稳定的。第19页/共65页20冒泡排序算法(对n n个整数按递增次序作冒泡排序)void bubble1(int a,int n)void bubble1(int a,int n)int i,j,te

22、mp int i,j,temp；for(i=0for(i=0；in-1in-1；i+)/i+)/作n-1n-1趟排序 for(j=0for(j=0；jn-1-ijaj+1)if(ajaj+1)temp=aj temp=aj；/交换记录 aj=aj+1aj=aj+1；aj+1=tempaj+1=temp；for(i=0 for(i=0；inin；i+)i+)printf(%d,ai)printf(%d,ai)；/输出排序后的元素 第20页/共65页21改进的冒泡排序算法void bubblesort(RecType r,int n)void bubblesort(RecType r,int n)

23、int i,j,swap int i,j,swap；RecType tempRecType temp；j=1j=1；/置比较的趟数为1 1 do swap=0 do swap=0；/置交换标志为0 0 for(i=1 for(i=1；i=n-jiri+1.key)if(ri.keyri+1.key)temp=ri temp=ri；/交换记录 ri=ri+1 ri=ri+1；ri+1=tempri+1=temp；swap=1swap=1；/置交换标志为1 1 j+j+；/作下一趟排序 while(jn&swap)while(jn&swap)；/未作完n-1n-1趟,且标志为1 1第21页/共65

24、页2210.3.2 10.3.2 快速排序基本思想：首先在r1.nr1.n中，确定一个riri，经过比较和移动，将riri放到 中间 某个位置上，使得riri左边所有记录的关键字小于等于ri.keyri.key，riri右边所有记录的关键字大于等于ri.keyri.key。以riri为界,将文件划分为左、右两个子文件。用同样的方法分别对这两个子文件进行划分,得到4 4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,便得到原文件的有序文件。第22页/共65页2320200505373708086363 12125959151544440808xi ij j0808050537370

25、8086363 12125959151544440808xi ij j20202020例.给定文件(20,05,37,08,63,12,59,15,44,08)(20,05,37,08,63,12,59,15,44,08)，选用第1 1个元素2020进行划分:第23页/共65页2408080505373708086363 12125959151544440808x xi ij j08080505373708086363 12125959151544443737x xi ij j08080505151508086363 12125959151544443737x xi ij ji ii i202

26、0j jj j20202020第24页/共65页2508080505151508086363 12125959151544443737x xi ij j08080505151508086363 12125959636344443737x xi ij j08080505151508081212 12125959636344443737x xi i j j202008080505151508081212 20205959636344443737x xi i j j左子文件右子文件2020i ii i2020j jj ji i2020第25页/共65页26void quksort(RecType r

27、,int low,int high)void quksort(RecType r,int low,int high)RecType x RecType x；int i,jint i,j；if(lowhigh)if(lowhigh)/有两个以上记录 i=low i=low；j=highj=high；x=rix=ri；/保存记录到变量x x中 do do /此时i i指示位置可用 while(i=x.key)while(i=x.key)j-j-；/j/j从右向左端扫描通过keykey不小于x.keyx.key的元素 if(ij)if(ij)/i,j/i,j未相遇 ri=rj ri=rj；i+i+；

28、/此时j j指示位置可用 while(ij&ri.key=x.key)while(ij&ri.key=x.key)i+i+；/i/i从左向右端扫描通过keykey不大于x.keyx.key的元素 if(ij)if(ij)rj=ri rj=ri；j-j-；while(i!=j)while(i!=j)；/i,j/i,j未相遇 第26页/共65页27/划分结束，i i经过的是keykey不大于x.keyx.key的元素；j j经过的是keykey不小于x.keyx.key的元素。i,ji,j至少有一个指示的位置可用 ri=xri=x；quksort(r,low,i-1)quksort(r,low,i

29、-1)；/递归处理左子文件 quksort(r,i+1,high)quksort(r,i+1,high)；/递归处理右子文件 对文件r1.nr1.n快速排序：void quicksort(RecType r,int n)void quicksort(RecType r,int n)quksort(r,1,n)quksort(r,1,n)；第27页/共65页28算法分析就平均速度而言，快速排序是已知内部排序方法中最好的一种排序方法,其时间复杂度为O(nlog(n)O(nlog(n)。但是，在最坏情况下（基本有序时），快速排序所需的比较次数和冒泡排序的比较次数相同,其时间复杂度为O(nO(n2 2

30、)。快速排序需要一个栈作辅助空间，用来实现递归处理左、右子文件。在最坏情况下,递归深度为n n，因此所需栈的空间大小为O(n)O(n)数量级。快速排序是不稳定的。第28页/共65页2910.4 10.4 选择排序10.4.1.10.4.1.简单选择(选择排序)算法思想:设待排序的文件为(r1,r2,.,rn),(r1,r2,.,rn),关键字为 (r1.key,r2.key,.,rn.key),(r1.key,r2.key,.,rn.key),第1 1趟(遍)：在(r1,r2,.,rn)(r1,r2,.,rn)中,选出关键字最小 的记录rmin.keyrmin.key，若min1,min1,则

31、交换r1r1和rminrmin；需要进行n-1n-1次比较。第2 2趟(遍)：在n-1n-1个记录(r2,.,rn)(r2,.,rn)中,选出关键字 最小的记录rmin.keyrmin.key，若min2,min2,则交换r2r2和rminrmin；需要进行n-2n-2次比较。.第n-1n-1趟(遍)：在最后的2 2个记录记录(rn-1,rn)(rn-1,rn)中,选 出关键字最小的记录rmin.keyrmin.key，若minn-1,minn-1,则交换rn-1rn-1 和minmin；需要进行1 1次比较。第29页/共65页30例:k1 k2 k3 k4 k5 k6:k1 k2 k3 k4

32、 k5 k6 初始关键字：（4343 89 21 89 21 4343 28 28 1515 ）第1 1遍排序后：15 15 （89 89 2121 43 43 28 28 4343 ）第2 2遍排序后：15 21 15 21 （89 89 43 43 2828 4343 ）第3 3遍排序后：15 21 28 15 21 28 （4343 89 89 4343 ）第4 4遍排序后：15 21 28 15 21 28 4343 （89 89 4343 ）第5 5遍排序后：15 21 28 15 21 28 4343 43 43 89 89第30页/共65页31简单选择排序算法:(:(对数组r1.

33、nr1.n中的记录作简单选择排序)void SelectSort(RecType r,int n)void SelectSort(RecType r,int n)int i,j,min;int i,j,min;RecType x;/RecType x;/交换记录的中间变量 for(i=1;in;i+)/for(i=1;in;i+)/共n-1n-1趟(遍)min=i;/ri min=i;/ri为最小记录rminrmin for(j=i+1;j=n;j+)for(j=i+1;j=n;j+)if(rj.keyrmin.key)if(rj.keyrmin.key)min=j;/min=j;/修改min

34、min if(min!=i)/if(min!=i)/若rminrmin不是riri x=rmin;/x=rmin;/交换rminrmin和riri rmin=ri;ri=x;rmin=ri;ri=x;第31页/共65页32算法分析：(1)(1)比较次数，在任何情况下,均为 n-1 n-1 (n (ni)i)(n-1)+(n-2)+.+1(n-1)+(n-2)+.+1 i=1 i=1 n(n-1)/2 n(n-1)/2 O(nO(n2 2)(2)(2)交换记录的次数 在最好情况下,原n n个记录递增有序：不移动记录。在最坏情况下,每次都要交换数据（不是递减有序）共交换记录n-1n-1对,移动记录

35、数3(n-1)3(n-1)次。故,时间复杂度为O(nO(n2 2)。(3)(3)只需少量中间变量作为辅助空间。(4)(4)算法是不稳定的。第32页/共65页3310.4.2.10.4.2.堆排序（堆排序（Heap Sort)Heap Sort)堆的定义：堆的定义：n n个元素的序列个元素的序列kk1 1,k,k2 2,k,kn n 当且仅当满足下关系当且仅当满足下关系时，称之为堆。时，称之为堆。k ki i k k2i2i k ki i k k2i2i 或或 k ki i k k2i+12i+1 k ki i k k2i+12i+1 (i=1,2,(i=1,2,n/2n/2)其中：其中：前面一

36、种称为小顶堆；前面一种称为小顶堆；后面一种称为大顶堆。后面一种称为大顶堆。第33页/共65页34 n n个元素的序列个元素的序列kk1 1,k,k2 2,k,kn n 可看成是一个结点个数为可看成是一个结点个数为n n的完全二叉数，若其为大顶堆，则的完全二叉数，若其为大顶堆，则k k1 1最大；若其为小顶堆，最大；若其为小顶堆，则则k k1 1最小。最小。例：例：序列序列1 1：9696，8383，2727，3838，1111，09 09 序列序列2 2：1212，3636，2424，8585，4747，3030，5353，91 91 9696838327273838 111109093636

37、8585474791912424303053531212序列2 2的二叉树(小顶)堆序列1 1的二叉树(大顶堆)第34页/共65页35 通常，通常，n n个元素的序列个元素的序列kk1 1,k,k2 2,k,kn n 不符合堆的定义，不符合堆的定义，所以，面临的第一个问题：所以，面临的第一个问题：问题问题1 1：如何将序列如何将序列kk1 1,k,k2 2,k,kn n 处理成（大顶）堆（初始化）？处理成（大顶）堆（初始化）？问题问题1 1一旦解决，得到规模为一旦解决，得到规模为n n的堆，则的堆，则k k1 1最大，将最大，将k k1 1与与k kn n互换，则最大的数已放置到最后，同时，剩

38、下的序列互换，则最大的数已放置到最后，同时，剩下的序列kk1 1,k,k2 2,k,kn-1n-1 不是堆，如何将其重新处理成规模为不是堆，如何将其重新处理成规模为n-1n-1的堆，的堆，求取第二大的数据，以此类推，堆的规模逐步减小，直到求求取第二大的数据，以此类推，堆的规模逐步减小，直到求出第出第n-1n-1大的数据，完成递增排序。所以，面临的第二个问大的数据，完成递增排序。所以，面临的第二个问题是：题是：第35页/共65页36问题问题2 2：如何在堆顶元素被替换后，调整剩余元素成为一个新如何在堆顶元素被替换后，调整剩余元素成为一个新的堆。的堆。提示：根据上述过程描述，提示：根据上述过程描述

39、，借助大顶堆可实现序列的递增排借助大顶堆可实现序列的递增排序；借助小顶堆可实现序列的递减排序。序；借助小顶堆可实现序列的递减排序。第36页/共65页3796968383272711113838252522220909问题2方法：某序列的堆形式：96，27，83，25，22，11，38，09 090983832727111138382525222296960909838327271111383825252222969609098383272711113838252522229696除顶以外，其它都符合堆的定义83=max(83,27)38=max(38,11)sssjjjsjs第37页/共65页

40、38typedef SqList HeapType;typedef SqList HeapType;/采用顺序表存储表示void HeapAdjust(HeapType&Hvoid HeapAdjust(HeapType&H，int s,int m)int s,int m)/已知H.rsmH.rsm中记录的关键字除H.rs.keyH.rs.key之外均满足堆的定义，本函数调整H.rsH.rs的关键字,使H.rsmH.rsm成大顶堆。第38页/共65页39void HeapAdjust(HeapType&Hvoid HeapAdjust(HeapType&H，int s,int m)int s,

41、int m)rc=H.rs;rc=H.rs;/保存需调整的数据元素，空出s s的记录位置 for(j=2*s;j=m;j*=2)for(j=2*s;j=m;j*=2)/j=m/j=m表示s s有左孩子序号 j=2*sj=2*s if(jm&H.rj.keyH.rj+1.key)if(jm&H.rj.keyH.rj+1.key)/jm/j H.rj.key)if(rc.key H.rj.key)/rc/rc在s s的结点时满足结点定义,调整完毕 break;break;H.rss=H.rj;s=j;H.rss=H.rj;s=j;/s/s的较大孩子上移，修改s s下移 /正常结束时，s s的结点无

42、孩子结点。H.rs=rc;H.rs=rc;第39页/共65页4038389797767649496565131398984949问题1 1方法:建立序列：49,38,65,49,38,65,49,49,76,13,98,9776,13,98,97的初始堆。1 1。对以最后一个结点（序号n n）的双亲结点（序号i=i=n/2n/2 ）为根的二叉树，进行堆调整。383897977676494965651313989849492 2。对以序号序号i=i-1i=i-1的结点为双亲结点为根的二叉树，进行堆调整。6565第40页/共65页4138389797767649496565131398984949

43、3 3。对以序号序号i=i-1i=i-1的结点为双亲结点为根的二叉树，进行堆调整。97973838767649496565131398984949979738387676494965651313989849493838第41页/共65页429797383876764949656513139898494997973838767649496565131349499898979738387676494949491313656598984 4。对以序号序号i=i-1i=i-1的结点为双亲结点为根的二叉树，进行堆调整。此时i i已等于1 1，调整完后，初始大顶堆建成。第42页/共65页439797989

44、8767649494949131365653838767638384949494913136565979798987676383849499797131365654949989849493838494997971313656576769898选择较小范围选择较小范围调整调整第43页/共65页44i0i0真假堆排序结束H.r1H.r1H.riH.ri调整以i i为根的二叉树i-i-n/2n/2 i in ni ii1i1真假i-i-调整剩余i-1i-1个结点的二叉树初始化堆选择、调整n-1n-1次第44页/共65页45算法分析与评价：对深度为k k的堆，调整算法进行的关键字比较次数至多为2(k-

45、1)2(k-1)次，建立n n个元素的初始堆，调用HeapAdjustHeapAdjust算法 n/2n/2 次，总共进行的关键字比较次数不超过4n4n次。n n个结点的完全二叉树深度为h=h=loglog2 2n n+1+1 需要调整的层为h-1h-1层至1 1层，以第i i层某结点为根的二叉树深度对应为h-i+1,h-i+1,第i i层结点最多为2 2i-1i-1个，故调整时比较关键字最多为：2 2i-1i-1*2*(h-i+1-1)=2*2*(h-i+1-1)=2i i*(h-i)*(h-i)令j=h-i,j=h-i,当i=h-1i=h-1时 j=1 j=1 当i=1i=1时 j=h-1

46、j=h-1 2 2h-jh-j*j=2*j=2h-1h-1*1+2*1+2h-2h-2*2+2*2+21 1*(h-1)=2*(h-1)=2h+1h+1-2h-2-2h-2 2 2h+1h+1=2=2 log2nlog2n+2+2=4*2=4*2 loglog2 2n n=4n=4n第45页/共65页46算法分析与评价(续）：n n个结点的完全二叉树深度为 loglog2 2n n+1+1，选择调整过程n-1n-1次，总共比较次数至多为：2 2（loglog2 2(n-1)(n-1)+loglog2 2(n-2)(n-2)+loglog2 22 2)2n()2n(loglog2 2n n)最坏

47、情况下，算法的时间复杂度为O(4n+nlogn)O(4n+nlogn)O(nlogn)O(nlogn)；仅需要一个记录大小供交换用的辅助存储空间；堆排序是不稳定排序；堆排序对记录较少的文件不提倡，对较大的文件很有效。第46页/共65页4710.5 10.5 归并排序 基本思想：把k(k2)k(k2)个有序子文件合并在一起，形成一个新的有序文件。同时归并k k个有序子文件的排序过程称为k-k-路归并排序。2-2-路归并排序：归并2 2个有序子文件的排序。例.将有序文件A A和A A归并为有序文件C C。A A(2,10,15,18,21,30)(2,10,15,18,21,30)B B(5,20

48、,35,40)(5,20,35,40)按从小至大的次序从A A或B B中依次取出 2,5,10,15,.,40,2,5,10,15,.,40,顺序归并到C C中,得:C C(2,5,10,15,18,20,21,30,35,40)(2,5,10,15,18,20,21,30,35,40)第47页/共65页4806060808151540400707090920202222r9.16r9.16 9 91010111112121313141415151616y9.16y9.16 9 910101111121213131414151516162-2-路归并有序文件(表)i ij jk k例有序子表有

49、序子表06060707080809091515202022224040一般地，2-2-路归并过程为：假定文件rlow.highrlow.high中的相邻子文件(子表)(rlow,rlow+1,.,rmid)(rlow,rlow+1,.,rmid)和(rmid+1,.,rhigh)(rmid+1,.,rhigh)为有序子文件,其中:lowmidhigh:lowmidhigh。将这两个相邻有序子文件归并为有序文件ylow.high,ylow.high,即：(ylow,ylow+1,.,yhigh)(ylow,ylow+1,.,yhigh)第48页/共65页49将两个有序子文件归并为有一个有序文件的

50、算法void merge(r,y,low,mid,high)void merge(r,y,low,mid,high)RecType r,yRecType r,y；int low,mid,highint low,mid,high；int k=i=low,j=mid+1 int k=i=low,j=mid+1；while(i=mid&j=high)while(i=mid&j=high)if(ri.key=rj.key)if(ri.key=rj.key)yk=ri yk=ri；/归并前一个子文件的记录 i+i+；else else yk=rj yk=rj；/归并后一个子文件的记录 j+j+；k+k+