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

桶排序的输出结果 * 冒泡排序 冒泡排序（Bubble Sort）的基本概念是： 将被排序的记录数组a[1..n]垂直排列，每个记录a[i]看作是重量为a[i]所存数值的气泡 根据轻气泡不能在重气泡之下的原则，从下往上扫描数组a[]：凡扫描到违反本原则的轻气泡，就使其向上飘浮“ 如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止 * * 冒泡排序main子图 * 冒泡算法说明 初始状态： a[1..n]为无序区。 第一次扫描：从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置，第一次扫描完毕时，最轻的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置a[1]上。 第二次扫描：扫描a[2..n]。扫描完毕时，次轻的气泡飘浮到a[2]的位置上……。 最后，经过n-1 趟扫描可得到有序区a[1..n] * 冒泡排序 bubble子图 * 冒泡算法如何改进？ 假如待排序列已经是基本有序的（只有两个数字需要换位），如何能够在n-1趟之前，结束排序？ 提示：可以将已经排好的数据，有意调换一对，然后使用改进后的算法实验（从文件读入待排数据） * 快速排序 快速排序（Quick sort）是在冒泡排序基础上做了适当的改进 快速排序是由C. A. R. Hoare在1962年提出的 它采用了分治的策略，是一种划分交换排序算法 被誉为二十世纪“十大经典算法”之一 * 快速排序的基本思想 通过一趟排序将要排序的数据分割成独立的两部分 其中一部分的所有数据都比另外一部分的所有数据要小 然后再按此方法对这两部分数据分别进行快速排序 整个排序过程可以递归进行，从而使整个数据变为有序序列 * * 快速排序main子图 * 快速排序QkSort子图 * 快速排序QkPass子图 * RAPTOR中的快速排序 通过实际运行可知，这里实现的“快速排序”尽管可以改善排序算法的时间复杂性，但由于全局变量问题，实际上的空间复杂性很差 可以考虑使用非递归的实现来完成“快速排序” * 归并排序 归并排序也叫合并排序是分治法一个非常典型的应用 归并排序法是将两个或更多个有序表合并成一个新的有序表 如果是将两个有序表合并成一个有序表，被称为2-路归并 * * 归并排序main子图 * 归并排序input子图（I） * 归并排序input子图（II） * 归并算法实现的说明 待排的两路数据存放在一个文件中，文件中的头两个数据，分别是两路数据的个数（可以不等长）； 在得到线形表的长度后，再用两个数组a[]、b[]保存待排数据 第一个排序循环过程是对两个数组的元素逐个进行比对，并输出较小的数据元素； 第二个循环过程是在比对输出完成后，仍有一个线形表的数据尚未输出完毕，所以再将有剩余元素的数组进行输出 * 归并排序merge子图（I） * 归并排序merge子图（II） * 排序算法的分析 冒泡排序显然最容易实现对已经存在的无序线形表进行排序，所以最为最常见； 插入排序对于随机产生的无序数据，可以实现实时排序； 归并排序的前提是存在两个以上已经排序的线形表； 桶排序则适用于可以进行分类的数据排序； 快速排序则是最能体现时间复杂性优化的排序算法，但要关注其在不同的实现环境中，可能因空间复杂性所带来的问题 * 排序算法的分析 稳定性分类 算法名称 时间复杂性 空间复杂性 稳定排序 冒泡排序 O(n^2) O(1) 插入排序 O(n^2) O(1) 桶排序 O(n) O(k) 空间 合并排序 O(nlogn) O(n) 空间 不稳定排序 快速排序 O(nlogn) 最坏O(n^2) 稳定性分类 算法名称 时间复杂性 空间复杂性 * End of ch5-1 * 第5章 排序与查找PART A 《可视化计算》 学习目标 如何在计算机中进行排序? 排序算法有那些分类? 如何实现常用的排序算法? 查找与排序有何关系? 查找算法有哪些分类? 如何实现常用的查找算法？ * 何为排序? 学习中的排序： 在一些教课书中，会将涉及到的所有术语排成索引，作为附录，方便读者在需要时查找 图书馆工作人员的重要工作，就是把归还的书，插入适当的书架、层次、位置, 方便读者查阅 社会中排序： 会议代表名单的排序（按姓氏笔画）； 联大会议的发言顺序（按国家名称字母排序） * 计算机如何进行排序？ 从”混沌”到有序：排序自身也是一种应用,同时也为快速的查找提供必要的准备 在计算机科学中，排序(sorting)是研究最多的问题之一 基本排序算法有5类： 插入排序，例如，直接插入排序，二分插入排序等； 交换排序，例如，冒泡排序，快速排序等； 选择排序，例如，选择排序，推排序等 归并排序，例如，归并排序，