数据结构排序.ppt

上传人:夺命阿水 文档编号:229779 上传时间:2023-03-02 格式:PPT 页数:52 大小:686KB
返回 下载 相关 举报
数据结构排序.ppt_第1页
第1页 / 共52页
数据结构排序.ppt_第2页
第2页 / 共52页
数据结构排序.ppt_第3页
第3页 / 共52页
数据结构排序.ppt_第4页
第4页 / 共52页
数据结构排序.ppt_第5页
第5页 / 共52页
点击查看更多>>
资源描述

《数据结构排序.ppt》由会员分享,可在线阅读,更多相关《数据结构排序.ppt(52页珍藏版)》请在课桌文档上搜索。

1、第九章 排序,本章讨论数据结构中另一个重要的运算排序(或分类),包括排序的定义、各种排序的方法、算法实现及时间复杂度的分析等内容。9.1 概述排序(Sort)是将无序的记录序列(或称文件)调整成有序的序列。对文件(File)进行排序有重要的意义。如果文件按key有序,可对其折半查找,使查找效率提高;在数据库(Data Base)和知识库(Knowledge Base)等系统中,一般要建立若干索引文件,就牵涉到排序问题;在一些计算机的应用系统中,要按不同的数据段作出若干统计,也涉及到排序。排序效率的高低,直接影响到计算机的工作效率。另外,研究排序方法和算法,目的不单纯是完成排序的功能和提高效率,

2、其中对软件人员的程序设计能力会有一定的提高,也是对以前数据结构内容的复习、巩固和提高。,1.排序定义,设含有n个记录的文件f=(R1 R2Rn),相应记录关键字(key)集合k=k1 k2kn。若对1、2n的一种排列:P(1)P(2)P(n)(1P(i)n,ij时,P(i)P(j))有:kP(1)kP(2)kP(n)递增关系或 kP(1)kP(2)kP(n)递减关系则使f 按key线性有序:(RP(1)RP(2)RP(n)),称这种运算为排序(或分类)。关系符“”或“”并不一定是数学意义上的“小于等于”或“大于等于”,而是一种次序关系。但为讨论问题方便,取整型数作为key,故“”或“”可看作通

3、常意义上的符号。2.稳定排序和非稳定排序 设文件f=(R1RiRjRn)中记录Ri、Rj(ij,i、j=1n)的key相等,即Ki=Kj。若在排序前Ri领先于Rj,排序后Ri仍领先于Rj,则称这种排序是稳定的,其含义是它没有破坏原本已有序的次序。反之,若排序后Ri与Rj的次序有可能颠倒,则这种排序是非稳定的,即它有可能破坏了原本已有序记录的次序。,3.内排序和外排序,若待排文件f在计算机的内存储器中,且排序过程也在内存中进行,称这种排序为内排序。内排序速度快,但由于内存容量一般很小,文件的长度(记录个数)n受到一定限制。若排序中的文件存入外存储器,排序过程借助于内外存数据交换(或归并)来完成,

4、则称这种排序为外排序。我们重点讨论内排序的一些方法、算法以及时间复杂度的分析。4.内排序方法 截止目前,各种内排序方法可归纳为以下五类:(1)插入排序;(2)交换排序;(3)选择排序;(4)归并排序;(5)基数排序。5.文件存储结构(1)顺序结构类似线性表的顺序存储,将文件f=(R1 R2Rn)存于一片连续的存储空间,逻辑上相邻的记录在存储器中的物理位置也是相邻的,如图9.1:在这种结构上对文件排序,一般要作记录的移动。当发生成片记录移动时,是一个很耗时的工作。,(2)链表结构,类似于线性表的链式存储,文件中记录用节点来表示,其物理位置任意,节点之间用指针相连,如图9.2:链表结构的优点在于排

5、序时无须移动记录,只需修改相应记录的指针即可。(3)地址映象结构 该结构是另设一地址向量,存储文件中各记录的地址(或序号),如图9.3:,(数据文件),i j(地址向量),排序可在地址向量上进行,一定程度上免去了排序时记录的移动。,9.2 插入排序,插入排序(Insert Sort)可分为:直接插入排序、折半插入排序、链表插入排序以及Shell(希尔)排序等。每种排序按照排序方法、举例说明、算法描述以及算法分析等几个步骤讨论。9.2.1 直接插入排序 设待排文件f=(R1 R2Rn)相应的key集合为k=k1 k2kn,文件f对应的结构可以是9.1节中讨论的三种文件结构之一。1.排序方法 先将

6、文件中的(R1)看成只含一个记录的有序子文件,然后从R2起,逐个将R2至Rn按key插入到当前有序子文件中,最后得到一个有序的文件。插入的过程上是一个key的比较过程,即每插入一个记录时,将其key与当前有序子表中的key进行比较,找到待插入记录的位置后,将其插入即可。另外,假定排序后的文件按递增次序排列(以下同)。例9-1 设文件记录的key集合k=50,36,66,76,95,12,25,36(考虑到对记录次key排序的情况,允许多个key相同。如此例中有2个key为36,后一个表示成36,以示区别),按直接插入排序方法对k的排序过程如下:,直接插入排序,k=50,36,66,76,95,

7、12,25,36,50 36,36,50 66,36,50,66 76,36,50,66,76 95,36,50,66,76,95 12,12,36,50,66,76,95 25,12,25,36,50,66,76,95 36,12,25,36,36,50,66,76,95,一般,插入ki(2in),当kjkikj+1ki-1时:,直接插入排序,文件结构说明:#define maxsize 1024 文件最大长度typedef int keytype;设key为整型typedef struct 记录类型 keytype key;记录关键字 记录其它域Retype;typedef struct

8、文件或表的类型 Retype Rmaxsize+1;文件存储空间 int len;当前记录数sqfile;若说明sqfile F;则:(F.R1,F.R2F.RF.len)为待排文件,它是一种顺序结构;文件长度n=F.len;F.R0为工作单元,起到“监视哨”作用;记录的关键字ki写作F.Ri.key。,直接插入排序,2.算法描述void Insort(sqfile F)对顺序文件F直接插入排序的算法 int i,j;for(i=2;i=F.len;i+)插入n1个记录 F.R0=F.Ri;待插入记录先存于监视哨 j=i-1;while(F.R0.keyF.Rj.key);key比较 F.Rj

9、+1=F.Rj;记录顺序后移 j-;F.Rj+1=F.R0;原Ri插入j+1位置 3.算法分析 排序算法一般包括key的比较和记录的移动两种操作,所以算法分析应求出这两种操作的时耗作为算法的时间复杂度T(n)。当然算法分析还应包括算法中存储空间的耗费,但当辅助空间占用不太多时,不作讨论。,直接插入排序,设排序中key比较次数为C,C最小时记为Cmin,最大时记为Cmax。(1)当文件原来就有序(正序)时,每插入一个Ri只需比较key一次,即:(2)当文件原本逆序(key从大到小)时,每插入一个Ri要和子表中i1个key比较,加上同自身R0的比较,此时比较次数最多,即:(3)求记录总的移动次数m

10、(m最小时记为mmin,最大时记为mmax)算法中,Ri=R0,R0=Rj+1移动两次;插入Ri时,Ri-1Rj+1各移动一次。文件正序时,子表中记录的移动免去,即:逆序时,插入Ri牵涉移动整个子表。移动次数为2+(i1)=i+1,此时表的移动次数最大,即:排序的时间复杂度取耗时最高的量级,故直接插入排序的T(n)=O(n2)。,9.2.2 折半插入排序,排序算法的T(n)=O(n2),是内排序时耗最高的时间复杂度。随着文件记录数n的增大,效率降低较快。下面的一些插入排序的方法,都是围绕着改善算法的时间复杂度而展开的。另外,直接插入排序是稳定排序。为减少插入排序过程中key的比较次数,可采用折

11、半插入排序。1.排序方法 同直接插入排序,先将(R1)看成一个子文件,然后依次插入R2Rn。但在插入Ri时,子表R1Ri-1已是有序的,查找Ri在子表中的位置可按折半查找方法进行,从而降低key的比较次数。例9-2 设当前子表key序列及插入的ki=28如下:序号:1 2 3 4 5 6 15 20 25 3 0 35 40 28 low high 令:,28R3.key=25,low=3+1=4;28high,所以“28”应插在low=4所指示的位置。,折半插入排序,2.算法描述void Binsort(sqfile F)对文件F折半插入排序的算法 int i,j,low,high,mid;

12、for(i=2;i=F.Rmid.key)low=mid+1;调整下界 else high=mid-1;调整上界 for(j=i-1;j=low;j-)F.Rj+1=F.Rj;记录顺移 F.Rlow=F.R0;原Ri插入low位置,折半插入排序,3.算法分析 插入Ri(2in)时,子表记录数为i1。同第八章中的折半查找算法的讨论,查找Ri的key比较次数为,故总的key比较次数C为:显然优于O(n2)。但折半插入排序的记录移动次数并未减少,仍为O(n2)。故算法的时间复杂度T(n)仍为O(n2)。9.2.3 链表插入排序设待排序文件f=(R1 R2Rn),对应的存储结构为单链表结构,如图9.4

13、:1.排序方法 链表插入排序实际上是一个对链表遍历的过程。先将表置为空表,然后依次扫描链表中每个节点,设其指针为p,搜索到p节点在当前子表的适当位置,将其插入。,链表插入排序,例9-3 设含4个记录的链表如图9.5:,插入50:,初始化:,插入36:,插入66:,插入12:,2.算法描述,typedef struct node 存放记录的节点 keytype key;记录关键字 记录其它域 struct node*next;链指针Lnode,*linklist;void Linsertsort(linklist L)链表插入排序算法 linklist p,q,r,u;p=L-next;p为待插

14、入节点指针 L-next=NULL;置子表为空 while(p)若待排序节点存在 r=L;q=L-next;r为q的前驱指针 while(q,3.算法分析,(1)当链表L逆序时,每插入一个节点时,key的比较次数最多为1,总的key比较次数C达到最小,即:(2)当链表L正序时,每插入第i号(1in)节点都要搜索到当前子表的表尾,key的比较次数为i-1,故总的key比较次数C达到最大,即:所以链表插入排序的时间复杂度T(n)=O(n2)。但排序过程中不牵涉到记录的移动,只是修改相应指针,这一点优于其它的插入排序方法。9.2.4 Shell排序 Shell(希尔)排序又称“缩小增量”排序,195

15、9年由D.L.Shell提出。希尔发现:直接插入排序中,key比较次数及记录移动次数会比较大,若将待排序文件按某种次序分隔成若干个子文件,对各子文件“跳跃”式的排序,然后调整子文件个数,逐步对原文件排序,这样总的key比较次数尤其是记录移动次数也许会大大降低。,1.Shell排序方法,设待排文件f=(R1 R2Rn),先将f中相隔增量d(如令d=n/2)的记录组成一个个子文件,对各子文件插入排序;然后缩小增量d(如令d=d/2),再将相隔新增量的记录组成一个个子文件,对诸子文件排序,直到增量d=1为止,排序完毕。这是一种跳跃式的排序方法,它使得文件逐步有序,从而克服了一次排序时记录成片移动现象

16、。例9-4 设文件的记录key集合k=50,36,66,76,95,12,25,36,24,08(n=10),选取增量序列为10/2=5、5/2=2、2/2=1。排序过程如下:序号:1 2 3 4 5 6 7 8 9 10 50 36 66 76 95 12 25 36 24 08,令:d=5,令:d=2,令:d=1,08 12 24 25 36 36 50 66 76 95(完毕)显然,Shell排序是非稳定排序。,Shell排序,2.算法描述void Shellsort(sqfile F)对顺序文件F按Shell方法排序的算法 int i,j,d=F.len/2;第一次增量 while(d

17、=1)for(i=d+1;i0)形成新的增量 从算法中看出,若将其中的d 改为1,基本上同直接插入排序算法。,Shell排序,Shell排序的算法分析目前还是一道数学难题,如何选择增量序列使得排序效率最高还无定论。选取增量序列的经验公式之一为:ds=2s-1,1s如n=100时,增量序列为:d6=63,d5=31,d4=15,d3=7,d2=3,d1=1此时算法的时间复杂度T(n)可达O(n1.5),强于O(n2)。9.3 交换排序 本节讨论借助记录“交换”进行的排序方法(Exchange Sort),即“起泡”排序(Bubble Sort)和“快速”排序(Quick Sort)。9.3.1

18、起泡排序设待排文件f=(R1 R2Rn),相应key集合k=k1 k2kn。1.排序方法 从k1起,两两key比较,逆序时交换,即:k1k2,若k1k2,则R1 R2;k2k3,若k2k3,则R2 R3;kn-1kn,若kn-1kn,则Rn-1 Rn。经过一趟比较之后,最大key的记录沉底,类似水泡。接着对前n1个记录重复上述过程,直到排序完毕。,起泡排序,注意:在某趟排序的比较中,若发现两两比较无一记录交换,则说明文件已经有序,不必进行到最后两个记录的比较。例9-5 设记录key集合k=50,36,66,76,95,12,25,36,排序过程如下:,排序完毕,K503666769512253

19、6,从此例可以看出,起泡排序属于稳定排序。,起泡排序,2.算法描述void Bubsort(sqfile F)对顺序文件起泡排序的算法 int i,flag;flag为记录交换的标记 Retype temp;for(i=F.len;i=2;i-)最多n1趟排序 flag=0;for(j=1;jF.Rj+1.key)两两比较 temp=F.Rj;Rj Rj+1 F.Rj=F.Rj+1;F.Rj+1=temp;flag=1;if(flag=0)break;无记录交换时排序完毕,起泡排序,3.算法分析 设待排文件长度为n,算法中总的key比较次数为C。若文件正序,第一趟就无记录交换,退出循环,Cmi

20、n=n1=O(n);若文件逆序,则需n1趟排序,每趟key的比较次数为i1(2in),故:同理,记录的最大移动次数为:故起泡排序的时间复杂度T(n)=O(n2)。,9.3.2 快速排序,快速排序是对起泡排序的一种改进,目的是提高排序的效率。1.排序方法 经过key的一趟比较后,确定某个记录在排序后的最终位置。设待排文件的key集合k=k1 k2kikjkn-1 kn,对k中的k1,称作枢轴(Pivot)或基准。(1)逆序比较:k1kn,若k1kn,则k1不可能在kn位置,k1kn-1,直到有个kj,使得k1kj,则k1有可能落在kj位置,将kjk1位置,即key比基准(k1)小的记录向左移。(

21、2)正序比较:k1k2,若k1k2,则k1不可能在k2位置,k1k3,直到有个ki,使得k1ki,则k1有可能落在ki位置,将ki kj位置(原kj已送走),即key比基准大的记录向右移。反复逆序、正序比较,当i=j时,i位置就是基准k1的最终落脚点(因为比基准小的key统统在其“左部”,比基准大的统统在其“右部”,作为基准的key自然落在排序后的最终位置上),并且k1将原文件分成了两部分:对k和k”,套用上述排序过程(可递归),直到每个子表只含有一项时,排序完毕。,快速排序,例9-6 设记录的key集合k=50,36,66,76,36,12,25,95,每次以集合中第一个key为基准的快速排

22、序过程如下:,k=50 36 66 76 36 12 25 95,25 36 12 36 50 76 66 95,12 25 36 36,36 36,66 76 95,排序完毕,2.算法描述,关键是写出对一个子表的一趟快排函数。主函数可递归,也可非递归。下面写出非递归算法。typedef struct 栈元素类型 int low,high;当前子表的上下界 stacktype;int qkpass(sqfile F,int low,int high)对子表(RlowRhigh)一趟快排算法 int i=low,j=high;keytype x=F.Rlow.key;存入基准key F.R0=F

23、.Rlow;存入基准记录 while(i=F.Ri.key)i+;正序比较 if(ij)F.Rj=F.Ri;比x大的key右移 F.Ri=F.R0;基准记录存入第i位置 return(i);返回基准位置,算法描述,void qksort(sqfile F)对文件F快速排序的算法(非递归)int i,low,high;stacktype u;栈元素 Clearstack(S);置栈空 u.low=1;u.high=F.len;Push(S,u);排序文件上下界初值进栈 while(!Emptystack(S)u=Pop(S);退栈 low=u.low;high=u.high;当前表的上下界 wh

24、ile(lowhigh)i=qkpass(F,low,high);对当前子表的一趟快排 if(i+1high)u.low=i+1;u.high=high;Push(S,u);i位置的右部上下界进栈 high=i-1;排当前左部,3.算法分析,设待排文件F=(R1 R2Rn),第一次调用算法qkpass()后的F为(R1Ri-1)Ri(Ri+1Rn),耗时为Cn。设两子表k和k”记录均等,约为n/2,则快速排序的时间复杂度可以简单统计如下:当 时,则:O(nlog2n)是目前效率最高的内排序时间复杂度。但这是假定每次调用qkpass()后将原表分成长度相等的两个子表时的情况。若文件F原本就正序或

25、逆序,每次调用一次qkpass()后,文件记录数只减少了一个,故此时T(n)=C(n+(n1)+1)=O(n2)。这是快速排序效率最差的情况。所以快速排序算法有待改进。,9.4 选择排序,选择排序(Selection Sort)是最符合人们思维习惯的一种排序方法。基本思路是每次从待排文件中挑选一个key值最小的(或最大的)记录放置于它应所在的位置。若待排文件长度n为,则选择n1次便达到排序目的。选择排序一般又分为“直接选择排序”和“堆选择排序”。9.4.1 直接选择排序1.排序方法 设待排文件F=(R1 R2Rn),相应key集合k=k1 k2kn。首先进行n1次key比较,选择一个最小的kj

26、(1jn),将R1与Rj互换,于是最小key记录落在R1位置;接着在余下的(R2 R3Rn)中选出key次小者,放置于R2位置,依此类推,当待选记录中只剩下一个时,排序完毕。例9-7 设key集合k=50,36,66,76,36,12。直接选择排序过程如下:,直接选择排序,12 36 66 76 36 50,12 36 36 76 66 50,12 36 36 50 66 76,12 36 36 50 66 76 排序完毕,k=50 36 66 76 36 12,12 36 66 76 36 50,2.算法描述,void Slectsort(sqfile F)对顺序文件F直接选择排序的算法 i

27、nt i,j,k;Retype temp;for(i=1;iF.len;i+)选择n1趟 j=i;j为本趟最小key的序号 for(k=i+1;k=F.len;k+)本趟选择 if(F.Rk.keyF.Rj.key)j=k;if(i!=j)temp=F.Ri;F.Ri=F.Rj;F.Rj=temp;3.算法分析 设排序文件的记录长度为n。算法中共进行了n1趟选择,每选择一个当前最小key的记录,要经过ni(1in1)次的key比较,故总的key比较次数C为:另外,当文件按key正序时,记录移动次数等于0;而逆序时,每趟选择后有3次记录移动,所以最多移动次数=3(n1)。故直接选择排序的时间复杂

28、度T(n)=O(n2)。从例9-7中可以看出,直接选择排序属于稳定排序。,9.4.2 堆选择排序,堆选择排序是J.Willioms(威廉姆斯)于1964年提出的一种排序效率较高、属于选择排序的方法。1.堆定义设文件F=(R1 R2Rn)的key集合k=k1 k2kn,当且仅当满足:kik2i ki k2ikik2i+1 ki k2i+1i=1,2n/2 时,称k为堆(或称文件F为堆)。若将k=k1 k2kn看作一棵完全二叉树,如图9.11:则堆上任一非叶节点,有kik2i、kik2i+1。此时,根节点k1的值最大,称为“大根堆”。若ki与k2i、k2i+1满足“”关系,则k1最小,称为“小根堆

29、”。,或,堆选择排序,例9-8 大根堆、小根堆的例子。设k1=95,76,66,50,36,12,25,36,k2=12,36,25,76,36,66,50,95,相应堆如图9.12:2.排序方法 设文件F的记录key集合k=k1 k2kn,对F排序(实际上是对k排序)分两步进行:(1)将k1 k2kn建成一个大根堆;(2)取堆的根(key最大者),然后将剩余的(n1)个key又调整为堆,再取当前堆的根(key次大者),直到所有key选择完毕。先讨论第(2)步。,大根堆,小根堆,堆选择排序,例9-9 对大根堆k1=95,76,66,50,36,12,25,36排序过程如图9.13:,堆选择排序

30、,结果:k1=12,25,36,36,50,66,76,95,堆选择排序,将新换上来的根所在的二叉树调整成堆时,根节点的左右子树已满足堆定义,此时要设计一个自堆顶到叶节点的调整二叉树为堆的算法,称之为“筛选”算法,它是堆排序的一个关键算法,堆排序的大部分工作依赖于筛选算法。筛选算法思路:设要调整成堆的完全二叉树如图9.14:其中s为当前根的序号。先将Rstemp,令j=s节点的左右孩子key最大者的序号。将temp.key与kj比较,若kjtemp.key,则Rj Rs。然后令s=j,j等于新s的左右孩子key最大者的序号,继续temp.key与kj的比较,直到某个kjtemp.key或已调整

31、到叶子层时,将temp送入最后一个s位置处,筛选算法结束。,筛选算法描述,void Adjust(sqfile F,int s,int n)将(F.RsF.Rn)调整成大根堆 Retype temp;int j;temp=F.Rs;暂存F.Rs j=2*s;令j为s节点的左子序号 while(jF.Rj.key)j+;令j为s的左右孩子key最大者的序号 if(F.Rj.keytemp.key)F.Rs=F.Rj;Rj Rs s=j;j=2*s;置新的调整点 else break;调整完毕,退出循环 F.Rs=temp;最初的根回归,堆选择排序,再讨论第(1)步,将F=(R1 R2Rn)建成堆

32、。方法是将F看作是一棵完全二叉树,从最后一个有孩子的节点起,反复调用筛选算法,逆序向根逐步将F调整成堆。例9-10 设排序前文件的关键字集合k=50,36,66,76,95,12,25,36,n=8。根据二叉树性质5,n号节点的父节点序号为n/2=4,即从第4号节点起,逆序(4,3,2,1)到根,调用筛选算法,逐步求堆。过程如图9.15:,3.堆排序算法,void Heapsort(sqfile F)对顺文件F的堆排序算法 int i;Retype temp;for(i=F.len/2;i=1;i-)Adjust(F,i,F.len);调整(RiRn)为堆 for(i=F.len;i=2;i-

33、)选择n1次 temp=F.R1;根与当前最后一个节点互换 F.R1=F.Ri;F.Ri=temp;Adjust(F,1,i-1);互换后再建堆 4.算法分析设待排文件长度为n,相应n个节点的完全二叉树如图9.16:,堆排序算法分析,根据第六章二叉树性质4,n个节点的完全二叉树的深度:对筛选算法Adjust():若从根向下调整完全二叉树为堆,key比较次数最多为2(k1)(while循环里有2次key比较),则有:,堆排序算法分析,堆排序算法Heapsort():第一个for循环中,每个有孩子节点的子树都要调用一次筛选算法Adjust(),如表9.1:所以,所有有孩子节点的子树调整成堆的key

34、比较次数C为:,堆排序算法分析,C:2k-112k-222k-33.22(k-2)21(k-1),根据二叉树性质2,有n2k-1-1,即n2k-1,故上式:C=2(22k1-k-1)2(2n-k-1)4n。,堆排序算法分析,第二个for循环中,共选择了n1次,每次选择后调用Adjust()再建堆的key比较次数2log2n,故此循环的时间复杂度为(n-1)2log2n。所以,堆排序的时间复杂度:是一种效率较高的内排序方法。另外,堆排序是非稳定排序。9.5 归并排序 归并排序(Merge Sort)是采用合并的方法对文件进行排序,这也是外排序经常采用的方法。讨论二路归并排序。1.排序方法 设待排

35、文件F=(R1 R2Rn),先将每个Ri(1in)看作一个子文件,然后通过key的比较两两归并,得到 个长度为2的有序子文件,再两两归并,直到得到一个长度为n的有序文件为止。在归并过程中,需要设置一个辅助文件F1。开始时,F为源文件,F1为目标文件,将F归并到F1;然后又将F1作为源文件,F作为目标文件,再将F1归并到F,如此反复,最终排序结果仍在F中。,归并排序,例9-11 设文件F的记录key集合k=50,36,66,76,95,12,25,36,对F进行二路归并排序的过程如下:,F:(50 36 66 76 95 12 25 36),F1:50 36 66 76 95 12 25 36,

36、F:36 50 66 76 12 95 25 36,F1:36 50 66 76 12 25 36 95,F:12 25 36 36 50 66 76 95 完毕,2.算法描述 二路归并排序的算法实现分三个函数来完成。,归并排序,(1)相邻两个子文件的归并void Tmerge(sqfile F,sqfile F1,int s,int m,int t)相邻两个子文件的归并算法 int i,j,k,r;i=s;j=m+1;扫描指针初值 k=s;k为目标文件的记录指针 while(i=m)复制子文件剩余部分,源:Rs Rs+1 Rm Rm+1 Rm+2 Rt i j,目标:R1s R1s+1 R1

37、t,归并排序,(2)对源文件的一趟的二路归并设当前源文件F中各子文件的长度为len(最后一个子文件的长度可能不是len),文件总长为n,对F一趟的二路归并排序示意如下:void mpass(sqfile F,sqfile F1,int len)对子文件长度=len的源文件F一趟归并 int i=1,j;i为第一个子文件的起点 while(i+2*len-1n)当前长度=len的两子文件存在时 Tmerge(F,F1,i,i+len-1,i+2*len-1);对当前两子文件归并 i=i+2*len;i指向下一对子文件起点 if(i+len-1n)剩下两子文件后一个长度小于len时 Tmerge(

38、F,F1,i,i+len-1,n);最后两子文件的归并 else for(j=i;j=n;j+)最后一个子文件复制到F1中 F1.Rj=F.Rj;,F:RiRi+len-1 Ri+lenRi+2len-1 Ri+2lenR.,F1:R1i.R1i+2len-1 R1i+2len.,归并排序,(3)源文件的二路归并排序 借助于辅助文件F1,在F与F1之间来回调用mpass()函数,实现对F排序。void Mergesort(sqfile F)对文件F二路归并排序的算法 int len=1;sqfile F1;辅助文件 while(lenn)mpass(F,F1,len);F归并到F1 len=2

39、*len;新的子文件长度 mpass(F1,F,len)F1归并到F len=2*len;3.算法分析设待排文件F长度为n。从Mergesort()中看出,归并初始,子文件长度len=1;第1趟归并后,len=21;第2趟归并后,len=22,第i趟归并后,len=2i。当2in 时,归并过程结束,归并次数。另外,进行某趟归并时,mpass()的时间复杂度为O(n)。故二路归并排序的。归并排序属于稳定排序。,9.6 基数排序,前面讨论的排序方法都是对记录的单key排序,有时记录存在多个key,或是key由若干位组成,这时对文件排序可借助于基数排序(Radix Sort)方法。讨论最低位优先法(

40、LSD)方法的算法实现。设待排文件F=(R1Rn)为单链表结构,每个记录Ri(1in)对应的节点为:其中kd+1存放Ri的d位key,即k1,k2,kd;info为记录的其它信息域(泛指);next为指向Ri+1的指针,Rn的next=。为讨论方便,设key的基数为10,即ki的取值状态为:0|1|2|3|8|9。排序过程中,设置10个队列(或称为桶),其队头、队尾指针存入2个指针数组f10、e10,fi、ei(0i9)分别为第i队列的队头、队尾指针,初值为空。排序分两个步骤:分配;收集。举例说明。,基数排序,例9-14 设key的位数d=3。待排文件的链表结构如图9.13(记录其它信息inf

41、o舍去):(1)第1趟按k3排序(分配、收集),e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,(按k3有序),基数排序,(2)第2趟按k2排序,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,f0=f1=f2 f3 f4 f5 f6 f7 f8 f9,(按k2 k3有序),基数排序,(3)第3趟按k1排序,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,(按k1k2k3有序),2.算法描述,#define d 6 key的位数#defin

42、e r 10 当前key的基数typedef struct node 存放记录的节点类型 keytype kd+1;记录的key other info;记录其它域 struct node*next;Rnode,*Rlink;void Radixsort(Rlink F)对指针F所指的记录链表基数排序 Rlink p,t,fr,er;int i,j;if(F-next=NULL)return;空表返回 for(i=d;i=1;i-)d趟的分配与收集 for(j=0;jnext;while(p)本趟分配 j=ord(p-ki);取记录第i位key的序号 if(fj=NULL)fj=p;p节点进队

43、else ej-next=p;ej=p;p=p-next;,算法描述,本趟收集 for(j=0;!fj;j+);找第1个非空队列 F-next=fj;置本趟排序后的第1节点 t=ej;t为当前非空队列尾指针 while(jnext=fj;t=ej;收集时的链接 t-next=NULL;表尾置空 3.算法分析设待排链表长度为n。算法Radixsort()共进行了d 趟的“分配”与“收集”。每趟分配中,while循环的次数为n;每趟收集中,找非空队列以及非空队列的收集共进行了r次,所以基数排序的时间复杂度为O(d(n+r)。它不但依赖于n,还与key的位数d和基数r有关。基数排序属于稳定排序。(外排序略),收集,F-next=fj,fj,fj,fj,ej,ej,ej,ej,第九章小结,排序,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 在线阅读 > 生活休闲


备案号:宁ICP备20000045号-1

经营许可证:宁B2-20210002

宁公网安备 64010402000986号