《可视化计算》第5章排序与查找(A)

第5章 排序与查找 PART A《可视化计算》

学习目标

如何在计算机中进行排序? 排序算法有那些分类? 如何实现常用的排序算法? 查找与排序有何关系? 查找算法有哪些分类? 如何实现常用的查找算法？

2

http://doc.guandang.net

何为排序?

学习中的排序： 在一些教课书中，会将涉及到的所有术语排成 索引，作为附录，方便读者在需要时查找 图书馆工作人员的重要工作，就是把归还的书 ，插入适当的书架、层次、位置, 方便读者查阅 社会中排序： 会议代表名单的排序(按姓氏笔画); 联大会议的发言顺序(按国家名称字母排序)

3

http://doc.guandang.net

计算机如何进行排序？

从”混沌”到有序：排序自身也是一种应用, 同时也为快速的查找提供必要的准备 在计算机科学中，排序(sorting)是研究最多 的问题之一 基本排序算法有5类：

插入排序，例如，直接插入排序，二分插入排序等； 交换排序，例如，冒泡排序，快速排序等； 选择排序，例如，选择排序，推排序等 归并排序，例如，归并排序，多相归并排序等 分布排序，例如，桶排序，基数排序等4 http://doc.guandang.net

排序术语和实现策略

自然的(natural)

如果某种排序算法对有序的数据排序速度较快( 工作量变小),对无序的数据排序速度却较慢( 工作变量大),这种算法被称为自然排序算法 如果数据已接近有序，就需要考虑选用自然的 排序算法

5

http://doc.guandang.net

排序术语和实现策略

稳定的(stable)

如果能保持它认为相等的数据的前后顺序，这 种算法被称为稳定排序算法 稳定的排序算法可按主、次关键字对数据进行 排序，例如，按照姓氏和名字排序。

在具体实现时，就是先按主关键字排序，再按次关 键字排序

6

http://doc.guandang.net

排序术语和实现策略

内部排序和外部排序

待排数据全部在内存中的排序方法被称为内部 排序，待排数据在磁盘、磁带和其它外存中的 排序方法被称为外部排序 本节涉及的排序算法，全部针对内部排序进行 讨论

7

http://doc.guandang.net

排序术语和实现策略

关键字排序(Key sort)

如果要对某班级学生的期末成绩表进行排序， 表中给出了每个学生的学号、姓名、单科成绩 和总成绩等项目 按什么来排序？所选结果,就是关键字 本章所有案例中，只考虑关键字字段，而先将 信息的其他内容一概略去

8

http://doc.guandang.net

排序术语和实现策略

数字化排序(digitized sort)

在排序过程中，可以按数值大小

排序，有时候 需要按字符来排序，有时候需要按照时间的迟 早来排序 实际上，计算机内的所有数据，无论属于哪种 类型数据，都可以转换成数字(二进制或十进 制)表达 所以排序本身可以抽象为对数字进行排序

9

http://doc.guandang.net

如何在RAPTOR中实现排序

排序算法测试的数据来源

请回顾第2章提及的随机数生成和存储，以及 使用文件输入数据的方法

不仅可以节省用户与算法的交互时间 而且可以适当扩大数据集合，验证算法的 效率

10

http://doc.guandang.net

直接插入排序

直接插入排序与整理扑克牌的过程非常类 似

第1张牌没有必要整理 以后每次从牌堆(无序区)的最上面摸出1张牌并 插入左手牌(有序区)中正确的位置上

为了确定正确的插入位置，一般从左向右 将摸上来的牌与手中已有的牌逐一比较

11

http://doc.guandang.net

直接插入排序

假设data.txt文件中存放着待排序的记录R[] ,则R[]可以看成是一个长度为n的待排数组 首先从data.txt文件中保存的数组R[]读入一 个数据到a[1],生成一个有序数组 由于文件中的数组R[]呈无序状态，从i=2起 至i=n为止，依次将R[i]插入当前的有序数组 a[1..i-1]中 最后生成含n个记录的有序数组12 http://doc.guandang.net

插入排序main子图

13

http://doc.guandang.net

插排look_for_position子图

14

http://doc.guandang.net

插排move_to_new_position子图

15

http://doc.guandang.net

桶排序

桶排序的思想源于信件分拣 在现实应用中，是把[0,1)的数值划分为n个大小 相同的子区间，每一子区间可以看作是一个桶

然后将n个记录分配到各个桶内

由于同一桶内的记录其关键字不尽相同，所以必 须采用关键字比较的排序方法(通常用插入排序)对 每个桶进行排序 然后依次将各非空桶内的记录连接(收集)起来即可

16

http://doc.guandang.net