数据结构教学课件第章排序市公开课一等奖百校联赛特等奖课件.pptx
《数据结构教学课件第章排序市公开课一等奖百校联赛特等奖课件.pptx》由会员分享,可在线阅读,更多相关《数据结构教学课件第章排序市公开课一等奖百校联赛特等奖课件.pptx(106页珍藏版)》请在咨信网上搜索。
1、第第9 9章章 排序排序9.1 排序基本概念排序基本概念 9.2 插入排序插入排序 9.3 交换排序交换排序 9.4 选择排序选择排序 9.5 归并排序归并排序 9.6 基数排序基数排序 9.7 内部排序总结内部排序总结 9.8 相关排序算法相关排序算法C语言源程序语言源程序 9.9 多路归并用于外排序介绍多路归并用于外排序介绍第第9章章 排序排序返回主目录返回主目录第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页第第9 9章章 排序排序9.2 插入排序插入排序 9.2.1 直接插入排序直接插入排序直接插入排序(straightinsertionsort)是一个最简单排序方法。它基本操作是将一个统计插入到一个长度为m(假设)有序表中,使之仍保持有序,从而得到
4、一个新长度为m1有序表。算法思绪:设有一组关键字K1,K2,Kn,排序开始就认为K1是一个有序序列;让K2插入上述表长为1有序序列,使之成为一个表长为2有序序列;然后让K3插入上述表长为2有序序列,使之成为一个表长为3有序序列;依次类推,最终让Kn插入上述表长为n-1有序序列,得一个表长为n有序序列。第5页第第9 9章章 排序排序第6页第第9 9章章 排序排序例9.1设有一组关键字序列55,22,44,11,33,这里n=5,即有5个统计。如图9.1所表示。请将其按由小到大次序排序在详细实现Ki向前边插入时,有两种方法。一个方法是让Ki与K1,K2,次序比较;另一个方法是Ki与Ki-1,Ki-
5、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页第第9 9章章 排序排序当某结点
6、i关键字Kj与前边有序表比较时,显然先与K1比较,再与K2比较,即从链表表头结点开始向后逐一比较更适当。另外,直接插入排序在原关键字序列基本有序或n值较小时,它是一个最惯用排序方法,它时间复杂度靠近于O(n)。不过,当n值又较大时,此方法就不再适用。第9页第第9 9章章 排序排序9.2.2 折半插入排序折半插入排序当直接插入排序进行到某一趟时,对于ri.key来讲,前面i-1个统计已经按关键字有序。此时不用直接插入排序方法,而改为折半查找,找出ri.key应插位置,然后插入。这种方法就是折半插入排序(binaryinsertionsort)。算法以下:算法9.2voidbinasort(str
7、uctnoderMAXSIZE,intn)for(i=2;i=n;i+)ZK(r0=ri;l=1;h=i-1;第10页第第9 9章章 排序排序while(l=h)mid=(l+h)/2;if(r0.key=l;j-)rj+1=rj;rl=r0;/*binasort*/第11页第第9 9章章 排序排序9.2.3 希尔排序希尔排序希尔排序(shellsort)是D希尔(D.L.Shell)提出“缩小增量”排序方法。它作法不是每次一个元素挨一个元素比较,而是早期选取大跨步(增量较大)间隔比较,使统计跳跃式靠近它排序位置;然后增量缩小;最终增量为1,这么统计移动次数大大降低,提升了排序效率。希尔排序对
8、增量序列选择没有严格要求。算法思绪:先取一个正整数d1(d1n),把全部统计分成d1个组,全部距离为d1倍数统计看成一组,然后在各组内进行插入排序;然后取d2(d2=1),即全部统计成为一个组为止。普通选d1约为n/2,d1为d1/2,d3为d1/2,d1=1。第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值*
9、/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页第第9 9章章 排序排序第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向前插;第1
10、6页第第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页第第9 9章章 排序排序希尔排序分析是一个复杂问题,因为它时间是所选定“增量序列”函数,这包括到数学上一些还未处理
11、难题。到当前为止,没有些人找到一个最好增量序列。有些人在大量试验基础上推导出,希尔排序时间复杂度为O(n1.3)。假如对关键字序列6,7,51,2,52,8进行希尔排序,能够看出希尔排序是不稳定。第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)第
12、20页第第9 9章章 排序排序第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页第第9 9章章 排序排序9.3.2快速排序快速排序由霍尔(Hoare)提出,它是一种对冒泡排序改正。由于其排序速
13、度快,故称快速排序(quicksort)。快速排序方法实质是将一组关键字K1,K2,Kn进行分区交换排序。其算法思路是:(1)以第一个关键字K1为控制字,将K1,K2,Kn分成两个子区,使左区全部关键字小于等于K1,右区全部关键字大于等于K1,最后控制字居两个子区中间适当位置。在子区内数据尚处于无序状态。(2)将右区首、尾指针(记录下标号)保存入栈,对左区进行与第(1)步相类似处理,又得到它左子区和右子区,控制字居中。第23页第第9 9章章 排序排序(3)重复第(1)、(2)步,直到左区处理完成。然后退栈对一个个子区进行相类似处理,直到栈空。由以上三步能够看出:快速排序算法总框架是进行多趟分区
14、处理;而对某一特定子区,则应把它看成又是一个待排序文件,控制字总是取子区中第一个统计关键字。现在设计一个函数hoare,它仅对某一待排序文件进行左、右子区划分,使控制字居中;再设计一个主体框架函数quicksort,在这里屡次调用hoare函数以实现对整个文件排序。例9.4HT设有一组关键字46,56,14,43,95,19,18,72,这里n=8。试用快速排序方法由小到大进行排序。1)分区处理函数hoare第24页第第9 9章章 排序排序思绪:首先用两个指针i、j分别指向首、尾两个关键字,i=1,j=8。第一个关键字46作为控制字,该关键字所属统计另存放在一个x变量中。从文件右端元素rj.k
15、ey开始与控制字x.key相比较,当rj.key大于等于x.key时,rj不移动,修改j指针,j-,直到rj.keyx.key,把统计ri移到文件右边j所指向位置;再到文件右边修改j指针,j-。重复上面步骤,直到i=j,此处就是控制字统计x所在位置。第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+
16、;第26页第第9 9章章 排序排序第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页第第9 9章章 排序排序第29页第第9 9章章 排序排
17、序下面给出快速排序递归算法和非递归算法。非递归算法:算法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页第第9 9章章 排序排序elsel=stop0;h=stop1;top-;while(tag=1);/*quicksort1*/递归算法:算法9.7voidquicksort2(structnoder,intl,inth)if(lh)i=hoare(r,l,h)
18、;/*划分两个区*/第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页第第9 9章章 排序排序3)快速排序算法空间时间及稳定性分析快速排序非递归算法引用了辅助栈,它深度为log2n。
19、假设每一次分区处理所得两个子区长度相近,那么可入栈子区长度分别为: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页第第9 9
20、章章 排序排序而这种情况冒泡排序是O(n),反而很快。在原文件统计关键字无序时各种排序方法中,快速排序被认为是最好一个排序方法。例9.5试对6,7,51,2,52,8进行快速排序。排序过程简述以下:67512528初始状态527516782525167825251678最终状态第34页第第9 9章章 排序排序9.4 选择排序选择排序9.4.1 简单项选择择排序简单项选择择排序简单项选择择排序(simpleselectionsort)也是直接选择排序。此方法在一些高级语言课程中做过介绍,是一个较为轻易了解方法。对于一组关键字K1,K2,Kn,将其由小到大进行简单排序详细思绪是:首先从K1,K2,
21、Kn中选择最小值,假如它是Kz,则将Kz与K1对换;然后从K2,K3,Kn中选择最小值Kz,再将Kz与Kz对换;如此进行选择和调换n-2趟。第(n-1)趟,从Kn-1、Kn中选择最小值Kz,将Kz与Kn-1对换,最终剩下就是该序列中最大值,一个由小到大有序序列就这么形成。该算法时间复杂度为O(n2)。第35页第第9 9章章 排序排序由此可见,对于n个统计关键字,需要处理n-1趟;而在每趟之中,又有一个内循环。图9.6是一个有5个关键字3,4,1,5,2简单项选择择排序过程示意图。假设用变量z记下较小值下标,则算法如算法9.8。算法9.8voidsisort(structnoderMAXSIZE
22、,intn)for(i=1;in;i+)z=i;for(j=i+1;j=n;j+)第36页第第9 9章章 排序排序第37页第第9 9章章 排序排序if(rj.keyrz.key)z=j;x=ri;ri=rz;rz=x;/*sisort*/第38页第第9 9章章 排序排序9.4.2 堆排序堆排序除了简单项选择择排序之外,还有树形选择排序(锦标赛排序)。1964年威洛姆斯(J.Willioms)提出了深入更正排序方法,即堆排序(heapsort)。堆是n个元素有限序列k1,k2,kn,它当且仅当满足以下关系:ki=k2iki=k2i+1i=1,2,这是一个上小、底大堆。若是一个上大、底小堆,只需把
23、“=”即可。堆是一个数据元素之间逻辑关系,惯用向量做存放结构。对于第6章中介绍满二叉树,当对它结点由上而下,第39页第第9 9章章 排序排序自左至右编号之后,编号为i结点是编号为2i和2i+1结点双亲。反过来讲,结点2i是结点i左孩子,结点2i+1是结点i右孩子。图9.7表示完全二叉树和它在向量中存放状态。结点编号对应向量中下标号。用堆概念分析向量中数据,它显然满足(上小、底大)堆关系。不难看出,满足堆逻辑关系一组数据,可画成二叉树形状,而且它是一棵完全二叉树树形。所以,也可借助完全二叉树来描述堆概念。若完全二叉树中任一非叶子结点值小于等于(或大于等于)其左、右孩子结点值,则从根结点开始按结点
24、编号排列所得结点序列就是一个堆。在图9.8中(a)、(c)是堆,(b)、(d)不是堆。第40页第第9 9章章 排序排序第41页第第9 9章章 排序排序第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)堆排序。首先输出堆顶元素(普通
25、是最小值),让堆中最终一个元素上移到原堆顶位置,然后恢复堆。因为经过第一步输出堆顶元素操作后,往往破坏了堆关系,所以要恢复堆;重复执行输出堆顶元素、堆尾元素上移和恢复堆步骤,直到全部元素输出完为止。第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时,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 教学 课件 排序 公开 一等奖 联赛 特等奖
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。