数据结构教学课件第章排序市公开课金奖市赛课一等奖课件.pptx

第第9 9章章 排序排序9.1 排序基本概念排序基本概念 9.2 插入排序插入排序 9.3 互换排序互换排序 9.4 选择排序选择排序 9.5 归并排序归并排序 9.6 基数排序基数排序 9.7 内部排序总结内部排序总结 9.8 相关排序算法相关排序算法C语言源程序语言源程序 9.9 多路归并用于外排序简介多路归并用于外排序简介第第9章章 排序排序返回主目录返回主目录第1页第1页第第9 9章章 排序排序第第9章章排序排序9.1排序基本概念排序（sorting）又称分类,意指把一批杂乱无章数据序列重新排列成有序序列。按待排序统计数量多少,排序过程中包括存放介质不同,排序方法分为两大类:内部排序和外部排序。内部排序是指待排序统计存放在计算机内存之中;外部排序是指待排序统计数量很大,以至于内存容纳不下而存放在外存放器之中,排序过程需要访问外存。排序依据能够是统计主关键字,也能够是次关键字,甚至是若干数据项组合。为了讨论方便,把排序所依据数据项统称排序关键字,简称关键字。第2页第2页第第9 9章章 排序排序假设含有n个统计序列为R1,R2,Rn,其相应关键字序列为K1,K2,Kn,所谓排序就是将统计按关键字非递减(或非递增)顺序重新排列起来。在待排序统计中若有多个相同关键字,在用某种办法排序之后,这些关键字相同统计相对先后顺序不变,则称这种排序办法是稳定;不然是不稳定。本章所简介内部排序办法包括插入排序、互换排序、选择排序、归并排序和基数排序。前四类排序是通过比较关键字大小决定统计先后顺序,也称为比较排序。基数排序是不经关键字比较排序办法。为了讨论以便,在此把排序关键字假设为整型。统计结构定义为:第3页第3页第第9 9章章 排序排序structnodeintkey;/*排序关键字域*/intoth;/*其它域,依据需要自己设定*/第4页第4页第第9 9章章 排序排序9.2 插入排序插入排序 9.2.1 直接插入排序直接插入排序直接插入排序（straightinsertionsort）是一个最简朴排序办法。它基本操作是将一个统计插入到一个长度为m（假设）有序表中,使之仍保持有序,从而得到一个新长度为m1有序表。算法思绪:设有一组关键字K1,K2,Kn,排序开始就认为K1是一个有序序列;让K2插入上述表长为1有序序列,使之成为一个表长为2有序序列;然后让K3插入上述表长为2有序序列,使之成为一个表长为3有序序列;依次类推,最后让Kn插入上述表长为n-1有序序列,得一个表长为n有序序列。第5页第5页第第9 9章章 排序排序第6页第6页第第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。则算法下列:算法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相等时并不移动统计,因此直接插入排序办法是稳定。直接插入排序也可用单链表做存储结构。第8页第8页第第9 9章章 排序排序当某结点i关键字Kj与前边有序表比较时,显然先与K1比较,再与K2比较,即从链表表头结点开始向后逐一比较更适当。另外,直接插入排序在原关键字序列基本有序或n值较小时,它是一个最惯用排序办法,它时间复杂度靠近于O(n)。但是,当n值又较大时,此办法就不再合用。第9页第9页第第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;第10页第10页第第9 9章章 排序排序while(l=h)mid=(l+h)/2;if(r0.key=l;j-)rj+1=rj;rl=r0;/*binasort*/第11页第11页第第9 9章章 排序排序9.2.3 希尔排序希尔排序希尔排序（shellsort）是D希尔（D.L.Shell）提出“缩小增量”排序办法。它作法不是每次一个元素挨一个元素比较,而是早期选取大跨步（增量较大）间隔比较,使统计跳跃式靠近它排序位置;然后增量缩小;最后增量为1,这样统计移动次数大大减少,提升了排序效率。希尔排序对增量序列选择没有严格要求。算法思绪:先取一个正整数d1(d1n),把所有统计分成d1个组,所有距离为d1倍数统计当作一组,然后在各组内进行插入排序;然后取d2(d2=1),即所有统计成为一个组为止。普通选d1约为n/2,d1为d1/2,d3为d1/2,d1=1。第12页第12页第第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=k/2;ZK)/*shellsort*/第14页第14页第第9 9章章 排序排序第15页第15页第第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向前插;第16页第16页第第9 9章章 排序排序第2组是33,22,81,79,排序后结果为22,33,79,81,插入操作下列:HT5”SSi=4K2=33有序,K2=22向前插;i=622,33有序,K6=81不移动;i=822,33,81有序,K8=79向前插;对 整 个 文 献 来 说,排 序 结 果 事 实 上 为:12,22,60,33,76,79,98,81。当K=1时,此算法就等同于直接插入排序办法。由于前边大增量处理,使关键字大体有序,因此最后一趟排序移动统计少,处理速度快。第17页第17页第第9 9章章 排序排序希尔排序分析是一个复杂问题,由于它时间是所选定“增量序列”函数,这涉及到数学上一些尚未处理难题。到当前为止,没有些人找到一个最好增量序列。有些人在大量试验基础上推导出,希尔排序时间复杂度为O(n1.3）。假如对关键字序列6,7,51,2,52,8进行希尔排序,能够看出希尔排序是不稳定。第18页第18页第第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)第20页第20页第第9 9章章 排序排序第21页第21页第第9 9章章 排序排序x=rj;rj=ri;ri=x;tag=1;ZK)i+;while(tag=1&in);/*bubblesort*/算法中tag为标志变量,当某一趟处理过程中未进行过统计互换时,tag值应为0；若发生过互换,则tag值为1。因此外循环结束条件是:或者tag=0,已有序;或者i=n,已进行了n-1趟处理。该算法时间复杂度为O(n2)。但是,当原始关键字序列已有序时,只进行一趟比较就结束,此时时间复杂度为O(n)。第22页第22页第第9 9章章 排序排序9.3.2快速排序快速排序由霍尔(Hoare)提出,它是一种对冒泡排序改正。由于其排序速度快,故称快速排序(quicksort)。快速排序办法实质是将一组关键字K1,K2,Kn进行分区互换排序。其算法思路是:（1）以第一个关键字K1为控制字,将K1,K2,Kn分成两个子区,使左区所有关键字小于等于K1,右区所有关键字不小于等于K1,最后控制字居两个子区中间适当位置。在子区内数据尚处于无序状态。（2）将右区首、尾指针(记录下标号)保存入栈,对左区进行与第（1）步相类似处理,又得到它左子区和右子区,控制字居中。第23页第23页第第9 9章章 排序排序（3）重复第（1）、（2）步,直到左区处理完毕。然后退栈对一个个子区进行相类似处理,直到栈空。由以上三步能够看出:快速排序算法总框架是进行多趟分区处理;而对某一特定子区,则应把它当作又是一个待排序文献,控制字总是取子区中第一个统计关键字。现在设计一个函数hoare,它仅对某一待排序文献进行左、右子区划分,使控制字居中;再设计一个主体框架函数quicksort,在这里多次调用hoare函数以实现对整个文献排序。例9.4HT设有一组关键字46,56,14,43,95,19,18,72,这里n=8。试用快速排序办法由小到大进行排序。1)分区处理函数hoare第24页第24页第第9 9章章 排序排序思绪:首先用两个指针i、j分别指向首、尾两个关键字,i=1,j=8。第一个关键字46作为控制字,该关键字所属统计另存储在一个x变量中。从文献右端元素rj.key开始与控制字x.key相比较,当rj.key不小于等于x.key时,rj不移动,修改j指针,j-,直到rj.keyx.key,把统计ri移到文献右边j所指向位置;再到文献右边修改j指针,j-。重复上面环节,直到i=j,此处就是控制字统计x所在位置。第25页第25页第第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+;第26页第26页第第9 9章章 排序排序第27页第27页第第9 9章章 排序排序while(ij)&(ri.key=x.key)i+;if(i=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行结果。第28页第28页第第9 9章章 排序排序第29页第29页第第9 9章章 排序排序下面给出快速排序递归算法和非递归算法。非递归算法:算法9.6void quicksort1(struct node r MAXSIZE,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;第30页第30页第第9 9章章 排序排序elsel=stop0;h=stop1;top-;while(tag=1);/*quicksort1*/递归算法:算法9.7voidquicksort2(structnoder,intl,inth)if(lh)i=hoare(r,l,h);/*划分两个区*/第31页第31页第第9 9章章 排序排序quicksort2(r,l,i-1);/*对左分区快速排序*/quicksort2(r,i+1,h);/*对右分区快速排序*/*quicksort2*/在主程序调用非递归算法比较简朴易懂。若要调用递归算法,因函数形参不同,需做预处理。主程序主要操作以下:调用递归函数调用非递归函数creat(r,n);creat(r,n);l=1;h=n;quicksort1(r,n);quicksort2(r,l,h);输出r;输出r;第32页第32页第第9 9章章 排序排序3）快速排序算法空间时间及稳定性分析快速排序非递归算法引用了辅助栈,它深度为log2n。假设每一次分区处理所得两个子区长度相近,那么可入栈子区长度分别为:n/21,n/22,n/23,n/2k,又由于n/2k=1,因此k=log2n。分母中2指数正好反应出需要入栈子区个数,它就是log2n,也即栈深度。在最坏情况下,比如原文献关键字已有序,每次分区处理仅能得到一个子区。可入子区个数靠近n,此时栈最大深度为n。快速排序主体算法时间运算量约O(log2n),划分子区函数运算量约O(n),因此总时间复杂度为O(nlog2n),它显然优于冒泡排序O(n2)。可是算法优势并不是绝正确,试分析,当原文献关键字有序时,快速排序时间复杂度是O(n2),这种情况下快速排序不快。第33页第33页第第9 9章章 排序排序而这种情况冒泡排序是O(n),反而不久。在原文献统计关键字无序时各种排序办法中,快速排序被认为是最好一个排序办法。例9.5试对6,7,51,2,52,8进行快速排序。排序过程简述下列:67512528初始状态527516782525167825251678最后状态第34页第34页第第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-1)趟,从Kn-1、Kn中选择最小值Kz,将Kz与Kn-1对换,最终剩下就是该序列中最大值,一个由小到大有序序列就这么形成。该算法时间复杂度为O(n2)。第35页第35页第第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+)第36页第36页第第9 9章章 排序排序第37页第37页第第9 9章章 排序排序if(rj.keyrz.key)z=j;x=ri;ri=rz;rz=x;/*sisort*/第38页第38页第第9 9章章 排序排序9.4.2堆排序除了简单选择排序之外,还有树形选择排序(锦标赛排序)。1964年威洛姆斯(J.Willioms)提出了深入更正排序方法,即堆排序(heapsort)。堆是n个元素有限序列k1,k2,kn,它当且仅当满足以下关系:ki=k2iki=k2i+1i=1,2,这是一个上小、底大堆。若是一个上大、底小堆,只需把“=”即可。堆是一个数据元素之间逻辑关系,惯用向量做存放结构。对于第6章中介绍满二叉树,当对它结点由上而下,第39页第39页第第9 9章章 排序排序自左至右编号之后,编号为i结点是编号为2i和2i+1结点双亲。反过来讲,结点2i是结点i左孩子,结点2i+1是结点i右孩子。图9.7表示完全二叉树和它在向量中存储状态。结点编号相应向量中下标号。用堆概念分析向量中数据,它显然满足（上小、底大）堆关系。不难看出,满足堆逻辑关系一组数据,可画成二叉树形状,并且它是一棵完全二叉树树形。因此,也可借助完全二叉树来描述堆概念。若完全二叉树中任一非叶子结点值小于等于（或不小于等于）其左、右孩子结点值,则从根结点开始按结点编号排列所得结点序列就是一个堆。在图9.8中(a)、(c)是堆,(b)、(d)不是堆。第40页第40页第第9 9章章 排序排序第41页第41页第第9 9章章 排序排序第42页第42页第第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)堆排序。首先输出堆顶元素（普通是最小值）,让堆中最后一个元素上移到原堆顶位置,然后恢复堆。由于通过第一步输出堆顶元素操作后,往往破坏了堆关系,因此要恢复堆;重复执行输出堆顶元素、堆尾元素上移和恢复堆环节,直到所有元素输出完为止。第43页第43页第第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,则把这个孩子结点移上来。假如结点i两个孩子关键字都小于kz,那么将两个孩子中较小一个调整上来。第44页第44页第第9 9章章 排序排序第45页第45页第第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本来位置上。第二步:堆排序。这是一个重复输出堆顶元素,将堆尾元素移至堆顶,再调整恢复堆过程。恢复堆过程与初建堆中i=1时所进行操作完全相同。请注意:每输出一次堆顶元素，堆尾逻辑位置退1，直到堆中剩余一个元素为止。排序过程如图9.10所表示。第46页第46页第第9 9章章 排序排序堆排序算法实现:由上述可知,有一个操作过程（即调整恢复堆）要被多次重复调用,那就是当i值拟定之后,以ki为比较参考值,与它左、右孩子关键字比较和调整,使得以结点i为根子树成为堆,因此把这个过程设计成一个函数heap。另外,当然还需再设计一个主体算法,使在初建堆阶段,让i从n/2改变到1,循环调用函数heap。而在堆排序阶段,每输出一次堆顶元素同时将堆尾元素移至堆顶之后,就调用一次heap函数来恢复堆。主体算法由函数heapsort实现。以编号为i结点为根,调整为堆算法为:算法9.9第47页第47页第第9 9章章 排序排序第48页第48页第第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,以便结束循环*/第49页第49页第第9 9章章 排序排序ri=x;/*heap*/堆排序主体算法:算法9.10HTvoidheapsort(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*/第50页第50页第第9 9章章 排序排序在堆排序图示中,堆越画越小,事实上在r向量中堆顶元素输出之后并未删除,而是与堆尾元素对换。由图9.10可知输出是一个由小到大升序序列,而最后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所表示。第51页第51页第第9 9章章 排序排序第52页第52页第第9 9章章 排序排序9.5 归并排序归并排序归并排序(mergesort)是一类与插入排序、互换排序、选择排序不同另一个排序方法。归并含义是将两个或两个以上有序表合并成一个新有序表。归并排序有多路归并排序和两路归并排序；可用于内排序,也能够用于外排序。这里仅对内排序两路归并方法进行讨论。两路归并排序算法思绪:（1）把n个统计当作n个长度为l有序子表;（2）进行两两归并使统计关键字有序,得到n/2个长度为2有序子表;（3）重复第（2）步，直到全部统计归并成一个长度为n有序表为止。第53页第53页第第9 9章章 排序排序例9.7HT有一组关键字4,7,5,3,2,8,6,1,n=8,将其按由小到大顺序排序。两路归并排序操作过程如9.12所表示,其中l为子表长度。初始47532861l=1第1趟47321l=2第2趟34571268l=4第1趟12345678l=n算法实现:此算法实现不像图示那样简朴,现分三步来讨论。首先从宏观上分析,先让子表表长l=1进行处理;不断地使l=2*L,进行子表处理,直到l=n为止,把这一过程写成一个主体框架函数mergesort。第54页第54页第第9 9章章 排序排序第55页第55页第第9 9章章 排序排序然后对于某确定子表表长l,将n个统计分成若干组子表,两两归并,这里显然要循环若干次,把这一步写成一个函数mergepass,可由mergesort调用。最终再看每一组（一对）子表归并,其原理是相同,只是子表表长不同。换句话说,是子表首统计号与尾统计号不同,把这个归并操作作为关键算法写成函数merge,由mergepass来调用。主体框架算法描述以下:算法9.11voidmergesort(structnoderMAXSIZE,intn)/*r是包含有n个统计原文件,归并过程中另需一个r2作为辅助存放空间*/l=1;/*子表初始长度*/第56页第56页第第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;/*跳过两个子表,指向新一对子表首统计*/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*/第58页第58页第第9 9章章 排序排序归并排序关键算法描述下列:算法9.13oid merge(struct node rMAXSIZE,struct node r2MAXSIZE,inth1,intmid,inth2)/*h1为第一个子表首元素下标,mid为第一个子表未元素下标,*/*h2为第二个子表未元素下标*/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+;第59页第59页第第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;第60页第60页第第9 9章章 排序排序9.6 基数排序基数排序基数排序(radixsort)是与前面所介绍各类排序方法完全不同一个排序方法。前几节所介绍排序方法主要是经过比较统计关键字来实现,而基数排序法无须经过关键字比较来实现排序,而是依据关键字每个位上有效数字值,借助于“分派”和“搜集”两种操作来实现排序。本章假设统计关键字为整型（实质上关键字并不限于整型）。基数排序有两种方法:一个方法是首先依据最高位有效数字进行排序,然后依据次高位有效数字进行排序,依次类推,直到依据最低位（个位）有效数字进行排序,产生一个有序序列。这种方法称最高位优先法(MostSignificantDigitFirst),简称MSD法。第61页第61页第第9 9章章 排序排序另一办法是首先依据关键字最低位（个位）有效数字进行排序,然后依据次低位（十位）有效数字进行排序,依次类推,直到依据最高位有效数字进行排序,产生一个有序序列。这种办法称最低位优先法(LeastSignificantDigitFirst),简称LSD法。现用LSD法进行基数排序。假设有n个统计,其关键字在0999之间,每一位上有效数字值在09之间共10种也许性,则认为基数是10,在进行“分派”操作时涉及10个队列,即队列个数与基数相同。此处关键字最多位数是3,那么就需进行3趟“分派”和“搜集”操作。算法思绪:第62页第62页第第9 9章章 排序排序1）第一趟“分派”,依据关键字个位有效数字,把所有统计分派到相应10个队列中去。用f0,e0表示0号队列头、尾指针,f9,e9表示9号队列头、尾指针。比如,关键字为184统计就分派到4号队列中去。（2）第一趟“搜集”把所有非空队列（10个队列中也许有空队）按队列号由小到大顺序头、尾相接,搜集成一个新序列。此序列若观测其关键字个位,则它是有序;若观测其关键字高位,则它尚处于无序状态。（3）以后各趟分别依据关键字十位、百位有效数字重复第（1）、（2）步“分派”与“搜集”操作,最后得到一个按关键字由小到大序列。例9.8有一组关键字278,109,063,930,589,184,505,269,008,083,将它们按由小到大顺序排序。第63页第63页第第9 9章章 排序排序图9.13(a)是待排序关键字序列初始状态。图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)则是再次搜集后结果,这也是基数排序所得到最后有序序列。第64页第64页第第9 9章章 排序排序第65页第65页第第9 9章章 排序排序在本章前几节讨论中,待排序统计是用向量r做存储结构。基数排序又是“分派”队列,又要“搜集”起来,故适合用于链表形式存储。本节不采用动态链表而仍用向量r存储（即一维数组）,让每个存储统计数组元素增长一个指针域。此域为整型,用来存储该统计下一个相邻统计所在数组元素下标。这种结构称为静态链表结构。所谓队列头、尾指针也是整型,它们记下可做某号队列队头或队尾元素统计在数组r中下标值。统计结构为:structnodeintkey;/*关键字域*/intoth;/*其它信息域*/intpoint;/*指针域*/第66页第66页第第9 9章章 排序排序基数排序算法:设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指向链表第一个元素第67页第67页第第9 9章章 排序排序for(i=1;i=d;i+)/*下面是分派队列*/for(j=0;j10;j+)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指针向后移*第68页第68页第第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;*将前边一个非空队列队尾指针指向现在队头并记下现在队尾位置*第69页第69页第第9 9章章 排序排序rt.point=0;*这是一趟分派与搜集之后链表最后一个元素*/*fori*/return(p);/*基数排序结果p指向静态链表第一个元素,即关键字最小统计*/*radixsort*/分离关键字倒数第i位有效数字算法:第70页第70页第第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*/第71页第71页第第9 9章章 排序排序radixsort算法中基数为10,这里用rd表示它,最高有效数字位是4,这里用d表示,统计总数为n。基数排序时间复杂度为O(d(n+rd),这是由于总共循环d趟,每趟分派运算量数量级为O(n),搜集运算量数量级为O(rd),因此总时间复杂度为O(d(n+rd)。它空间占用情况是,向量r多了n个指针域,辅助空间为2rd个队列指针。基数排序是稳定。第72页第72页第第9 9章章 排序排序.7 内部排序总结内部排序总结表9.1列出了8种排序办法性能比较。（）当问题规模不大,即待排序统计数n不大时(n=50),可选取表中前三种排序办法之一。它们时间复杂度虽为O(n2),但办法简朴易掌握。直接插入排序和冒泡排序在原文献统计按关键字“基本有序”时,排序速度比较快。其中直接插入排序更为惯用。（）当n值很大,并不强求排序稳定性,并且内存容量不宽余时,应当选取快速排序或堆排序。普通来讲,它们排序速度非常快。但快速排序对原序列基本有序情况,速度减慢靠近O(n2),而堆排序不会出现最坏情况。第73页第73页第第9 9章章 排序排序第74页第74页第第9 9章章 排序排序（）当n值很大,对排序稳定性有要求,存储容量较宽余时,用归并排序最为适当。排序速度不久,并且稳定性好。（）当n值很大并且关键字位数较小时,采用静态链表基数排序不但速度较快,并且稳定性好。第75页第75页第第9 9章章 排序排序9.8 相关排序算法相关排序算法C语言源程序语言源程序本章介绍了各种算法,其中直接插入排序、折半插入排序、冒泡排序和简单选择排序程序在各种程序设计语言中都有详细介绍。这里我们提供希尔排序、快速排序、堆排序、归并排序和基数排序程序清单（均已上机经过）,供大家在消化算法和试验时参考。structnode/*统计结构。为简化问题,设定统计中只含关键字*intkey;r20;第76页第76页第第9 9章章 排序排序main()oidprint(structnodea20,intn);intcreat();oidshell(structnodea20,intn);inthoare(structnodea20,intl,inth);oidquick1(structnodea20,intn);oidquick2(structnodea20,intl,inth);oidheap(structnodea20,inti,intm);oidheapsort(structnodea20,intn);oidmerge(structnodea20,structnodea220,inth1,intmid,inth2);第77页第77页第第9 9章章 排序排序oidmergepass(structnodea20,structnodea220,intl,intn);oidmergesort(structnodea20,intn);intyx(intm,inti);intradixsort(structrnodea20,intn);intnum,l,h,c;structrnodes20;c=1;while(c!KG-*2=0)第78页第78页第第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表示结束):);第79页第79页第第9 9章章 排序排序scanf(%d,&c);switch(c)case1: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:radixso