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

《《可视化计算》第5章排序与查找(A)》由会员分享，可在线阅读，更多相关《《可视化计算》第5章排序与查找(A)（46页珍藏版）》请在金锄头文库上搜索。

1、第5章 排序与查找 PART A可视化计算学习目标如何在计算机中进行排序?排序算法有那些分类? 如何实现常用的排序算法?查找与排序有何关系?查找算法有哪些分类? 如何实现常用的查找算法？2http:/何为排序?学习中的排序：在一些教课书中，会将涉及到的所有术语排成 索引，作为附录，方便读者在需要时查找图书馆工作人员的重要工作，就是把归还的书 ，插入适当的书架、层次、位置, 方便读者查 阅社会中排序：会议代表名单的排序（按姓氏笔画）；联大会议的发言顺序（按国家名称字母排序）3http:/计算机如何进行排序？从”混沌”到有序：排序自身也是一种应用,同 时也为快速的查找提供必要的准备在计算机科学中，

2、排序(sorting)是研究最多 的问题之一基本排序算法有5类：插入排序，例如，直接插入排序，二分插入排序等；交换排序，例如，冒泡排序，快速排序等；选择排序，例如，选择排序，推排序等归并排序，例如，归并排序，多相归并排序等分布排序，例如，桶排序，基数排序等4http:/排序术语和实现策略自然的(natural)如果某种排序算法对有序的数据排序速度较快( 工作量变小)，对无序的数据排序速度却较慢( 工作变量大)，这种算法被称为自然排序算法如果数据已接近有序，就需要考虑选用自然的 排序算法5http:/排序术语和实现策略稳定的(stable)如果能保持它认为相等的数据的前后顺序，这 种算法被称为稳

3、定排序算法稳定的排序算法可按主、次关键字对数据进行 排序，例如，按照姓氏和名字排序。在具体实现时，就是先按主关键字排序，再按次关 键字排序6http:/排序术语和实现策略内部排序和外部排序待排数据全部在内存中的排序方法被称为内部 排序，待排数据在磁盘、磁带和其它外存中的 排序方法被称为外部排序本节涉及的排序算法，全部针对内部排序进行 讨论7http:/排序术语和实现策略关键字排序（Key sort）如果要对某班级学生的期末成绩表进行排序， 表中给出了每个学生的学号、姓名、单科成绩 和总成绩等项目按什么来排序？所选结果,就是关键字本章所有案例中，只考虑关键字字段，而先将 信息的其他内容一概略去8

4、http:/排序术语和实现策略数字化排序（digitized sort）在排序过程中，可以按数值大小排序，有时候 需要按字符来排序，有时候需要按照时间的迟 早来排序实际上，计算机内的所有数据，无论属于哪种 类型数据，都可以转换成数字（二进制或十进 制）表达所以排序本身可以抽象为对数字进行排序9http:/如何在RAPTOR中实现排序排序算法测试的数据来源请回顾第2章提及的随机数生成和存储，以及 使用文件输入数据的方法不仅可以节省用户与算法的交互时间而且可以适当扩大数据集合，验证算法的 效率10http:/直接插入排序直接插入排序与整理扑克牌的过程非常类 似第1张牌没有必要整理以后每次从牌堆(无

5、序区)的最上面摸出1张牌并 插入左手牌(有序区)中正确的位置上为了确定正确的插入位置，一般从左向右 将摸上来的牌与手中已有的牌逐一比较11http:/直接插入排序假设data.txt文件中存放着待排序的记录R ，则R可以看成是一个长度为n的待排数组首先从data.txt文件中保存的数组R读入一 个数据到a1，生成一个有序数组由于文件中的数组R呈无序状态，从i=2起 至i=n为止，依次将Ri插入当前的有序数组 a1i-1中最后生成含n个记录的有序数组12http:/插入排序main子图13http:/插排look_for_position子图14http:/插排move_to_new_posit

6、ion子图15http:/桶排序桶排序的思想源于信件分拣 在现实应用中，是把0，1)的数值划分为n个大小 相同的子区间，每一子区间可以看作是一个桶然后将n个记录分配到各个桶内由于同一桶内的记录其关键字不尽相同，所以必 须采用关键字比较的排序方法(通常用插入排序) 对每个桶进行排序然后依次将各非空桶内的记录连接(收集)起来即 可16http:/17http:/桶排序main子图18http:/桶排序的实现说明简单的设计就是直接利用random()函数产 生待排数据准备一个10行的二维数组a,每一行就是一个桶将随机数小数后的第一位为09的数字依次放 入这10个桶内很显然，这个算法离不开上一节介绍的

7、插 入排序使用csv格式的文件保存已排序数据，可以 留给其他的应用使用19http:/桶排insert_sort_prepare子图 （I）20http:/桶排insert_sort_prepare子图 （II）21http:/桶排序的输出结果22http:/冒泡排序冒泡排序（Bubble Sort）的基本概念是：将被排序的记录数组a1n垂直排列，每个记 录ai看作是重量为ai所存数值的气泡根据轻气泡不能在重气泡之下的原则，从下往 上扫描数组a：凡扫描到违反本原则的轻气泡 ，就使其向上“飘浮“如此反复进行，直到最后任何两个气泡都是轻 者在上，重者在下为止23http:/24http:/冒泡排序

8、main子图25http:/冒泡算法说明初始状态： a1n为无序区。第一次扫描：从无序区底部向上依次比较相邻的 两个气泡的重量，若发现轻者在下、重者在上， 则交换二者的位置，第一次扫描完毕时，“最轻“ 的气泡就飘浮到该区间的顶部，即关键字最小的 记录被放在最高位置a1上。第二次扫描：扫描a2n。扫描完毕时，“次轻“的 气泡飘浮到a2的位置上。最后，经过n-1 趟扫描可得到有序区a1n26http:/冒泡排序bubble子图27http:/冒泡算法如何改进？假如待排序列已经是基本有序的（只有两 个数字需要换位），如何能够在n-1趟之前 ，结束排序？提示：可以将已经排好的数据，有意调换一对 ，然后

9、使用改进后的算法实验（从文件读入待 排数据）28http:/快速排序快速排序（Quick sort）是在冒泡排序基础 上做了适当的改进快速排序是由C. A. R. Hoare在1962年提出的它采用了分治的策略，是一种划分交换排序算 法被誉为二十世纪“十大经典算法”之一29http:/快速排序的基本思想通过一趟排序将要排序的数据分割成独立 的两部分其中一部分的所有数据都比另外一部分的所有 数据要小然后再按此方法对这两部分数据分别进行快速 排序整个排序过程可以递归进行，从而使整个 数据变为有序序列30http:/31http:/快速排序main子图32http:/快速排序QkSort子图33ht

10、tp:/快速排序QkPass子图34http:/RAPTOR中的快速排序通过实际运行可知，这里实现的“快速排序” 尽管可以改善排序算法的时间复杂性，但 由于全局变量问题，实际上的空间复杂性 很差可以考虑使用非递归的实现来完成“快速排 序”35http:/归并排序归并排序也叫合并排序是分治法一个非常 典型的应用归并排序法是将两个或更多个有序表合并 成一个新的有序表如果是将两个有序表合并成一个有序表， 被称为2-路归并36http:/37http:/归并排序main子图38http:/归并排序input子图（I）39http:/归并排序input子图（II）40http:/归并算法实现的说明待排的

11、两路数据存放在一个文件中，文件中的头 两个数据，分别是两路数据的个数（可以不等长 ）；在得到线形表的长度后，再用两个数组a、b 保存待排数据第一个排序循环过程是对两个数组的元素逐个进 行比对，并输出较小的数据元素；第二个循环过程是在比对输出完成后，仍有一个 线形表的数据尚未输出完毕，所以再将有剩余元 素的数组进行输出41http:/归并排序merge子图（I ）42http:/归并排序merge子图（II）43http:/排序算法的分析冒泡排序显然最容易实现对已经存在的无序线形 表进行排序，所以最为最常见；插入排序对于随机产生的无序数据，可以实现实 时排序；归并排序的前提是存在两个以上已经排序的线形 表；桶排序则适用于可以进行分类的数据排序；快速排序则是最能体现时间复杂性优化的排序算 法，但要关注其在不同的实现环境中，可能因空 间复杂性所带来的问题44http:/排序算法的分析稳定性分类算法名称时间复杂性空间复杂性稳定排序冒泡排序O(n2)O(1)插入排序O(n2)O(1)桶排序O(n)O(k) 空间合并排序O(nlogn)O(n) 空间不稳定排序快速排序O(nlogn)最坏O(n2)稳定性分类算法名称时间复杂性空间复杂性45http:/End of ch5-146http:/