yA数据结构PPT教学课件第9章排序

《yA数据结构PPT教学课件第9章排序》由会员分享，可在线阅读，更多相关《yA数据结构PPT教学课件第9章排序（106页珍藏版）》请在金锄头文库上搜索。

1、第第9 9章章 排序排序yA数据结构PPT教学课件-第9章排序Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望第第9 9章章 排序排序第第9章章排序排序9.1 排序基本概念排序基本概念排序（sorting）又称分类,意指把一批杂乱无章的数据序列重新排列成有序序列。按待排序的记录的数量多少,排序过程中涉及的存储介质不同,排序方法分为两大类:内部排序和外部排序。内部排序是指待排序的记录存放在计算机内存之中;外部排序是指待排序的记录数量很大,以至于内存容纳不下而存放在外存储器之中,排序过程

2、需要访问外存。排序的依据可以是记录的主关键字,也可以是次关键字,甚至是若干数据项的组合。为了讨论方便,把排序所依据的数据项统称排序关键字,简称关键字。第第9 9章章 排序排序假设含有n个记录的序列为R1,R2,Rn,其相应的关键字序列为K1,K2,Kn,所谓排序就是将记录按关键字非递减(或非递增)的顺序重新排列起来。在待排序的记录中若有多个相同的关键字,在用某种方法排序之后,这些关键字相同的记录相对先后次序不变,则称这种排序方法是稳定的;否则是不稳定的。本章所介绍的内部排序方法包括插入排序、交换排序、选择排序、归并排序和基数排序。前四类排序是通过比较关键字的大小决定记录先后次序,也称为比较排序

3、。基数排序是不经关键字比较的排序方法。为了讨论方便,在此把排序关键字假设为整型。记录的结构定义为:第第9 9章章 排序排序structnodeintkey;/*排序关键字域*/intoth;/*其它域,根据需要自己设定*/第第9 9章章 排序排序9.2 插入排序插入排序 9.2.1 直接插入排序直接插入排序直接插入排序（straightinsertionsort）是一种最简单的排序方法。它的基本操作是将一个记录插入到一个长度为m（假设）的有序表中,使之仍保持有序,从而得到一个新的长度为m1的有序表。算法思路:设有一组关键字K1,K2,Kn,排序开始就认为K1是一个有序序列;让K2插入上述表长为

4、1的有序序列,使之成为一个表长为2的有序序列;然后让K3插入上述表长为2的有序序列,使之成为一个表长为3的有序序列;依次类推,最后让Kn插入上述表长为n-1的有序序列,得一个表长为n的有序序列。第第9 9章章 排序排序第第9 9章章 排序排序例9.1设有一组关键字序列55,22,44,11,33,这里n=5,即有5个记录。如图9.1所示。请将其按由小到大的顺序排序在具体实现Ki向前边插入时,有两种方法。一种方法是让Ki与K1,K2,顺序比较;另一种方法是Ki与Ki-1,Ki-2倒着比较。这里选用后一种方法。用一维数组r做存储结构,n表示记录个数,MAXSIZE为常量，且MAXSIZEn。则算法

5、如下:算法9.1voidstinsort(structnoderMAXSIZE,intn)for(i=2;ir0.key)rj+1=rj;j-;rj+1=r0;/*将r0即原ri记录内容,插到rj后一位置*/*stinsort*/此算法外循环n-1次,在一般情况下内循环平均比较次数的数量级为(n),所以算法总时间复杂度为(n2)。由于比较过程中,当Kj与K0相等时并不移动记录,因此直接插入排序方法是稳定的。直接插入排序也可用单链表做存储结构。第第9 9章章 排序排序当某结点i的关键字Kj与前边有序表比较时,显然先与K1比较,再与K2比较,即从链表表头结点开始向后逐一比较更合适。另外,直接插入排

6、序在原关键字序列基本有序或n值较小时,它是一种最常用的排序方法,它的时间复杂度接近于O(n)。但是,当n值又较大时,此方法就不再适用。第第9 9章章 排序排序9.2.2 折半插入排序折半插入排序当直接插入排序进行到某一趟时,对于ri.key来讲,前面i-1个记录已经按关键字有序。此时不用直接插入排序的方法,而改为折半查找,找出ri.key应插的位置,然后插入。这种方法就是折半插入排序（binaryinsertionsort）。算法如下:算法9.2voidbinasort(structnoderMAXSIZE,intn)for(i=2;i=n;i+)ZK(r0=ri;l=1;h=i-1;第第9

7、9章章 排序排序while(l=h)mid=(l+h)/2;if(r0.key=l;j-)rj+1=rj;rl=r0;/*binasort*/第第9 9章章 排序排序9.2.3 希尔排序希尔排序希尔排序（shellsort）是D希尔（D.L.Shell）提出的“缩小增量”的排序方法。它的作法不是每次一个元素挨一个元素的比较,而是初期选用大跨步（增量较大）间隔比较,使记录跳跃式接近它的排序位置;然后增量缩小;最后增量为1,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。算法思路:先取一个正整数d1(d1n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成一

8、组,然后在各组内进行插入排序;然后取d2(d2=1),即所有记录成为一个组为止。一般选d1约为n/2,d1为d1/2,d3为d1/2,d1=1。第第9 9章章 排序排序例92有一组关键字76,81,60,22,98,33,12,79,将其按由小到大的顺序排序。这里n=8,取d1=4,d2=2,d3=1,其排序过程如图9.2所示。算法实现见算法9.3。算法9.3voidshellsort(structnoderMAXSIZE,intn)k=n/2;/*k值代表前文中的d值*/while(k=1)for(i=k+1;ir0.key)&(j=0)rj+k=rj;j=j-k;rj+k=r0;ZK)k=

9、k/2;ZK)/*shellsort*/第第9 9章章 排序排序第第9 9章章 排序排序此算法外层循环是增量由n/2逐步缩小到的循环。for所构成的循环是针对某一特定的增量k,进行大跨步跳跃式的插入排序。例如k=2时,关键字分成二组,见图9.2的第2行,其中第1组是76,12,98,60,排序后的结果为12,60,76,98,插入操作如下:i=3K1=76有序,K3=12向前插;i=512,76有序,K5=98不移动;i=712,76,98有序,K7=60向前插;第第9 9章章 排序排序第2组是33,22,81,79,排序后的结果为22,33,79,81,插入操作如下:HT5”SSi=4K2=

10、33有序,K2=22向前插;i=622,33有序,K6=81不移动;i=822,33,81有序,K8=79向前插;对 整 个 文 件 来 说 ,排 序 结 果 实 际 上 为 :12,22,60,33,76,79,98,81。当K=1时,此算法就等同于直接插入排序方法。由于前边大增量的处理,使关键字大体有序,因此最后一趟排序移动的记录少,处理速度快。第第9 9章章 排序排序希尔排序的分析是一个复杂的问题,因为它的时间是所选定的“增量序列”的函数,这涉及到数学上一些尚未解决的难题。到目前为止,没有人找到一种最好的增量序列。有人在大量实验基础上推导出,希尔排序的时间复杂度为O(n1.3）。如果对关

11、键字序列6,7,51,2,52,8进行希尔排序,可以看出希尔排序是不稳定的。第第9 9章章 排序排序9.3 交换排序交换排序9.3.1 冒泡排序冒泡排序冒泡排序(bubblesort)是一种人们熟知的、最简单的交换排序方法。在排序过程中,关键字较小的记录经过与其它记录的对比交换,像水中的气泡向上冒出一样,移到序列的首部,故称此方法为冒泡排序法。排序的算法思路是:(1) 让j取n至2, 将rj.key与rj-1.key比较, 如果rj.keyi;j-)if(rj.keyrj-1.key)第第9 9章章 排序排序第第9 9章章 排序排序x=rj;rj=ri;ri=x;tag=1;ZK)i+;whi

12、le(tag=1&in);/*bubblesort*/算法中tag为标志变量,当某一趟处理过程中未进行过记录交换时,tag值应为0；若发生过交换,则tag值为1。所以外循环结束条件是:或者tag=0,已有序;或者i=n,已进行了n-1趟处理。该算法的时间复杂度为O(n2)。但是,当原始关键字序列已有序时,只进行一趟比较就结束,此时时间复杂度为O(n)。第第9 9章章 排序排序9.3.2 快速排序快速排序快速排序由霍尔(Hoare)提出,它是一种对冒泡排序的改正。由于其排序速度快,故称快速排序(quicksort)。快速排序方法的实质是将一组关键字K1,K2,Kn进行分区交换排序。其算法思路是:

13、（1）以第一个关键字K1为控制字,将K1,K2,Kn分成两个子区,使左区所有关键字小于等于K1,右区所有关键字大于等于K1,最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。（2）将右区首、尾指针(记录的下标号)保存入栈,对左区进行与第（1）步相类似的处理,又得到它的左子区和右子区,控制字居中。第第9 9章章 排序排序（3）重复第（1）、（2）步,直到左区处理完毕。然后退栈对一个个子区进行相类似的处理,直到栈空。由以上三步可以看出:快速排序算法总框架是进行多趟的分区处理;而对某一特定子区,则应把它看成又是一个待排序的文件,控制字总是取子区中第一个记录的关键字。现在设计一个函数ho

14、are,它仅对某一待排序文件进行左、右子区的划分,使控制字居中;再设计一个主体框架函数quicksort,在这里多次调用hoare函数以实现对整个文件的排序。例9.4HT设有一组关键字46,56,14,43,95,19,18,72,这里n=8。试用快速排序方法由小到大进行排序。1)分区处理函数hoare第第9 9章章 排序排序思路:首先用两个指针i、j分别指向首、尾两个关键字,i=1,j=8。第一个关键字46作为控制字,该关键字所属的记录另存储在一个x变量中。从文件右端元素rj.key开始与控制字x.key相比较,当rj.key大于等于x.key时,rj不移动,修改j指针,j-,直到rj.ke

15、yx.key,把记录ri移到文件右边j所指向的位置;再到文件右边修改j指针,j-。重复上面的步骤,直到i=j,此处就是控制字记录x所在的位置。第第9 9章章 排序排序至此将文件分成了左、右两个子区,其具体操作见图9.4。算法如算法9.5（假设某区段文件,指向第一个记录的指针为l,指向最后一个记录的指针为h）。算法9.5inthoare(structnoderMAXSIZE,intl,inth)i=1;j=h;x=ri;dowhile(i=x.key)j-;if(ij)ri=rj;i+;第第9 9章章 排序排序第第9 9章章 排序排序while(ij)&(ri.key=x.key)i+;if(i

16、=j)rj=ri;j-;while(ij);ri=x;return(i);/*hoare*/2）快速排序主体框架算法对一个文件,令l=1,h=n,调用hoare,求出i;然后右子区l=i+1,h=n,入栈,对左子区令l=1,h=i-1,再次调用hoare,如此反复,直到全部文件记录处理完毕。图9.5中第1行表示对例9.4的数据进行过一次分区处理之后的结果,在此基础上经过多次调用hoare后,最后得出第5行的结果。第第9 9章章 排序排序第第9 9章章 排序排序下面给出快速排序的递归算法和非递归算法。非递归算法:算法9.6void quicksort1(struct node r MAXSIZE

17、 , int n) /*intsn2;辅助栈s*/l=1;h=n;tag=1;top=0;dowhile(lh)i=hoare(r,l,h);top+;stop0=i+1;stop1=h;h=i-1;第第9 9章章 排序排序elsel=stop0;h=stop1;top-;while(tag=1);/*quicksort1*/递归算法:算法9.7voidquicksort2(structnoder,intl,inth)if(lh)i=hoare(r,l,h);/*划分两个区*/第第9 9章章 排序排序quicksort2(r,l,i-1);/*对左分区快速排序*/quicksort2(r,i+

18、1,h);/*对右分区快速排序*/*quicksort2*/在主程序调用非递归算法比较简单易懂。若要调用递归算法,因函数的形参不同,需做预处理。主程序的主要操作如下:调用递归函数调用非递归函数creat(r,n);creat(r,n);l=1;h=n;quicksort1(r,n);quicksort2(r,l,h);输出r;输出r;第第9 9章章 排序排序3）快速排序算法空间时间及稳定性分析快速排序的非递归算法引用了辅助栈, 它的深度为log2n。假设每一次分区处理所得的两个子区长度相近,那么可入栈的子区长度分别为:n/21,n/22,n/23,n/2k,又因为n/2k=1,所以k=log2

19、n。分母中2的指数恰好反映出需要入栈的子区个数,它就是log2n,也即栈的深度。在最坏情况下,比如原文件关键字已经有序,每次分区处理仅能得到一个子区。可入的子区个数接近n,此时栈的最大深度为n。快速排序主体算法时间运算量约O(log2n),划分子区函数运算量约O(n),所以总的时间复杂度为O(nlog2n),它显然优于冒泡排序O(n2)。可是算法的优势并不是绝对的,试分析,当原文件关键字有序时,快速排序时间复杂度是O(n2),这种情况下快速排序不快。第第9 9章章 排序排序而这种情况的冒泡排序是O(n),反而很快。在原文件记录关键字无序时的多种排序方法中,快速排序被认为是最好的一种排序方法。例

20、9.5试对6,7,51,2,52,8进行快速排序。排序过程简述如下:67512528初始状态527516782525167825251678最后状态第第9 9章章 排序排序9.4 选择排序选择排序9.4.1 简单选择排序简单选择排序简单选择排序(simpleselectionsort)也是直接选择排序。此方法在一些高级语言课程中做过介绍,是一种较为容易理解的方法。对于一组关键字K1,K2,Kn,将其由小到大进行简单排序的具体思路是:首先从K1,K2,Kn中选择最小值,假如它是Kz,则将Kz与K1对换;然后从K2,K3,Kn中选择最小值Kz,再将Kz与Kz对换;如此进行选择和调换n-2趟。第(n

21、-1)趟,从Kn-1、Kn中选择最小值Kz,将Kz与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成的。该算法的时间复杂度为O(n2)。第第9 9章章 排序排序由此可见,对于n个记录的关键字,需要处理n-1趟;而在每趟之中,又有一个内循环。图9.6是一个有5个关键字3,4,1,5,2的简单选择排序过程的示意图。假设用变量z记下较小值的下标,则算法如算法9.8。算法9.8voidsisort(structnoderMAXSIZE,intn)for(i=1;in;i+)z=i;for(j=i+1;j=n;j+)第第9 9章章 排序排序第第9 9章章 排序排序if(rj

22、.keyrz.key)z=j;x=ri;ri=rz;rz=x;/*sisort*/第第9 9章章 排序排序9.4.2 堆排序堆排序除了简单选择排序之外,还有树形选择排序(锦标赛排序)。1964年威洛姆斯(J.Willioms)提出了进一步改正的排序方法,即堆排序(heapsort)。堆是n个元素的有限序列k1,k2,kn,它当且仅当满足如下关系:ki=k2iki=k2i+1i=1,2,这是一个上小、底大的堆。若是一个上大、底小的堆,只需把“=”即可。堆是一种数据元素之间的逻辑关系,常用向量做存储结构。对于第6章中介绍的满二叉树,当对它的结点由上而下,第第9 9章章 排序排序自左至右编号之后,编

23、号为i的结点是编号为2i和2i+1结点的双亲。反过来讲,结点2i是结点i的左孩子,结点2i+1是结点i的右孩子。图9.7表示完全二叉树和它在向量中的存储状态。结点编号对应向量中的下标号。用堆的概念分析向量中的数据,它显然满足（上小、底大）堆的关系。不难看出,满足堆的逻辑关系的一组数据,可画成二叉树的形状,并且它是一棵完全二叉树树形。因此,也可借助完全二叉树来描述堆的概念。若完全二叉树中任一非叶子结点的值小于等于（或大于等于）其左、右孩子结点的值,则从根结点开始按结点编号排列所得的结点序列就是一个堆。在图9.8中(a)、(c)是堆,(b)、(d)不是堆。第第9 9章章 排序排序第第9 9章章 排

24、序排序第第9 9章章 排序排序堆排序的思路是:把n个记录存于向量r之中,把它看成完全二叉树,此时关键字序列不一定满足堆的关系。堆排序大体分两步处理。(1)初建堆。从堆的定义出发,当i=1,2,n/2时应满足ki=k2i和ki=k2i+1。所以先取i=n/2(它一定是第n个结点双亲的编号),将以i结点为根的子树调整为堆;然后令i=i-1,将以i结点为根的子树调整为堆。此时可能会反复调整某些结点,直到i=1为止,堆初步建成。(2)堆排序。首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置,然后恢复堆。因为经过第一步输出堆顶元素的操作后,往往破坏了堆关系,所以要恢复堆;重复执行输出

25、堆顶元素、堆尾元素上移和恢复堆的步骤,直到全部元素输出完为止。第第9 9章章 排序排序例 9.6设 有 n个 记 录 (n=8)的 关 键 字 是46,55,13,42,94,17,5,80,试对它们进行堆排序。第一步:初建堆。因为n=8,所以从i=4开始,见图9.9。调整成为堆是一个较复杂的过程,当i值确定之后用kz记下ki的值,用kz分别与k2i和k2i+1比较,可理解为kz值与结点i的左、右孩子的关键字比较。如果一开始kz比k2和k2+1均小,则不进行任何调整。例如i=4时,k4k8(4280),就不用调整,见图9.9(a)。如果结点i的某一个孩子的关键字小于kz,则把这个孩子结点移上来

26、。如果结点i的两个孩子的关键字都小于kz,那么将两个孩子中较小的一个调整上来。第第9 9章章 排序排序第第9 9章章 排序排序如果结点i的两个孩子的关键字都小于kz,那么将两个孩子中较小的一个调整上来。在图9.9(c)中,i=1时,k2、k3都小于kz(42,546),则让k3(即5)移上去。此时需要让kz与更下一层的左、右孩子的关键字进行比较,直到某一层的左、右孩子的关键字不小于kz,或左、右孩子不存在为止。此时将kz填入适当位置,使之成为堆。在图9.9(c)中,先把5调整上来,然后把13移到5原来的位置上,最后将kz(即46)填到13原来的位置上。第二步:堆排序。这是一个反复输出堆顶元素,

27、将堆尾元素移至堆顶,再调整恢复堆的过程。恢复堆的过程与初建堆中i=1时所进行的操作完全相同。请注意:每输出一次堆顶元素，堆尾的逻辑位置退1，直到堆中剩下一个元素为止。排序过程如图9.10所示。第第9 9章章 排序排序堆排序算法实现:由上述可知,有一种操作过程（即调整恢复堆）要被多次反复调用,那就是当i值确定之后,以ki为比较参照值,与它的左、右孩子的关键字比较和调整,使得以结点i为根的子树成为堆,因此把这个过程设计成一个函数heap。另外,当然还需再设计一个主体算法,使在初建堆阶段,让i从n/2变化到1,循环调用函数heap。而在堆排序阶段,每输出一次堆顶元素同时将堆尾元素移至堆顶之后,就调用

28、一次heap函数来恢复堆。主体算法由函数heapsort实现。以编号为i的结点为根,调整为堆的算法为:算法9.9第第9 9章章 排序排序第第9 9章章 排序排序voidheap(structnoderMAXSIZE,inti,intm)/*i是根结点编号,m是以i结点为根的子树的最后一个结点编号*/x=ri;j=2*i;/*x保存根记录内容,j为左孩子编号*/while(j=m)if(jrj+1.key)j+;/*当结点i有左、右两个孩子时,j取关键字较小的孩子结点编号*/if(rj.keym,以便结束循环*/第第9 9章章 排序排序ri=x;/*heap*/堆排序主体算法:算法9.10HTv

29、oidheapsort(structnoderMAXSIZE,intn)/*n为文件的实际记录数,r0没有使用*/for(i=n/2;i=1;i-)heap(r,i,n)/*初建堆*/for(v=n;v=2;v-)printf(%5d,r1.key);/*输出堆顶元素*/x=r1;r1=rv;rv=x;/*堆顶堆尾元素交换*/heap(r,1,v-1);/*本次比上次少处理一个记录*/printf(%5d,r1.key);/*heapsort*/第第9 9章章 排序排序在堆排序图示中,堆越画越小,实际上在r向量中堆顶元素输出之后并未删除,而是与堆尾元素对换。由图9.10可知输出的是一个由小到大

30、的升序序列,而最后r向量中记录的关键字从r1.key到rn.key是一个由大到小的降序序列。堆排序中heap算法的时间复杂度与堆所对应的完全二叉树的树深log2n+1相关。而heapsort中对heap的调用数量级为n,所以整个堆排序的时间复杂度为O(nlog2n)。在内存空间占用方面,基本没有额外的辅助空间,仅有一个x。现在来分析堆排 序 的 稳 定 性 问 题 。 设 有 一 组 关 键 字 :6,7,51,2,52,8,经排序后的结果是:2,52,51,6,7,8。本来51在前面,排序后52移到51的前面,所以说堆排序是不稳定的。堆排序的部分处理过程如图9.11所示。第第9 9章章 排序

31、排序第第9 9章章 排序排序9.5 归并排序归并排序归并排序(mergesort)是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序和两路归并排序；可用于内排序,也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。两路归并排序算法思路:（1）把n个记录看成n个长度为l的有序子表;（2）进行两两归并使记录关键字有序,得到n/2个长度为2的有序子表;（3）重复第（2）步，直到所有记录归并成一个长度为n的有序表为止。第第9 9章章 排序排序例9.7HT有一组关键字4,7,5,3,2,8,6,1,n=8,将其按

32、由小到大的顺序排序。两路归并排序操作过程如9.12所示,其中l为子表长度。初始47532861l=1第1趟47321l=2第2趟34571268l=4第1趟12345678l=n算法实现:此算法的实现不像图示那样简单,现分三步来讨论。首先从宏观上分析,先让子表表长l=1进行处理;不断地使l=2*L,进行子表处理,直到l=n为止,把这一过程写成一个主体框架函数mergesort。第第9 9章章 排序排序第第9 9章章 排序排序然后对于某确定的子表表长l,将n个记录分成若干组子表,两两归并,这里显然要循环若干次,把这一步写成一个函数mergepass,可由mergesort调用。最后再看每一组（一

33、对）子表的归并,其原理是相同的,只是子表表长不同。换句话说,是子表的首记录号与尾记录号不同,把这个归并操作作为核心算法写成函数merge,由mergepass来调用。主体框架算法描述如下:算法9.11voidmergesort(structnoderMAXSIZE,intn)/*r是包含有n个记录的原文件,归并过程中另需一个r2作为辅助存储空间*/l=1;/*子表初始长度*/第第9 9章章 排序排序while(l=2*l)/*剩下的记录数目大于两个子表时*/h1=i;mid=h1+l-1;h2=i+2*l-1;merge(r,r2,h1,mid,h2);i=i+2*l;/*跳过两个子表,指向新

34、的一对子表的首记录*/if(n-i+1)=l)/*剩下的记录数目小于一个子表时*/for(j=i;j=n;j+)r2j=rj;else/*剩下的记录数目大于一个,小于两个子表时*/h1=i;mid=h1+l-1;h2=n;merge(r,r2,h1,mid,h2);/*mergesort*/第第9 9章章 排序排序归并排序核心算法描述如下:算法9.13oid merge(struct node rMAXSIZE,struct node r2MAXSIZE,inth1,intmid,inth2)/*h1为第一个子表首元素的下标,mid为第一个子表未元素的下标,*/*h2为第二个子表未元素的下标*

35、/i=h1;j=mid+1;k=h1-1;/*k是r2的初始指针*/while(i=mid)&(j=h2)k=k+1;if(ri.key=rj.key)r2k=ri;i+;elser2k=rj;j+;第第9 9章章 排序排序while(i=mid)k+;r2k=ri;i+;while(j=h2)k+;r2=rj;j+;/*merge*/算法的最后两个while语句也可以改写成:if(i=mid)for(t=i;t=mid;t+)k+;r2k=rt;elsefor(t=j;t=h2;t+)k+;r2k=rt;第第9 9章章 排序排序9.6 基数排序基数排序基数排序(radixsort)是与前面所

36、介绍的各类排序方法完全不同的一种排序方法。前几节所介绍的排序方法主要是通过比较记录的关键字来实现的,而基数排序法不必经过关键字的比较来实现排序,而是根据关键字每个位上的有效数字的值,借助于“分配”和“收集”两种操作来实现排序的。本章假设记录的关键字为整型（实质上关键字并不限于整型）。基数排序有两种方法:一种方法是首先根据最高位有效数字进行排序,然后根据次高位有效数字进行排序,依次类推,直到根据最低位（个位）有效数字进行排序,产生一个有序序列。这种方法称最高位优先法(MostSignificantDigitFirst),简称MSD法。第第9 9章章 排序排序另一方法是首先根据关键字最低位（个位）

37、有效数字进行排序,然后根据次低位（十位）有效数字进行排序,依次类推,直到根据最高位有效数字进行排序,产生一个有序序列。这种方法称最低位优先法(LeastSignificantDigitFirst),简称LSD法。现用LSD法进行基数排序。假设有n个记录,其关键字在0999之间,每一位上有效数字值在09之间共10种可能性,则认为基数是10,在进行“分配”操作时涉及10个队列,即队列的个数与基数相同。此处关键字最多位数是3,那么就需进行3趟“分配”和“收集”操作。算法思路:第第9 9章章 排序排序1）第一趟“分配”,根据关键字个位有效数字,把所有记录分配到相应的10个队列中去。用f0,e0表示0号

38、队列的头、尾指针,f9,e9表示9号队列的头、尾指针。例如,关键字为184的记录就分配到4号队列中去。（2）第一趟“收集”把所有非空队列（10个队列中可能有空队）按队列号由小到大的顺序头、尾相接,收集成一个新的序列。此序列若观察其关键字的个位,则它是有序的;若观察其关键字的高位,则它尚处于无序状态。（3）以后各趟分别根据关键字的十位、百位有效数字重复第（1）、（2）步的“分配”与“收集”操作,最终得到一个按关键字由小到大的序列。例9.8有一组关键字278,109,063,930,589,184,505,269,008,083,将它们按由小到大的顺序排序。第第9 9章章 排序排序图9.13(a)

39、是待排序的关键字序列的初始状态。图9.13(b)是按每个关键字的个位有效数字将它们分配到相应的队列中去。例如,关键字008、278都分配到了8号队列中去,e8指向队尾,f8指向队头。图9.13(c)是将6个非空队列（0号,3号,4号,5号,8号,9号）头尾相接收集在一起之后得到的一个新的序列。图9.13(d)是按每个关键字十位上的有效数字重新将它们分配到相应的队列中去,例如,关键字589、184、083都分配到了8号队列中去。然后再次收集,形成如图9.13(e)所示的新的序列。图9.13(f)则是按百位上的有效数字分配之后的各队列状态。图9.13(g)则是再次收集后的结果,这也是基数排序所得到

40、的最终的有序序列。第第9 9章章 排序排序第第9 9章章 排序排序在本章前几节的讨论中,待排序的记录是用向量r做存储结构的。基数排序又是“分配”队列,又要“收集”起来,故适用于链表形式存储。本节不采用动态链表而仍用向量r存储（即一维数组）,让每个存放记录的数组元素增加一个指针域。此域为整型,用来存放该记录的下一个相邻记录所在数组元素的下标。这种结构称为静态链表结构。所谓队列的头、尾指针也是整型,它们记下可做某号队列队头或队尾元素的记录在数组r中的下标值。记录结构为:structnodeintkey;/*关键字域*/intoth;/*其它信息域*/intpoint;/*指针域*/第第9 9章章

41、排序排序基数排序算法:设n个待排序的记录存储在向量r中,限定关键字为整型并且有效数字位数d5;基数显然是10;10个队列的头指针、尾指针分别用向量f和e来表示,代表头指针的数组元素是f0,f1,f9,代表尾指针的数组元素分别是e0,e1,e2,e9,则算法描述如下:算法9.14intradixsort(structnoderMAXSIZE,intn)intf10,e10;for(i=1;in;i+)ri.point=i+1;rn.point=0;p=1;/*建立静态链表,p指向链表的第一个元素第第9 9章章 排序排序for(i=1;i=d;i+)/*下面是分配队列*/for(j=0;j10;j

42、+)fj=0;ej=0;while(p!KG-*2=0)k=yx(rp.key,i);/*取关键字倒数第i位有效数字*if(fk=0)fk=p;ek=p;*让头指针指向同一元素*elsel=ek;rl.point=p;ek=p;*在k号队列尾部入队*p=rp.point;*在r向量中,p指针向后移*第第9 9章章 排序排序*下面是收集*j=0;while(fj=0)j+;/*找第一个非空队列*p=fj;t=ej;*p记下队头做收集后的静态链表头指针*while(j10)j+;while(j10)&(fj=0)j+;if(fj!KG-*2=0)rt.point=fj;t=ej;*将前边一个非空队

43、列的队尾指针指向现在队头并记下现在队尾位置*第第9 9章章 排序排序rt.point=0;*这是一趟分配与收集之后的链表最后一个元素*/*fori*/return(p);/*基数排序结果p指向静态链表的第一个元素,即关键字最小的记录*/*radixsort*/分离关键字倒数第i位有效数字算法:第第9 9章章 排序排序算法9.15intyx(intm,inti)switch()case1:x=m%10;/*个位*case2:x=(m%100)/10;*十位*case3:x=(m%1000)/100;*百位*case4:x=(m%10000)/1000;*千位*return(x);/*yx*/第第

44、9 9章章 排序排序radixsort算法中基数为10,这里用rd表示它,最高有效数字位是4,这里用d表示,记录总数为n。基数排序时间复杂度为O(d(n+rd),这是因为总共循环d趟,每趟分配运算量数量级为O(n), 收集运算量数量级为O(rd), 所以总时间复杂度为O(d(n+rd)。它的空间占用情况是,向量r多了n个指针域,辅助空间为2rd个队列指针。基数排序是稳定的。第第9 9章章 排序排序.7 内部排序总结内部排序总结表9.1列出了8种排序方法的性能比较。（） 当问题的规模不大, 即待排序的记录数n不大时(n=50),可选用表中前三种排序方法之一。它们的时间复杂度虽为O(n2),但方法

45、简单易掌握。直接插入排序和冒泡排序在原文件记录按关键字“基本有序”时,排序速度比较快。其中直接插入排序更为常用。（）当n值很大,并不强求排序稳定性,并且内存容量不宽余时,应该选用快速排序或堆排序。一般来讲,它们排序速度非常快。但快速排序对原序列基本有序的情况,速度减慢接近O(n2),而堆排序不会出现最坏情况。第第9 9章章 排序排序第第9 9章章 排序排序（）当n值很大,对排序稳定性有要求,存储容量较宽余时,用归并排序最为合适。排序速度很快,并且稳定性好。（）当n值很大并且关键字位数较小时,采用静态链表基数排序不仅速度较快,并且稳定性好。第第9 9章章 排序排序9.8 有关排序算法的有关排序算

46、法的C语言源程序语言源程序本章介绍了多种算法,其中直接插入排序、折半插入排序、冒泡排序和简单选择排序的程序在各种程序设计语言中都有详细的介绍。这里我们提供希尔排序、快速排序、堆排序、归并排序和基数排序的程序清单（均已上机通过）,供大家在消化算法和实验时参考。structnode/*记录结构。为简化问题,设定记录中只含关键字*intkey;r20;第第9 9章章 排序排序main()oidprint(structnodea20,intn);intcreat();oidshell(structnodea20,intn);inthoare(structnodea20,intl,inth);oidqu

47、ick1(structnodea20,intn);oidquick2(structnodea20,intl,inth);oidheap(structnodea20,inti,intm);oidheapsort(structnodea20,intn);oidmerge(structnodea20,structnodea220,inth1,intmid,inth2);第第9 9章章 排序排序oidmergepass(structnodea20,structnodea220,intl,intn);oidmergesort(structnodea20,intn);intyx(intm,inti);in

48、tradixsort(structrnodea20,intn);intnum,l,h,c;structrnodes20;c=1;while(c!KG-*2=0)第第9 9章章 排序排序printf(主菜单);printf(1.输入关键字,以-9999表示结束。n);printf(2.希尔排序n);printf(3.非递归的快速排序n);printf(4.递归的快速排序n);printf(5.堆排序n);printf(6.归并排序n);printf(7.基数排序n);printf(输入选择(1-7,0表示结束):);第第9 9章章 排序排序scanf(%d,&c);switch(c)case1:

49、num=creat();print(r,num);break;case2:shell(r,num);print(r,num);break;case3:quick1(r,num);print(r,num);break;case4:l=0;h=num-1;quick2(r,l,h);printf(outputquick2sortresult:n);print(r,num);break;case5:heapsort(r,num);break;case6:mergesort(r,num);print(r,num);break;case7:radixsort(s,num);第第9 9章章 排序排序/*m

50、ainend*/oidprint(structnodea20,intn)*打印记录*inti;for(i=0;i=1;i-)ai.key=ai-1.key;k=n/2;while(k=1)for(i=k+1;ia0.key)&(j=0)aj+k.key=aj.key;j=j-k;aj+k=a0;第第9 9章章 排序排序k=k/2;for(i=0;in;i+)ai.key=ai+1.key;printf(输出希尔排序的结果:n);*shellend*inthoare(structnodea20,intl,inth)*分区处理函数*inti,j;structnodex;i=l;j=h;x.key=

51、ai.key;dowhile(i=x.key)j-;if(ij)ai.key=aj.key;i+;第第9 9章章 排序排序while(ij)&(ai.key=x.key)i+;if(ij)aj.key=ai.key;j-;while(ij);ai.key=x.key;return(i);*hoareend*oidquick1(structnodea20,intn)*非递归的快速排序主体函数*inti,l,h,tag,top;ints202;l=0;h=n-1;tag=1;top=0;dowhile(lh)第第9 9章章 排序排序i=hoare(a,l,h);top+;stop0=i+1;sto

52、p1=h;h=h-1;if(top=0)tag=0;elsel=stop0;h=stop1;top-;while(tag=1);第第9 9章章 排序排序printf(输出非递归快速排序的结果:n);*quick1end*oidquick2(structnodea20,intl,inth)*递归的快速排序主体函数inti;if(lh)i=hoare(a,l,h);quick2(a,l,i-1);quick2(a,i+1,h);*quick2end*第第9 9章章 排序排序oidheap(structnodea20,inti,intm)*调整堆的函数*structnodex;intj;x.key=

53、ai.key;j=2*i;while(j=m)if(jaj+1.key)j+;if(aj.key0;i-)ai.key=ai-1.key;for(i=n/2;i=1;i-)heap(a,i,n);printf(输出归并排序的结果:n);for(=n;=2;-)printf(%5d,a1.key);x.key=a1.key;a1.key=a.key;a.key=x.key;heap(a,1,-1);第第9 9章章 排序排序printf(%5d,a1.key);for(i=0;in;i+)ai.key=ai+1.key;*heapsortend*oidmerge(structnodea20,str

54、uctnodea220,inth1,intmid,inth2)*归并排序的核心算法*inti,j,k;i=h1;j=mid+1;k=h1-1;while(i=mid)&(j=h2)k=k+1;if(ai.key=aj.key)a2k.key=ai.key;i+;第第9 9章章 排序排序elsea2k.key=aj.key;j+;while(i=mid)k+;a2k.key=ai.key;i+;while(j=2*l)第第9 9章章 排序排序h1=i;mid=h1+l-1;h2=i+2*l-1;merge(a,a2,h1,mid,h2);i=i+2*l;if(n-i)=l)for(j=i;j=n

55、;j+)a2j.key=aj.key;elseh1=i;mid=h1+l-1;h2=n-1;merge(a,a2,h1,mid,h2);*mergepassend*第第9 9章章 排序排序oidmergesort(structnodea20,intn)*归并排序的主体函数intl;structnodea220;l=1;while(ln)mergepass(a,a2,l,n);l=2*l;mergepass(a2,a,l,n);l=2*l;printf(输出归并排序的结果:n);*mergesortend*第第9 9章章 排序排序intyx(intm,inti)*分离关键字倒数第i位有效数字的算

56、法*intx;switch(i)case1:x=m%10;break;case2:x=(m%100)/10;break;case3:x=(m%1000)/100;break;case4:x=(m%10000)/1000;return(x);/*yxend*第第9 9章章 排序排序structrnode/*基数归并时记录的结构*intkey;intpoint;intradixsort(structrnodea20,intn)*基数排序*intf11,e11,i,j,k,l,p,d,t;for(i=1;i=n;i+)ai.key=ri-1.key;ai.point=i+1;an.point=0;p

57、=1;printf(输入关键字有效位数dn);scanf(%d,&d);第第9 9章章 排序排序printf(输出基数排序的结果:n);for(i=1;i=d;i+)for(j=0;j=10;j+)fj=0;ej=0;while(p!KG-*2=0)k=yx(ap.key,i);if(fk=0)fk=p;ek=p;elsel=ek;al.point=p;ek=p;p=ap.point;j=0;第第9 9章章 排序排序while(fj=0)j+;p=fj;t=ej;while(j10)j+;while(j10)&(fj=0)j+;if(fj!KG-*2=0)at.point=fj;t=ej;at

58、.point=0;t=p;第第9 9章章 排序排序while(t!KG-*2=0)printf(%5d,at.key);t=at.point;printf(n);return(p);*radixsortend*第第9 9章章 排序排序9.9 多路归并用于外排序的简介多路归并用于外排序的简介本章前面讨论的排序方法统称为内部排序。整个排序过程中不涉及数据的内外存交换,待排序的记录存放在内存储器中。本节我们简单介绍一下大型文件的排序技术。由于文件很大,无法把整个文件的所有记录同时调入内存中进行排序,即无法进行内排序,从而需要研究外存设备上（文件）的排序技术,我们称这种排序为外排序。最常用的外排序方法

59、是多路归并法。这种方法基本上要经历两个阶段:第一阶段是把文件逐段输入到内存,用较好的内排序方法对这段文件进行排序。已排序的文件段通常称为归并段,且记作R。整个文件经过逐段排序后又逐段写回到外存上。第第9 9章章 排序排序这样,在外存上就形成了许多初始归并段。第二阶段是对这些初始归并段使用某种归并方法（如两路归并法）,进行多遍归并。最后在外存上形成一个排序的文件。下面以两路归并为例。设某一文件共有4500个记录,若磁带的读、写单位是250个记录的数据块,内存最多只能为外排序提供750个记录的空间,另外有一个磁盘用来暂存中间结果。排序过程如下:(1)每次从外存上输入3个数据块,共750个记录到内存

60、中进行内排序,得到6个初始归并段R1R6,把它们写回存放中间结果的磁盘上。(2)将供内排序的内存空间分成3个相等的部分,其中两部分作为两个输入缓冲区,另一个作为输出缓冲区。先归并R1和R2。在归并时,要利用输入缓冲区,归并后送输出缓冲区。第第9 9章章 排序排序当输出缓冲区装满250个记录后,就写回磁盘。如果归并期间某个输入缓冲区空了,就立即将同一归并段中下一块记录输入,继续进行归并,直到R1和R2归并成一个归并段为止。此新的归并段共有1500个记录。类似地,再归并R3和R4,R5和R6,形成3个都包含1500个记录的归并段。再利用内存的缓冲区将其中两个归并段进行归并,得到一个共3000个记录

61、的归并段。最后将这个归并段与剩下的另一个有1500个记录的归并段进行归并,就得到了所求的排序文件。图9.14反映了这个归并过程。第第9 9章章 排序排序第第9 9章章 排序排序对18块记录采用两路归并需进行三遍归并,总共需要读48块次,写48块次。显然,读/写时间是较多的。若采用六路归并,则一次就可以成功,只需读/写各18块次就行了。在归并外排序中需深入研究的问题是:(1)如何进行多路归并以减少文件归并的遍数。(2)如何更巧妙地运用内存的缓冲区,使输入/输出和CPU处理工作尽可能地并行操作。(3)研究较好的产生初始归并段的方法。磁带机上文件的排序,其操作的基本步骤与磁盘文件相类似。但因磁带机是

62、顺序存取设备,因此,读取信息块的时间与所读信息块的位置关系极大。第第9 9章章 排序排序故在磁带机上进行文件排序时,研究归并段信息块的分布是一个极为重要的问题。在磁带机上常用的排序方法是平衡归并排序和多阶段归并排序（即斐波纳契归并排序）。若有T台磁带机,则可进行T/2路的平衡归并排序。现以两路平衡归并排序为例进行说明。两路平衡归并的基本思想是:从两条输入磁带上平衡地取初始归并段到内存缓冲区,经过归并排序后,平衡分配、输出到另外两条空带（输出带）上。直到输入带上所有的归并段平衡地归并完为止。上述过程称为一趟归并。到下一趟时,输入带和输出带互相转换再逐个对归并段进行平衡归并,直到归并成一个归并段为止。第第9 9章章 排序排序设有6000个记录的文件,经内部排序后生成R1R6六个初始归并段,每段大小为1000个记录。归并前4台磁带机上归并段的分布如下:T1:R1R3R5T2:R2R4R6T3:空T4:空经过一趟两路平衡归并排序后,各磁带机上归并段分布如下:T1:空T2:空T3:R1-2R5-6T4:R3-4第第9 9章章 排序排序经第二趟外排序后得:T1:R1-4T2:R5-6T3:空T4:空经第三趟外排序后得:T1:空T2:空T3:R1-6T4:空