《数据结构排序》课件.ppt

《《数据结构排序》课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构排序》课件.ppt（91页珍藏版）》请在三一办公上搜索。

1、1,第10章 排序,陈守孔 孟佳娜 陈卓,2,本章目录,10.1 概述10.2 插入排序 10.2.1 直接插入排序 10.2.2 折半插入排序*10.2.3 二路插入排序*10.2.4 表插入排序 10.2.5 希尔排序10.3 交换排序 10.3.1 起泡排序 10.3.2 快速排序10.4 选择排序 10.4.1 直接选择排序 10.4.2 树形选择排序10.4.3 堆排序10.5 归并排序10.6 分配排序10.7 内部排序方法的比较10.8 外部排序 10.8.1 文件管理 10.8.2 外部排序 10.8.3 多路归并排序 10.8.4 置换选择排序*10.8.5 最佳归并树*10

2、.8.6 磁带排序,3,主要内容,知识点1、排序的定义，排序可以看作是线性表的一种操作2、排序的分类，稳定排序与不稳定排序的定义。3、插入排序（直接插入、对分插入、二路插入、表插入、希尔插入排序）。4、交换排序（冒泡排序、快速排序）。5、选择排序（简单选择排序、树形选择排序、堆排序）。6、归并排序、基数排序。7、外部排序重点难点1、各种排序所基于的基本思想。2、排序性能的分析，是否是稳定排序。3、折半插入、希尔排序。4、快速排序。5、堆排序。6、败者树、置换选择排序、最佳归并树。7、对每种排序方法的学习，能举一反三。,4,基本概念,排序：假设含n个记录的序列为R1,R2,Rn，其相应的关键字序

3、列为 K1,K2,Kn，这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Ks1Ks2Ksn，按此固有关系将n个记录的序列重新排列为 Rs1,Rs2,Rsn 的操作称作排序。,5,基本概念,稳定排序：若Ki为关键字，Ki=Kj（ij），且在排序前的序列中Ri领先于Rj。经过排序后，Ri与Rj的相对次序保持不变（即Ri仍领先于Rj），则称这种排序方法是稳定的，否则称之为不稳定的。内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序 外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能一次在内存中完成，则称此类排序问题为外部排序,6,排序的类型定义,#de

4、fine n 待排序记录的个数typedef struct int key;AnyType other;记录其它数据域 RecType;RecType Rn+1;,7,基本思想：假定第一个记录有序，从第2个记录开始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。,插入排序,插入排序种类：直接插入排序 折半插入排序 二路插入排序 表插入排序 希尔排序,8,直接插入排序,基本思想：将记录Ri(2=i=n)插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i,9,示例,初始关键字序列：51 33 62 96 87 17 28 51i=2(33

5、)33 51 62 96 87 17 28 51i=3(62)33 51 62 96 87 17 28 51i=4(96)33 51 62 96 87 17 28 51i=5(87)33 51 62 87 96 17 28 51i=6(17)17 33 51 62 87 96 28 51i=7(28)17 28 33 51 62 87 96 51i=8(51)17 28 33 51 51 62 87 96,10,一趟直接插入排序算法,void StrOnePass(RecType R，int i)已知R1.i-1中的记录按关键字非递减有序排列，本算法 插入Ri,使R1.i中的记录按关键字非递减

6、有序排列 R0=Ri;j=i-1;将待排序记录放进监视哨 x=R0.key;从后向前查找插入位置，将大于待排序记录向后移动 while(x Rj.key)Rj+1=Rj;j-;记录后移 Rj+1=R0;将待排序记录放到合适位置 StrOnePass,11,直接插入排序算法,void StrInsSort1(RecType R，int n)本算法对R1.n进行直接插入排序 for(i=2;i=n;i+)假定第一个记录有序 StrOnePass(R，i)；,12,直接插入排序性能分析,最好情况,13,折半插入排序,void BinsSort(RecType R，int n)对R1.n进行折半插入排

7、序 for(i=2;ihigh;j-)Rj+1=Rj;记录后移 Rhigh+1=R0;插入 forBinsSort,14,折半插入排序性能分析,减少了比较次数，移动次数不变。时间复杂度仍为O（n2）。,15,在对一组记录（54，38，96，23，15，72，60，45，83）进行直接排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较多少次,16,二路插入排序,对折半插入排序改进，减少了移动记录的次数，但它要借助n个记录的辅助空间，即其空间复杂度为O（n）。基本思想：另设一数组d，将R1赋值给d1，并将d1看作排好序的中间记录，从第二个记录起依次将关键字小于d1的记录插入d1之前的有

8、序序列，将关键字大于d1的记录插入d1之后的有序序列。借助两个变量first和final来指示排序过程中有序序列第一个记录和最后一个记录在d中的位置。,17,初始关键字序列：51 33 62 96 87 17 28 51 i=1 51 firstfinali=2 51 33 final firsti=3 51 62 33 final firsti=4 51 62 96 33 final firsti=5 51 62 87 96 33 final firsti=6 51 62 87 96 17 33 final first i=7 51 62 87 96 17 28 33 final first

9、 i=8 51 51 62 87 96 17 28 33 final first,18,二路插入排序算法,void BiInsertSort(RecType R，int n)二路插入排序的算法int dn+1;辅助存储 d1=R1;first=1;final=1;for(i=2;i=d1.key)插入后部 low=1;high=final;while(low=high+1;j-)dj+1=dj;移动元素 dhigh+1=Ri;final+;插入有序位置,19,else if(first=1)插入前部 first=n;dn=Ri;else low=first;high=n;while(low=h

10、igh)m=(low+high)/2;if(Ri.key dm.key)high=m-1;else low=m+1;while for(j=first;j=high;j+)dj-1=dj;移动元素 dhigh=Ri;first-;if if/for,20,表插入排序,静态链表#define n 待排序记录的个数typedef struct int key;AnyType other;记录其他数据域 int next;STListType;STListType SLn+1;,21,表插入排序算法,void ListInsSort(STListType SL,int n)对记录序列SL1.n作表插

11、入排序。SL0.key=MAXINT;SL0.next=1;SL1.next=0;for(i=2;i=n;i+)查找插入位置 j=0;for(k=SL0.next;SLk.key=SLi.key;)j=k,k=SLk.next;SLj.next=i;SLi.next=k;结点i插入在结点j和结点k之间 for ListInsSort,22,表物理排序,void Arrange(STListType SL，int n)调整静态链表SL中各结点的指针值，使记录按关键字有序排列 p=SL0.next;p指示第一个记录的当前位置 for(i=1;in;i+)SL1.i-1 记录已按关键字有序，第i个记

12、录的当前位置应不小于i while(pi)p=SLp.next;找到第i个记录，并用p指示其在SL中当前位置 q=SLp.next;q指示尚未调整的表尾 if(p!=i)SLpSLi;交换记录，使第i个记录到位 SLi.next=p;指向被移走的记录，使得以后可由while循环找回 if p=q;p指示尚未调整的表尾，为找第i+1个记录作准备 forArrange,23,希尔(shell 1959)排序,基本思想：从“减小n”和“基本有序”两方面改进。将待排序的记录划分成几组，从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序

13、。,24,希尔排序示例,二趟排序结果：17 10 51 33 28 51 52 62 96 87三趟排序结果：10 17 28 33 51 51 52 62 87 96,初始关键字序列：51 33 62 96 87 17 28 51 52 10,一趟排序结果：17 28 51 52 10 51 33 62 96 87,25,希尔排序算法,void ShellSort(RecType R，int n)以步长di/2分组的希尔排序，第一个步长取n/2，最后一个取1for(d=n/2;d=1;d=d/2)for(i=1+d;i0第i个元素插入到合适位置 for forShellSort,26,希尔排

14、序示例,请给出对一组记录（54,38,96,23,15,90,72,60,45,83）进行希尔排序（增量序列为5，3，1）时的排序过程。,27,交换排序,主要思路：在排序过程中，通过对待排序记录序列中元素间关键字的比较，发现次序相反的，即将元素位置交换来达到排序目的。,交换排序种类：起泡排序 快速排序,28,起泡排序,基本思想：对所有相邻记录的关键字值进行比较，如果是逆序（ajaj+1），则将其交换，最终达到有序化,29,起泡排序示例,初始关键字序列：51 33 62 96 87 17 28 51第一趟排序结果：33 51 62 87 17 28 51 96 第二趟排序结果：33 51 62

15、17 28 51 87 96 第三趟排序结果：33 51 17 28 51 62 87 96 第四趟排序结果：33 17 28 51 51 62 87 96 第五趟排序结果：17 28 33 51 51 62 87 96 第六趟排序结果：17 28 33 51 51 62 87 96,30,void BubbleSort(RecType R，int n)起泡排序 i=n;i 指示无序序列中最后一个记录的位置 while(i1)lastExchange=1;记最后一次交换发生的位置 for(j=1;jRj+1.key）temp=Rj；Rj=Rj+1；Rj+1=temp；逆序时交换 lastExc

16、hange=j;if i=lastExchange;while,起泡排序算法,31,一组关键字（19,01,26,92,87,11,43,87,21），进行冒泡排序，试列出每一趟排序后的关键字序列,32,快速排序,基本思想：从待排序记录序列中任选取一个记录（通常可选第一个记录）的关键字作为枢轴（或支点），凡其关键字小于枢轴的记录均移动至该记录之前，而关键字大于枢轴的记录均移动至该记录之后。一趟快速排序后就将排序序列分成两部分，再分别对这两部分递归快速排序。,由Hoare(图灵奖获得者)1962年提出，被评为20世纪十大优秀算法之一。,33,快速排序图示,1,n,34,快速排序示例,初始关键字序

17、列：51 33 62 96 87 17 28 51R0=51 i(枢轴)jj向前扫描 i j,第一次交换之后：28 33 62 96 87 17 51 i ji向后扫描 i j,第二次交换之后：28 33 96 87 17 62 51 i jj向前扫描 i j,第三次交换之后：28 33 17 96 87 62 51i向后扫描 i j,第四次交换之后：28 33 17 87 96 62 51j向前扫描 i j,完成一趟排序：28 33 17 51 87 96 62 51 ij,35,快速排序示例,初始关键字序列：51 33 62 96 87 17 28 51一趟排序之后：28 33 17 51

18、 87 96 62 51,分别进行快速排序：17 28 33 结束 结束 51 62 87 96 51 62 结束 结束,有序序列：17 28 33 51 51 62 87 96,36,快速排序算法,int Partition(RecType R，int l，int h)交换记录子序列Rl.h中的记录，使枢轴记录到位并返回其所在位置 int i=l;j=h;用变量i,j记录待排序记录首尾位置 R0=Ri;以子表的第一个记录作枢轴，将其暂存到记录R0中 x=Ri.key;用变量x存放枢轴记录的关键字 while(i=x)j-;Ri=Rj;将比枢轴小的记录移到低端 while(ij 返回枢轴位置P

19、artition,37,快速排序算法,void QuickSort(RecType R，int s，int t)对记录序列Rs.t进行快速排序 if(st)k=Partition(R,s,t);QuickSort(R,s,k-1);QuickSort(R,k+1,t);if QuickSort,快速排序的平均时间复杂度为O（nlog2n）最差为O(n2),38,对下列一组关键字（46,58,15,45,90,18,10,62）试写出快速排序的每一趟的排序结果,39,选择排序,基本思想：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、，并分别将它们定位到序列左侧（或

20、右侧）的第1个位置、第2个位置、，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。,选择排序种类：直接（简单）选择排序 树形选择排序 堆排序,40,直接选择排序,待排记录序列的状态为：,并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i趟直接选择排序是，从无序序列Ri.n的n-i+1记录中选出关键字最小的记录加入有序序列,41,直接选择排序示例,初始关键字序列：51 33 62 96 87 17 28 51 第一趟排序后：17 33 62 96 87 51 28 51 第二趟排序后：17 28 62 96 87 51 33 51 第三趟排序后：17 2

21、8 33 96 87 51 62 51第四趟排序后：17 28 33 51 87 96 62 51第五趟排序后：17 28 33 51 51 96 62 87第六趟排序后：17 28 33 51 51 62 96 87第七趟排序后：17 28 33 51 51 62 87 96,42,直接选择排序算法,void SelectSort(RecType R，int n)对记录序列R1.n作直接选择排序。for(i=1;in;i+)选择第i小的记录，并交换到位 k=i;假定第i个元素的关键字最小 for(j=i+1;j=n;j+)找最小元素的下标 if(Rj.keyRk.key)k=j;if(i!=

22、k)RiRk;与第i个记录交换 forSelectSort,直接选择排序的平均时间复杂度为O（n2）,记录移动次数最好情况：0 最坏情况：3(n-1)比较次数（与初始状态无关）：,43,堆的定义：堆是满足下列性质的数列K1,K2,Kn：,堆排序,若上述数列是堆，则K1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆（小堆或大堆）。,44,堆排序示例,96，51，87，33，28，62，51，17 是大顶堆,例如：17，28，51，33，62，96，87，51 是小顶堆,45,建立完全二叉树,基本思想：先建一个堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前

23、n1个记录重新调整为一个堆（调堆的过程称为“筛选”），再将堆顶记录和第n1个记录交换，如此反复直至排序结束。,堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？,46,第二个问题解决方法方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆,第一个问题解决方法方法：把整个数组R1到Rn调整为一个大根堆，即把完全二叉树中以每一个结点为根的子树都调整为堆。所以需要将以序号为n/2，n/21，1的结点作为根的子树调整为堆即可用筛选法调整

24、堆,47,调整堆示例,(a)堆,(b)17与51交换后的情景,48,调整堆示例,(d)28与87交换后调成的新堆,(c)调整后的新堆,49,建堆示例,初始关键字序列：51，33，62，96，87，17，28，51为例，其初始建大顶堆过程,(a)4.8是堆，不调整,(b)3.8是堆，不调整,50,建堆示例,(c)2.8不是堆，进行筛选,(d)1.8不是堆，进行筛选,(e)建成的大顶堆,51,堆排序筛选算法,void Sift(RecType R，int i，int m)假设Ri+1.m中各元素满足堆的定义，本算法调整Ri使序列 Ri.m中各元素满足堆的性质 R0=Ri;for(j=2*i;j=m

25、;j*=2)if(jm Sift,52,堆排序算法,void HeapSort(RecType R，int n)对记录序列R1.n进行堆排序。for(i=n/2;i0;i-)把R1.n建成大顶堆 Sift(R,i,n);for(i=n;i1;i-)输出并调堆 R1Ri;Sift(R,1,i-1);将R1.i-1重新调整为大顶堆 forHeapSort,堆排序的时间复杂度为O（nlog2n）,53,时间复杂度：最坏情况下T(n)=O(nlogn)建初始堆时间：调用SIFT 过程n/2 次，每次以Ri为根的子树调整为堆。具有n个结点的完全二叉树深度是h=logn+1,第i层结点个数至多为 2 i-

26、1。SIFT对深度为k的完全二叉树进行比较的关键字次数至多为2(k-1)，因此比较总次数不超过C1(n)2 i-1*2(h-1)=2 h-1+2 h-2*2+2 h-3*3+2*(h-1)=2*2(log 2n)+1=4n重新建堆时间：排序过程中重新建堆比较总次数不超过C2(n)=2*(log n-1+log n-2+log 2)2n log n=O(n log n),54,已知一组关键字（46,58,15,45,90,18,10,62）试写出堆排序建初始堆和排序的过程,55,归并排序,基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2

27、的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，如此重复，直至得到一个长度为n的有序序列为止,56,归并排序示例,二趟归并排序后：33 51 62 96 17 28 87,初始关键字序列：51 33 62 96 87 17 28,一趟归并排序后：33 51 62 96 17 87 28,三趟归并排序后：17 28 33 51 62 87 96,57,一趟归并排序算法,void Merge(RecType R,RecType R1,int i,int l,int h)将有序的Ri.l和Rl+1.h归并为有序的R1i.h for(j=l+1,k=i;i=l 将剩余的Rj.h复制到R1M

28、erge,58,归并排序算法,void Msort(RecType R,RecType R1,int s,int t)将Rs.t进行2-路归并排序为R1s.t if(s=t)R1s=Rs;else m=(s+t)/2;将Rs.t平分为Rs.m和Rm+1.t Msort(R,R2,s,m);递归地将Rs.m归并为有序的R2s.m Msort(R,R2,m+1,t);递归地Rm+1.t归并为有序的R2m+1.t Merge(R2,R1,s,m,t);将R2s.m和R2m+1.t归并到R1s.t ifMSort,59,归并排序算法,void MergeSort(RecType R,int n)对记录

29、序列R1.n作2-路归并排序。MSort(R,R,1,n);MergeSort归并排序的设计复杂度为O(nlogn),60,分配排序,基本思想：利用关键字的结构，通过“分配”和“收集”的办法来实现排序,分配排序可分为桶排序和基数排序两类,61,桶排序,桶排序（Bucket Sort）也称箱排序（Bin Sort），其基本思想是：设置若干个桶，依次扫描待排序记录R1.n，把关键字等于k的记录全部都装到第k个桶里（分配），然后，按序号依次将各非空的桶首尾连接起来（收集）。,62,基数排序,基数排序就是一种借助“多关键字排序”的思想来实现“单关键字排序”的算法,假设有n个记录待排序序列 R1,R2,

30、，Rn，每个记录Ri中含有d个关键字(Ki0,Ki1,Kid-1),则称上述记录序列对关键字(Ki0,Ki1,Kid-1)有序是指：对于序列中任意两个记录Ri和Rj(1ijn)都满足下列(词典)有序关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)其中K0被称为“最主”位关键字，Kd-1被称为“最次”位关键字。,63,最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，依次类推，直至最后对最次位关键字排序完成为止。最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排

31、序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。,实现多关键字排序通常有两种作法:,64,基数排序示例,p369367167239237138230139第一次分配得到：B0.f230B0.eB7.f367167237B7.eB8.f138B8.eB9.f369239139B9.e第一次收集得到：p230367167237138369239139,65,基数排序示例,第二次分配得到：B3.f230237138239139B3.eB6.f367167369B6.e第二次收集得到：p230237138239139367167369,66,基数排

32、序示例,第三次分配得到：B1.f138139167B1.eB2.f230237239B2.eB3.f367369B3.e第三次收集之后便得到记录的有序序列：p138139167230237239367369,67,基数排序的类型定义,#define n 待排序记录的个数typedef struct int keyd;关键字由d个分量组成 int next;静态链域AnyType other;记录其他数据域 SLRecType;SLRecType Rn+1;R1.n存放n个待排序记录typedef struct int f,e;队列的头、尾指针 SLQueue;SLQueue Bm 用队列表示桶

33、，共m个,68,基数排序的算法,int RadixSort(SLRecType R,int n)对R1.n进行基数排序，返回收集用的链头指针 for(i=1;i=0;j-)进行d趟排序 for(i=0;im;i+)初始化桶 Bi.f=-1;Bi.e=-1;for while(p!=-1)一趟分配，按关键字的第j个分量进行分配 k=Rp.keyj;k为桶的序号 if(Bk.f=-1)Bk.f=p;Bk为空桶，将Rp链到桶头 else RBk.e.next=p;将Rp链到桶尾 Bk.e=p;修改桶的尾指针 p=Rp.next;扫描下一个记录 while接下页,69,基数排序的算法（续）,接上页 i

34、=0;/一趟收集 while(Bi.f=-1)i+;找第一个非空的桶 t=Bi.e;p=Bi.f p为收集链表的头指针，t为尾指针 while(im-1)i+;取下一个桶 if(Bi.f!=-1)Rt.next=Bi.f;t=Bi.e;连接非空桶 while Rt.next=-1;本趟收集完毕，将链表的终端结点指针置空 for return p;RadixSort,70,基数排序的性能分析,基数排序的时间复杂度是O(d*(rd+n)。当n较小、d较大时，基数排序并不合适。只有当n较大、d较小时，特别是记录的信息量较大时，基数排序最为有效。基数排序存储空间复杂度为O（rd）。基数排序是稳定的。,

35、71,已知8个记录，其关键字分别为(179，208，306，093，859，984，271，033)试用基数排序法实施排序，描述其排序过程,72,内部排序方法的比较,73,结论,（1）若n较小（如n50），可采用直接插入排序或直接选择排序。（2）若待排序记录的初始状态已是按关键字基本有序，则选用直接插入排序或起泡排序为宜。（3）当n较大，若关键字有明显结构特征（如字符串、整数等），且关键字位数较少易于分解，采用时间性能是线性的基数排序较好。若关键字无明显结构特征或取值范围属于某个无穷集合（例如实数型关键字）时，应借助于“比较”的方法来排序，可采用时间复杂度为O（nlog2n）的排序方法：快速排

36、序、堆排序或归并排序。,74,（4）对于以主关键字进行排序的记录序列，所用的排序方法是否稳定无关紧要，而用次关键字进行排序的记录序列，应根据具体问题所需慎重选择排序方法及描述算法。（5）前面讨论的排序算法，大都是利用一维向量实现的。若记录本身信息量大，为避免移动记录耗费大量时间，可用链式存储结构。比如插入排序和归并排序都易于在链表上实现。但象快速排序和堆排序这样的排序算法，却难于在链表上实现，此时可以提取关键字建立索引表，然后对索引表进行排序。,75,以关键码序列（503，087，512，061，908，170，897，275，653，246）为例，手工执行以下排序算法，写出每一趟排序结束时的

37、关键码状态：（1）直接插入排序；（2）希尔排序（增量5，3，1）；（3）起泡排序（4）快速排序；（5）简单选择排序（6）堆排序；（7）归并排序；（8）基数排序。,76,外部排序的两个阶段,1、生成顺串2、合并顺串,77,外部排序分析,外部排序所需总时间 T=m*tI+d*tI/O+s*ntm其中tI是构造一个初始归并段所需内部排序的平均时间；tI/O是进行一次外存读/写的平均时间；tm是对一个记录进行内部归并所需时间；n为记录个数；m为初始归并段的个数；s为归并的趟数；d为总的读/写次数,78,外部排序分析,79,多路归并排序,k-路归并，n个记录分布在k个归并段上，从k个记录中选出一个最小记

38、录需进行k1次比较，一趟归并要得到全部n个记录共需进行(n1)(k1)次比较。此k-路归并排序的内部归并过程中进行的总的比较次数为s(n1)(k1)。故有：,80,败者树,败者树是一颗完全二叉树 叶结点存放参加比较的记录 非叶结点记忆其子女结点中的败者 根结点之上的结点存放最后的胜者,81,实现5-路归并的败者树,82,建立败者树,void CreateLoserTree(int ls)b0到bk-1为完全二叉树ls的叶子结点，存有k个关 键字，沿叶子到根的k条路径将ls调整为败者树 bk=MINKEY;for(i=0;i=0;i-)Adjust(ls,i);依次从bk-1,bk-2,b0出发

39、调整败者CreateLoserTree,83,调整败者树,void Adjust(int ls,int s)从叶子结点bs到根结点ls0的路径调整败者树 t=(s+k)/2;lst是bs的双亲结点 while(t0)if(bsblst)slst;s指示新的胜者 t=t/2;while ls0=s;Adjust,84,多路平衡归并算法,#define MAXKEY 最大关键字值#define MINKEY 关键字可能的最小值#define k 归并路数void KWayMerge(int ls,int b)for(i=0;ik;i+)input(bi);CreateLoserTree(ls);建

40、败者树ls，选得最小关键字为bls0 while(bls0!=MAXKEY)q=ls0;q指示当前最小关键字所在归并段 output(q);输出 input(bq);从编号为q的输入归并段中读入下一个记录的关键字 Adjust(ls,q);调整败者树，选择新的最小关键字 whileoutput(ls0);将含最大关键字MAXKEY的记录写至输出归并段KWayMerge,85,置换选择排序利用败者树来减少归并段个数,置换选择排序,设初始待排文件为FI，输出文件FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳c个记录，（1）从FI输入c个记录到工作区WA，并构造败者树（2）利用败者树从

41、WA中选出最小关键字记录MIN。（3）将此最小关键字记录MIN输出到FO中去。（4）若FI不空，则从FI输入下个记录到WA中。（5）调整败者树，从所有关键字比MIN大的记录中选出最小关键字记录，作为新的记录MIN。（6）重复（3）（5），直到在败者树中选不出关键字比MIN大的记录为止。此时得到一个初始归并段，在其后加一个归并段结束标志。（7）重复（2）（6），直至WA为空。,86,置换选择排序示例,87,置换选择排序性能分析,1961年利用扫雪车类比得出：初始归并段的长度平均是缓冲区长度m的两倍，即2m。,88,最佳归并树,设有9个初始归并段，其长度（即记录数）依次为：9,30,12,18,3,17,2,6,24。现作3-路平衡归并,若将初始归并段的长度看成是归并树中叶子结点的权，则此三叉树的带权路径长度的WPL=242为读写次的一半,89,最佳归并树,最佳归并树：归并树是一棵哈夫曼树，则可使对外存进行的读写次数达到最少，这棵归并树便称作最佳归并树,90,最佳归并树,建立最佳归并树的方法：,与构造哈夫曼树的方法类似，若在初始归并段的数目不足时，增加长度为零的“虚段”，再按构造哈夫曼树的方法建立归并树,91,磁带排序,平衡归并：用2k条磁带，作k路归并排序多步归并：用k十1路磁带，可作k-路归并,