- 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
- 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
【考研计算机专业课】武汉大学数据结构PPT课件 第10章 内排序
while (i=mid) //将第1段余下部分复制到R1 { R1[k]=R[i]; i++;k++; } while (j=high) //将第2段余下部分复制到R1 { R1[k]=R[j]; j++;k++; } for (k=0,i=low;i=high;k++,i++) //将R1复制回R中 R[i]=R1[k]; free(R1); } void MergePass(RecType R[],int length,int n) { int i; for (i=0;i+2*length-1n;i=i+2*length) //归并length长的两相邻子表 Merge(R,i,i+length-1,i+2*length-1); if (i+length-1n) //余下两个子表,后者长度小于length Merge(R,i,i+length-1,n-1); //归并这两个子表 } MergePass()实现了一趟归并 二路归并排序算法如下: void MergeSort(RecType R[],int n) { int length; for (length=1;lengthn;length=2*length) MergePass(R,length,n); } 例 设待排序的表有8个记录,其关键字分别为{18,2,20,34,12,32,6,16,1,5}。说明采用归并排序方法进行排序的过程。 18 2 20 34 12 32 6 16 1 5 初始: 2 18 20 34 12 32 6 16 1 5 2 18 20 34 6 12 16 32 1 5 2 6 12 16 18 20 32 34 1 5 1 2 5 6 12 16 18 20 32 34 log210取上界为4 第1趟 第2趟 第3趟 第4趟 容易看出,对 n 个记录进行归并排序的时间复杂度为Ο(nlogn)。即: 每一趟归并的时间复杂度为 O(n), 总共需进行 ?log2n? 趟。 例 对任意的7个关键字进行排序,至少要进行 次关键字之间的两两比较。 A.13 B.14 C.15 D.16 解:基于“比较”进行排序的算法在最坏情况下所需进行的比较次数至少为?log2(n!)?。?log2(7!)?=13。本题答案为A。 例 若数据元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是 。 A. 起泡排序 B. 插入排序 C. 选择排序 D. 二路归并排序 本题为2009年全国考研题 void BubbleSort(RecType R[],int n) { int i,j,exchange;RecType temp; for (i=0;in-1;i++) { exchange=0; for (j=n-1;ji;j--) //比较,找出最小关键字的记录 if (R[j].keyR[j-1].key) { temp=R[j]; R[j]=R[j-1];R[j-1]=temp; exchange=1; } if (exchange==0) return; //中途结束算法 } } 最好的情况(关键字在记录序列中顺序有序): 只需进行一趟冒泡 “比较”的次数: 最坏的情况(关键字在记录序列中逆序有序): 需进行n-1趟冒泡 “比较”的次数: 0 “移动”的次数: “移动”的次数: n-1 10.3.2 快速排序 快速排序是由冒泡排序改进而得的。 基本思想:在待排序的n个记录中任取一个记录(通常取第一个记录),把该记
您可能关注的文档
- 2016年考研数学三真题及答案解析.pdf
- 2018年河南省许昌初中二模试卷及答案解析-英语.pdf
- 2018年河南省中考百校大联考试卷及答案解析(二)语文.pdf
- 《UnitHowwasyourschooltripSectionAad》课件.ppt
- 《UnitHowwasyourschooltripSectionAac》课件.ppt
- 《UnitHowwasyourschooltripSectionAdb》课件.ppt
- 《梁家河》心得体会范文:感悟《梁家河》里的“大学问”.doc
- 2018年河南省中考百校大联考试卷及答案解析(二)化学.pdf
- 2018年河南省许昌初中二模试卷及答案解析-语文.pdf
- 【娱乐综艺】2016 滴滴快车×二更 品牌推广方案.pdf
- 【端午节PPT模板】传统文化中国风端午节 情浓粽飘香.ppt
- 【美妆】Pandora 圣诞季品牌传播创意方案.pdf
- 【考研英语讲义】长难句试炼 第三课 状语从句.pdf
- 一个情人节.doc
- 【造价培训资料】造价实战--桥梁工程(满堂支架现浇预应力箱梁).pdf
- 【造价培训资料】造价实战--路基土石方(借土填方)(附施工图解、工艺、造价编制).pdf
- 【美妆】2017 丝芙兰 家庭日活动方案.pdf
- 上海交通大学考研资料--《纺织材料学》冲刺讲义及模拟卷四套.pdf
- 上海交通大学考研资料--《纺织材料学》真题解析讲义.pdf
- 上海交通大学考研资料--《行政管理学》冲刺讲义及模拟卷四套2.pdf
最近下载
- 风险管理与金融机构第二版课后习题答案+(修复的)()详细分析.doc VIP
- 白砂糖仓库管理方案范本.docx VIP
- 初中语文2024届中考成语专项练习(共20道选择题,附参考答案).doc VIP
- 必威体育精装版版个人征信报告模板(word版-可编辑-带水印).docx VIP
- 部编版语文三年级下册第三单元3单元整体作业设计.docx VIP
- 新22J04-1 内装修一(墙面、吊顶)参考图集.docx VIP
- GB50278-2010 起重设备安装工程施工及验收规范.docx VIP
- 达索BIOVIA COSMOtherm 2020 用户指南.pdf
- 智慧养殖在线监测系统微型水质自动监测系统使用说明书.pdf
- 铜、铅、锌、银、镍、钼矿地质勘查规范.pdf VIP
文档评论(0)