- 1、本文档共94页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
排序:将一组杂乱无章的数据按一定的规律顺次排列起来:输入记录R1, R2, …, Rn, 其键分别为K1, K2, …, Kn; 输出Ri1, Ri2 , …, Rin,使得键序列为Ki1, Ki2, …, Kin或相反序列。 一般来说,排序过程要对键大小进行比较,主要根据三个原则: 若键为数值类型,则以数值大小为依据; 若键为非中文字符串类型,则采用键的内码编排次序比较大小; 若键为中文字符串类型,同样也是自左往右逐字比较,但非单纯地运用ASCII,而是采用键所用的中文内码编排顺序来比较大小。 作为排序依据的键称为“排序码” : 若是主键,则对于任意待排序列,经排序后得到的结果是唯一的; 若是次键,则排序结果可能不唯一,即排序后的元素位置关系与排序前不一定保持不变。 排序算法的稳定性: 如果在对象序列中有两个对象ri和rj,它们的关键码 ki == kj,且在排序之前,对象ri排在rj前面。如果在排序之后,对象ri一定仍在对象rj的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。 排序的方法可以按以下两种方式分类: 按是否涉及数据的内外交换分类。 内排序是指在排序期间数据对象全部存放在内存的排序; 外排序是指在排序期间全部对象个数太多,不能同时存放在内存,必须根据排序过程的要求,不断在内、外存之间移动的排序。 按排序策略划分,内部排序可以分为: 插入排序 选择排序 交换排序 归并排序 分配排序(基数排序) 排序算法有两个基本操作: 比较两个键的大小; 改变指向记录的指针或移动记录本身。 排序过程依赖于待排序文件的存储结构: 以顺序表作为存储结构(重排过程中,记录需要移动合适的位置); 以链表作为存储结构(无需移动位置,只需修改指向记录的指针); 用顺序的方式存储记录,同时建立一个索引表(移动索引表的表目,不移动记录)。 排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志: 排序算法的时间复杂度:大多数排序算法的时间复杂度主要是键之间的比较次数与记录的移动次数,某些算法还取决于数据的原始状态; 排序算法的空间复杂度:若排序算法需要的辅助空间不依赖问题的规模,即复杂度为O(1),则成为就地排序。 给出算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象关键码序列初始排列及对象个数影响较大的,需要按最好情况和最坏情况进行估算。 插入排序的基本方法是:每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。 常见的两种插入排序方法是: 直接插入排序 希尔排序 直接插入排序的基本思想是:当插入第i (i ? 1) 个对象时,前面的v[0], v[1], …, v[i-1]已经排好序。这时,用v[i]的关键码与v[i-1], v[i-2], …的关键码顺序进行比较,找到插入位置即将v[i]插入,原来位置上的对象向后顺移。 若设待排序的对象个数为n,则该算法的主程序执行n-1趟。 关键码比较次数和对象移动次数与对象关键码的初始排列有关。 最好情况下,排序前对象已经按关键码大小从小到大有序,每趟只需与前面的有序对象序列的最后一个对象的关键码比较 1 次,移动 2 次对象,总的关键码比较次数为 n-1,对象移动次数为 2(n-1)。 最坏情况下,第 i 趟时第 i 个对象必须与前面 i 个对象都做关键码比较,并且每做 1 次比较就要做 1 次数据移动。则总的关键码比较次数KCN和对象移动次数RMN分别为: 若待排序对象序列中出现各种可能排列的概率相同,则可取上述最好情况和最坏情况的平均情况。 平均情况下关键码比较次数和对象移动次数约为 n2/4;在排序过程中需要一个辅助空间(监视哨)。因此,直接插入排序: 时间复杂度为 O (n2)。 空间复杂度为O (1)(是一个就地排序)。 是一种稳定的排序方法。 当 n 较大时,总关键码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。 在对象的初始排列已经按关键码排好序或接近有序时,直接插入排序比二分插入排序执行的关键码比较次数要少。 二分插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列,且需要一个辅助存储空间: 时间复杂度为O(nlgn)。 空间复杂点为O(1)。 是一个稳定的排序方法。 交换排序的基本思想是两两比较待排序对象的关键码,如果发生逆序(即排列顺序与排序后的次序正好相反),则交换之,直到所有对象都排好序为止。 交换排序常见的有两种方法: 冒泡排序 快速排序 算法quicksort是一个递归的算法,其递归树如图所示。 算法partition利用序列第一个对象作为基准,将整个序列划分为左右两个子序列。算法中执行了一个循环,只要是关键码小于基准对象关键码的对
您可能关注的文档
- C++设计模的式第六讲.ppt
- C++课程的设计实验报告.pdf
- C++设计的模式第四讲.ppt
- C++面向对象程序的设计复习资料.doc
- C++铁道第的2版-10.ppt
- c++面对的对象程序设计复习题集.pdf
- C++铁道的第2版-3.ppt
- C+的+_构造与析构函数知识详细讲解(有实例).ppt
- c+的+期末考试重点.docx
- C+的+ 第3章 中类和对象.pdf
- 《传统节日》教学设计.pdf
- 《初中数学“高效课堂”教学模式研究》课题设计论证书.pdf
- “确立中国学前教育的文化自信之思”观后感(10篇).pdf
- 《儿科护理学》在线作业试题和答案,中医儿科学期末试卷B.pdf
- Unit 8 S A (1a-1c)同步练习 2022-2023学年人教版七年级英语上册 .pdf
- windows server服务器配置与管理项目教程习题与答案.pdf
- xx市美容美发机构化妆品专项行动工作方案参考范文附:4个附表.pdf
- 《Matlab在光信息处理中的应用》课程教学大纲(本科).pdf
- XX学院商务大数据采集分析应用系统项目需求说明.pdf
- U校园》新视野大学英语视听说教程2第三版unit8答案.pdf
最近下载
- 微生物检测技术 教学课件 作者 叶磊杨学敏 主编 项目十一十二 食品的微生物学检验.pptx
- 输电线路运维管理方案.doc
- 2023年兰州大学计算机科学与技术专业《计算机网络》科目期末试卷B(有答案).docx VIP
- 钱七虎英雄事迹微党课ppt课件.pptx VIP
- 三一汽车起重机STC1000C7-1_产品手册用户使用说明书技术参数图解图示电子版.pdf VIP
- 免疫疾病治疗与输液泵技术.docx
- 电池生产企业安全生产风险分级管控和隐患排查治理双体系方案全套资料(2019-2020新标准完整版).docx
- 电缆桥架样本.pdf
- 代理记账客户合同书范本(标准版).doc VIP
- 湘教版七年级上册地理第二章第三节世界的地形课件01陆地地形和海底地形.pptx
文档评论(0)