数据结构排序.ppt

《数据结构排序.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,第九章小结,排序,