《可视化计算》第5章排序与查找.ppt

该【《可视化计算》第5章排序与查找 】是由【sanshenglu2】上传分享，文档一共【45】页，该文档可以免费在线阅读，需要了解更多关于【《可视化计算》第5章排序与查找 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。《可视化计算》第5章排序与查找
学****目标
如何在计算机中进行排序?
排序算法有那些分类?
如何实现常用的排序算法?
查找与排序有何关系?
查找算法有哪些分类?
如何实现常用的查找算法?
*
《可视化计算》第5章排序与查找
何为排序?
学****中的排序:
在一些教课书中,会将涉及到的所有术语排成索引,作为附录,方便读者在需要时查找
图书馆工作人员的重要工作,就是把归还的书,插入适当的书架、层次、位置,方便读者查阅
社会中排序:
会议代表名单的排序(按姓氏笔画);
联大会议的发言顺序(按国家名称字母排序)
*
《可视化计算》第5章排序与查找
计算机如何进行排序?
从”混沌”到有序:排序自身也是一种应用,同时也为快速的查找提供必要的准备
在计算机科学中,排序(sorting)是研究最多的问题之一
基本排序算法有5类:
插入排序,例如,直接插入排序,二分插入排序等;
交换排序,例如,冒泡排序,快速排序等;
选择排序,例如,选择排序,推排序等
归并排序,例如,归并排序,多相归并排序等
分布排序,例如,桶排序,基数排序等
*
《可视化计算》第5章排序与查找
排序术语和实现策略
自然的(natural)
如果某种排序算法对有序的数据排序速度较快(工作量变小),对无序的数据排序速度却较慢(工作变量大),这种算法被称为自然排序算法
如果数据已接近有序,就需要考虑选用自然的排序算法
*
《可视化计算》第5章排序与查找
排序术语和实现策略
稳定的(stable)
如果能保持它认为相等的数据的前后顺序,这种算法被称为稳定排序算法
稳定的排序算法可按主、次关键字对数据进行排序,例如,按照姓氏和名字排序。
在具体实现时,就是先按主关键字排序,再按次关键字排序
*
《可视化计算》第5章排序与查找
排序术语和实现策略
内部排序和外部排序
待排数据全部在内存中的排序方法被称为内部排序,待排数据在磁盘、磁带和其它外存中的排序方法被称为外部排序
本节涉及的排序算法,全部针对内部排序进行讨论
*
《可视化计算》第5章排序与查找
排序术语和实现策略
关键字排序(Keysort)
如果要对某班级学生的期末成绩表进行排序,表中给出了每个学生的学号、姓名、单科成绩和总成绩等项目
按什么来排序?所选结果,就是关键字
本章所有案例中,只考虑关键字字段,而先将信息的其他内容一概略去
*
《可视化计算》第5章排序与查找
排序术语和实现策略
数字化排序(digitizedsort)
在排序过程中,可以按数值大小排序,有时候需要按字符来排序,有时候需要按照时间的迟早来排序
实际上,计算机内的所有数据,无论属于哪种类型数据,都可以转换成数字(二进制或十进制)表达
所以排序本身可以抽象为对数字进行排序
*
《可视化计算》第5章排序与查找
如何在RAPTOR中实现排序
排序算法测试的数据来源
请回顾第2章提及的随机数生成和存储,以及使用文件输入数据的方法
不仅可以节省用户与算法的交互时间
而且可以适当扩大数据集合,验证算法的效率
*
《可视化计算》第5章排序与查找