大学《数据结构》第七章：排序-第七节-内部排序方法的分析比较_第1页
大学《数据结构》第七章：排序-第七节-内部排序方法的分析比较_第2页
大学《数据结构》第七章：排序-第七节-内部排序方法的分析比较_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

Word-3-大学《数据结构》第七章：排序-第七节-内部排序方法的分析比较

第七节内部排序办法的分析比较

1.时光复杂度I直接插入、直接挑选、冒泡排序算法的时光复杂度为0n202迅速、归并、堆排序算法的时光复杂度为0nlog2n3希尔排序算法的时光复杂度很难计算，有几种较临近的答案0nlog2n或0n1-25o4基数排序算法的时光复杂度为Od*rd+n，其中rd是基数，d是关键字的位数，n是元素个数

2、稳定性1直接插入、冒泡、归并和基数排序算法是稳定的；2直接挑选、希尔、迅速和堆排序算法是不稳定的

3、辅助空间空间复杂度1直接插入、直接挑选、冒泡、希尔和堆排序算法需要辅助空间为012迅速排序算法需要辅助空间为0log2n;3归并排序算法需要辅助空间为0n:4基数排序算法需要辅助空间为0n+rd

4、选取排序办法时需要考虑的主要因素1待排序的记录个数2记录本身的大小和存储结构3关键字的分布状况4对排序稳定性的要求5时光和空间复杂度等

5、排序办法的选取1若待排序的一组记录数目较小如n50时，可采纳插入排序或挑选排序2若n较大时，则应采纳迅速排序、堆排序或归并排序3若待排序记录按关键字基本有序时，则相宜选用直接插入排序或冒泡排序4当n很大，而且关键字位数较少时，采纳链式基数排序较好5关键字比较次数与记录的初始罗列挨次无关的排序办法是挑选排序

6、排序办法对记录存储方式的要求普通的排序办法都能够在挨次结构一维数组上实现当记录本身信息量较大时，为了避开移动记录耗费大量的时光，能够采纳链式存储结构例如插入排序、归并排序、基数排序易于在链表上实现，使之削减记录的移动次数，但有些排序办法，如迅速排序、堆排序在链表上却难于实现，在这种请况下，能够提取关键字建立索引表，然后对索引表举行排序【真题选解】例题•单选题无论待排序列是否有序，排序算法时光复杂度都是0户的排序办法是A.迅速排序B.归并排序C.冒泡排序D.直接挑选排序躲藏答案【答案】D【解析】四种排序办法中，惟独直接挑选排序，无论待排序列是否有序排序算法时光复杂度都是0小例题•单选题要以0nlog2n时光复杂度举行稳定的排序，可用的排序办法是A.归并排序B.迅速排序C.堆排序D.冒泡排序躲藏答案【答案】A【解析】四种排序办法中，归并排序和冒泡排序是稳定排序，归并排序的时光复杂度为0nlog2n,冒泡排序的时光复杂度为0n20当前讲授本章小结本章着重研究有关内部排序的一些常用办法，主要有插入排序、交换排序、挑选排序、归并排序及基数排序，介绍其排序思想、排序过程、算法实现时光和空间性能的分析及各种排序办法的比较和挑选在掌控所介绍的几种主要排序算法的基

人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论