ImageVerifierCode 换一换
格式:PPT , 页数:12 ,大小:321.50KB ,
文档编号:4107093      下载积分:19 文币
快捷下载
登录下载
邮箱/手机:
温馨提示:
系统将以此处填写的邮箱或者手机号生成账号和密码,方便再次下载。 如填写123,账号和密码都是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

优惠套餐
 

温馨提示:若手机下载失败,请复制以下地址【https://www.163wenku.com/d-4107093.html】到电脑浏览器->登陆(账号密码均为手机号或邮箱;不要扫码登陆)->重新下载(不再收费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  
下载须知

1: 试题类文档的标题没说有答案,则无答案;主观题也可能无答案。PPT的音视频可能无法播放。 请谨慎下单,一旦售出,概不退换。
2: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
3: 本文为用户(晟晟文业)主动上传,所有收益归该用户。163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

1,本文(数据结构0409归并排序课件.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!

数据结构0409归并排序课件.ppt

1、 归并排序 归并排序“归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。利用归并的思想实现排序假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到 n/2 个长度为2或1的有序子序列;再两两归并,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2-路归并排序。例题初始关键字:49 38 65 97 76 13 27一趟归并后:38 49 65 97 13 76 27二趟归并后:38 49 65 97 13 27 76三趟归并后:13 27 38 49 65 76 97 算法思想2-路归并排序将Rlow.high中的记录归并排序后

2、放入Tlow.high中。当序列长度等于1时,递归结束,否则:(1)将当前序列一分为二,求出分裂点mid=(low+high)/2;(2)对子序列Rlow.mid递归,进行归并排序,结果放入Slow.mid中;算法思想(3)对子序列Rmid+1.high递归,进行归并排序,结果放入Smid+1.high中;(4)调用算法Merge,将有序的两个子序列Slow.mid和Smid+1.high归并为一个有序的序列Tlow.high。算法描述void Msort(RedType R,RedType&T,int s,int t)/将Rs.t 归并排序为 Ts.t if(s=t)Ts=Rs;else m

3、=(s+t)/2;/将Rs.t平分为Rs.m和Rm+1.t Msort(R,TR2,s,m);/递归地将Rs.m归并为有序的TR2s.m Msort(R,TR2,m+1,t);/递归地Rm+1.t归并为有序的TR2m+1.t Merge(TR2,T,s,m,t);/将TR2s.m和TR2m+1.t归并到Ts.t /Msort 算法描述 void MergeSort(SqList&L)/对顺序表 L 作2-路归并排序 MSort(L.r,L.r,1,L.length);/MergeSort 将两个有序表归并为一个新的有序表的算法 void Merge(RedType R,RedType&T,in

4、t i,int m,int n)/将有序的记录序列Ri.m 和Rm+1.n 归并为有序的记录序列Ti.n int j,k;for(j=m+1,k=i;i=m&j=n;+k)/将SR中记录由小到大地并入TR if LQ(SRi.key,SRj.key)TRk=SRi+;else TRk=SRj+;if(i=m)/TRk.n=SRi.m;将剩余的SRi.m复制到TR while(k=n&i=m)TRk+=SRi+;if(j=n)/将剩余的SRj.n复制到TR while(k=n&j=n)TRk+=SRj+;/Merge 例 题52,23,80,36,68,14 (s=1,t=6)52,23,80 36,68,14 52,23 80 52 23,52 23,52,8036,68 14 36 6836,6814,36,68 14,23,36,52,68,80 23 算法的效率时间复杂度方面,由于每趟归并的时间复杂度O(n),而对于有n个记录的序列来说,一共需要进行 log2n 趟归并。因此归并排序的时间复杂度是O(n log2n)。空间复杂度方面,用顺序表实现归并排序时,需要和待排序记录个数相等的辅助存储空间,所以空间复杂度为O(n)。总 结归并排序很显然是一种稳定的排序方法。它也可用于链式存储结构存储的记录序列,并且不需要辅助的记录存储空间,但递归实现时仍然需要开辟相应的递归工作栈。

侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|