- 1、本文档共48页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第十章 排序 排序定义——将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列叫~ 排序分类 按待排序记录所在位置 内部排序:待排序记录存放在内存 外部排序:排序过程中需对外存进行访问的排序 按排序依据原则 插入排序:直接插入排序、折半插入排序、希尔排序 交换排序:冒泡排序、快速排序 选择排序:简单选择排序、堆排序 归并排序:2-路归并排序 基数排序 按排序所需工作量 简单的排序方法:T(n)=O(n2) 先进的排序方法:T(n)=O(n*logn) 基数排序:T(n)=O(d*n) 排序基本操作 比较两个关键字大小 将记录从一个位置移动到另一个位置 10.1 插入排序 直接插入排序 排序过程:整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序 折半插入排序 排序过程:用折半查找方法确定插入位置的排序叫~ 算法描述 2-路插入排序 目的减少移动记录次数(约为n2/8) 使用DS:辅助向量:d[1..n], 指针:first 和final(当前最小和最大值位置) 思想:将d[1]视为有序文件的中间记录,并将待插入记录 r[i].key与d[1] .key进行比较 若r[i].key<d[1] .key:则将r[i]插入到d[first]~d[1]之间。 若r[i].key≥d[1] .key:则将r[i]插入到d[1]~d[final]之间。 例如:49,38,65,97,76,13,27,49 i=1 49 first final i=2 49 38 final first i=3 49 65 38 final first i=4 49 65 97 38 final first . . . d[1] d[2]………………………………..… d[n] final first 希尔排序(缩小增量法) 1基本思想:分割成若干个较小的子文件,对各个子文件分别进行直接插入排序,当文件达到基本有序时,再对整个文件进行一次直接插入排序。 2 依据:⑴若待排序文件基本有序,即文件中具有特性: r[i].key< Max {r[j ].key} 1≤j<i的记录数较少,则文件中大多数记录都不需要进行插入。 ⑵基本有序时,直接插入排序效率可以提高,接近于O(n)。 3排序过程:先取一个正整数d1n,把所有相隔d1的记录放一组,组内进行直接插入排序;然后取d2d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止 算法描述 10.2 快速(交换)排序 冒泡排序 排序过程 将第一个记录的关键字与第二个记录的关键字进行比较,若为逆序r[1].keyr[2].key,则交换;然后比较第二个记录与第三个记录;依次类推,直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序,结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程,直到“在一趟排序过程中没有进行过交换记录的操作”为止 算法描述 快速排序 基本思想:通过一趟排序,将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录进行排序,以达到整个序列有序 排序过程:对r[s……t]中记录进行一趟快速排序,附设两个指针i和j,设枢轴记录rp=r[s],x=rp.key 初始时令i=s,j=t 首先从j所指位置向前有哪些信誉好的足球投注网站第一个关键字小于x 的记录,并和rp交换 再从i所指位置起向后有哪些信誉好的足球投注网站,找到第一个关键字大于x的记录,和rp交换 重复上述两步,直至i==j为止
您可能关注的文档
最近下载
- 演出合同范本13篇.pdf VIP
- 佳能EOS6D使用说明.docx
- 世茂集团工程招投标技术标管理制度.docx
- 长安铃木吉姆尼电路图.pdf
- 美国材料与试验协会A480-A480M-2016_平扎不锈钢及耐热钢中板、薄板及钢带的一般要求[1](中文版).doc
- 地铁保洁服务投标方案(技术标).docx
- 2022年湖南衡阳市衡东县人大代表服务中心选调考试备考试题及答案解析.docx VIP
- 3完整版本.1固相反应.ppt VIP
- 2025高考英语时事热点阅读专练10 自然和宇宙探索(学生版+解析版).docx
- 2023年北京中考数学重难题型01新定义创新型综合压轴问题(13-22年最后一题+真题10道模拟30道)含详解.pdf VIP
文档评论(0)