- 1、本文档共116页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
第八章排序技术;概述;;排序前(56,34,47,23,66,18,82,47);排序的根本概念;排序的根本概念;多关键字排序;“高位优先”排序法:其中一种是先按花色分成有序的四类〔分别放入4个桶中〕,然后再按面值对每一类从小到大排序〔分别放入13个桶中〕。
两次分配,一次收集;“低位优先”排序法:
首先按面值从小到大把牌摆成13叠〔每叠4张牌〕,
然后将每叠牌按面值的次序收集到一起,
再对这些牌按花色摆成4叠,每叠有13张牌,
最后把这4叠牌按花色的次序收集到一起
是分配与收集交替进行。分配与收集的次数等于排序码的数目;排序的分类
内排序:在排序的整个过程中,待排序的所有记录全部被放置在内存中
2.外排序:由于待排序的记录个数太多,不能同时放置在内存,而需要将一局部记录放置在内存,另一局部记录放置在外存上,整个排序过程需要在内外存之间屡次交换数据才能得到排序的结果。;排序的分类
1.基于比较:根本操作——关键码的比较和记录的移动,其最差时间下限已经被证明为Ω〔nlog2n〕。
2.不基于比较:根据关键码的分布特征。;1.根本操作。内排序在排序过程中的根本操作:
⑴比较:关键码之间的比较;
⑵移动:记录从一个位置移动到另一个位置。
2.辅助存储空间。
辅助存储空间是指在数据规模一定的条件下,除了存放待排序记录占用的存储空间之外,执行算法所需要的其他存储空间。
3.算法本身的复杂程度。;排序算法的存储结构;8.2插入排序;根本思想:在插入第i〔i>1〕个记录时,前面的i-1个记录已经排好序。;根本思想:在插入第i〔i>1〕个记录时,前面的i-1个记录已经排好序。;直接插入排序过程例如;解决方法:
将第1个记录看成是初始有序表,然后从第2个记录起依次插入到这个有序表中,直到将第n个记录插入。;关键问题(2)如何查找待插入记录的插入位置?;voidinsertSort(intr[],intn){
for(i=2;i=n;i++){
r[0]=r[i];j=i-1;
while(r[0]r[j]){
r[j+1]=r[j];
j=j-1;
}
r[j+1]=r[0];
}
};直接插入排序算法性能分析;直接插入排序算法性能分析;平均情况下〔随机排列〕:
;空间性能:需要一个记录的辅助空间。
直接插入排序算法是一种稳定的排序算法。;插入排序;希尔排序;〔1〕应如何分割待排序记录,才能保证整个序列逐步向根本有序开展?
〔2〕子序列内如何进行直接插入排序?;根本有序:接近正序,例如{1,2,8,4,5,6,7,3,9};
局部有序:局部有序,例如{6,7,8,9,1,2,3,4,5}。
局部有序不能提高直接插入排序算法的时间性能。;希尔插入排序过程例如;解决方法:
将相隔某个“增量”的记录组成一个子序列。
增量应如何取?
希尔最早提出的方法是d1=n/2,di+1=di/2。;解决方法:
在插入记录r[i]时,自r[i-d]起往前跳跃式〔跳跃幅度为d〕有哪些信誉好的足球投注网站待插入位置,并且r[0]只是暂存单元,不是哨兵。当有哪些信誉好的足球投注网站位置<0,表示插入位置已找到。
在有哪些信誉好的足球投注网站过程中,记录后移也是跳跃d个位置。
在整个序列中,前d个记录分别是d个子序列中的第一个记录,所以从第d+1个记录开始进行插入。;希尔插入排序过程例如;算法描述:;希尔排序算法的时间性能;交换排序的主要操作是交换,其主要思想是:在待排序列中选两个记录,将它们的关键码相比较,如果反序〔即排列顺序与排序后的次序正好相反〕,那么交换它们的存储位置。;起泡排序;05;⑴在一趟起泡排序中,假设有多个记录位于最终位置,应如何记载?
⑵如何确定起泡排序的范围,使得已经位于最终位置的记录不参与下一趟排序?
⑶如何判别起泡排序的结束?;解决方法:
设变量exchange记载记录交换的位置,那么一趟排序后,exchange记载的一定是这一趟排序中记录的最后一次交换的位置,且从此位置以后的所有记录均已经有序。;关键问题⑴:如何记载一趟排序过程中交换的多个记录?;解决方法:
设bound位置的记录是无序区的最后一个记录,那么每趟起泡排序的范围是r[1]~r[bound]。
在一趟排序后,从exchange位置之后的记录一定是有序的,所以bound=exchange。;解决方法:
设bound位置的记录是无序区的最后一个记录,那么每趟起泡排序的范围是r[1]~r[bound]。
在一趟排序后,从exchange位置之后的记录一定是有序的,
您可能关注的文档
最近下载
- 浙江省绍兴会稽联盟2023-2024学年高二上学期期末联考化学试题含解析.pdf VIP
- 中国华电集团招聘笔试题库2024.pdf
- 浙江省杭州市2023-2024学年高二上学期1月期末化学试题含解析.pdf VIP
- 登泰山记(ppt)课件.ppt
- 浙江省金华十校2023-2024学年高二上学期期末调研考试语文试卷含答案.pdf VIP
- 浙江省丽水市2023-2024学年高二上学期1月期末数学试题(含答案).pdf VIP
- ansys教学算例集筒型燃烧室内燃烧辐射分析.pdf
- 2022-2023年机场建设行业洞察报告.pdf VIP
- 360日志审计系统操作手册.pdf
- 电子工艺实习报告收音机(共10篇).docx VIP
文档评论(0)