数据结构与算法分析.ppt

第7章排序 7 1概述7 2插入排序7 3交换排序7 4选择排序7 5归并排序7 6外部排序7 7各种内排序方法的比较和选择 7 1概述 7 1 1排序的基本概念所谓排序就是整理文件中记录 使之按关键字递增 或递减 次序排列起来其确切的定义如下 假设含n个记录的序列为 R1 R2 Rn 其相应的关键字序列为 K1 K2 Kn 需确定1 2 n的一种排列Ri1 Ri2 Rin 使其相应的关键字满足Ki1 Ki2 Kin 或Ki1 Ki2 Kin 的关系 7 1概述 排序的对象 排序的对象是文件 它由一组记录组成 每条记录则由一个或若干个数据项 或域 组成排序运算的依据 所谓关键字项就是可用来标识一个记录的一个或多个组合的数据项 该数据项的值称为关键字 Key 需注意的是在不易产生混淆时 可将关键字项简称为关键字 用来作排序运算依据的关键字 可以是数字类型 也可以是字符类型 关键字的选取应根据问题的要求而定 7 1概述 7 1 2排序的稳定性当待排序记录的关键字均不相同时 排序结果是惟一的 否则排序结果不惟一 在待排序的文件中 若存在多个关键字相同的记录 经过排序后这些具有相同关键字的记录之间的相对次序保持不变 该排序方法是稳定的 若具有相同关键字的记录之间的相对次序发生变化 则称这种排序方法是不稳定的 排序算法的稳定性是针对所有输入实例而言的 即在所有可能的输入实例中 只要有一个实例使得算法不满足稳定性要求 则该排序算法就是不稳定的 7 1概述 7 1 3排序的分类按在排序过程中是否涉及数据的内 外存交换来分类 排序大致分为两类 内部排序和外部排序 对于外排序 可以进一步的分为两种方法 合并排序法直接合并排序法对于内排序 按策略进行划分 可以分为 插入排序选择排序交换排序归并排序分配排序 7 1概述 7 1 4排序算法分析分析排序算法时 传统方法是衡量关键字之间进行比较的次数排序算法分析应该考虑比较的次数和数据移动的次数并不总是需要或是可能确定比较的准确次数 因此只能计算一个近似值可以根据实际条件选择使用哪一种算法 7 2插入排序 7 2 1直接插入排序1 基本思想2 插入算法3 Java程序4 直接插入排序法的算法分析 1 算法的时间性能分析 2 算法的空间复杂度分析 3 直接插入排序的稳定性 7 2插入排序 7 2 2希尔排序1 基本思想2 具体算法3 希尔排序的算法分析 1 增量序列的选择 2 Shell排序的时间性能优于直接插入排序 7 2插入排序 希尔排序的时间性能优于直接插入排序的原因 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少 当n值较小时 n和n2的差别也较小 即直接插入排序的最好时间复杂度O n 和最坏时间复杂度0 n2 差别不大 在希尔排序开始时增量较大 分组较多 每组的记录数目少 故各组内直接插入较快 后来增量di逐渐缩小 分组数逐渐减少 而各组的记录数目逐渐增多 但由于已经按di 1作为距离排过序 使文件较接近于有序状态 所以新的一趟排序过程也较快 因此 希尔排序在效率上较直接插人排序有较大的改进 3 稳定性希尔排序是一种不稳定排序方法 7 3交换排序 7 3 1冒泡排序1 基本思想2 具体算法3 Java程序4 冒泡排序的算法分析 1 算法的最好时间复杂度 2 算法的最坏时间复杂度 3 算法的平均时间复杂度为O n2 4 算法稳定性 7 3交换排序 5 冒泡排序的算法改进 1 记住最后一次交换发生位置lastExchange的冒泡排序 2 改变扫描方向的冒泡排序 冒泡排序的不对称性 造成不对称性的原因 改进不对称性的方法 7 3交换排序 7 3 2快速排序1 基本思想2 具体算法3 算法分析 1 最坏时间复杂度 2 最好时间复杂度 3 基准关键字的选取 三者取中 的规则 取位于low和high之间的随机数k low k high 用R k 作为基准 4 平均时间复杂度 5 空间复杂度 6 稳定性 7 4选择排序 7 4 1直接选择排序1 基本思想2 具体算法3 直接选择排序的算法分析 1 关键字比较次数 2 记录的移动次数 3 直接选择排序是一个就地排序 4 稳定性分析 7 4选择排序 7 4 2堆排序1 基本思想2 具体算法3 算法分析 7 5归并排序 1 基本思想2 实现方法3 算法分析 1 稳定性 2 存储结构要求 3 时间复杂度 4 空间复杂度 7 6外部排序 7 6 1辅助存储器的存取1 磁盘信息的存取 磁盘是一种直接存取的存储设备 它是以存取时间变化不大为特征的2 磁带信息的存取 磁带是薄薄涂上一层磁性材料的一条窄带3 缓冲技术 操作系统使用了缓冲技术 可解决以下问题 1 解决信息的到达率和离去率不一致的矛盾 2 缓存起中转站的作用3 使得一次输入的信息能多次使用 7 6外部排序 7 6 2外部排序的方法如果你的操作系统支持虚拟存储 最简单的外部排序方法是把整个文件读入虚拟存储器中 然后运行一个内部排序方法调整内部排序算法使之应用于外部排序 这种思路的更普遍的问题是这样做不可能比设计一个新的尽量减少磁盘存取的算法更有效 进行外部排序的一个更好的方法源于归并排序 7 7各种内排序方法的比较和选择 判断内排序方法的性能的标准 1 评价排序算法好坏的标准 评价排序算法好坏的标准主要有两条 执行时间和所需的辅助空间 算法本身的复杂程度 2 排序算法的空间复杂度若排序算法所需的辅助空间并不依赖于问题的规模n 即辅助空间是O