数据结构课件-第九章.pptVIP

9.5.2 堆排序 1、大根堆的定义：若将堆看成是一棵完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不小于其左、右孩子结点的值。堆顶元素为最大值。 2、小根堆的定义：若将堆看成是一棵完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于其左、右孩子结点的值。堆顶元素为最小值。 9.5.2 堆排序 3、筛选的定义：将根结点值与左、右子树的根结点值进行比较，并与其中小者（大者）进行交换；重复上述操作，直至叶子结点，将得到新的堆。 4、排序过程描述： ①从无序序列的第?n/2?个元素（即此无序序列对应的完全 二叉树的最后一个非终端结点）起，至第一个元素止，进 行反复筛选。 ②输出堆的根结点之后，以堆中最后一个元素替代之，调整 剩余元素成为一个新的堆。 9.5.2 堆排序 5、举例：对序列{76,50,65,49,97,15,38,27 }进行堆排序。 9.5.2 堆排序 5、举例：对序列{76,50,65,49,97,15,38,27 }进行堆排序。 堆排序适合于待排序的记录较多的情况，而对于堆记录数目较少的文件并不提倡。堆排序是不稳定的排序方法。 9.6 归并排序 一、归并排序 2、排序过程描述 ①设初始序列含有n个记录，则可看成n个有序的子序列，每 个子序列长度为1； ②两两合并，得到?n/2?个长度为2或1的有序子序列； ③再两两合并，如此重复，直至得到一个长度为n的有序序 列为止。 1、2-路归并排序定义:将两个位置相邻的有序子序列归并为一个有序的序列。 9.6 归并排序 一、归并排序 3、举例：对序列{49,38,65,97,76,13,27进行归并排序。 9.7 各种排序方法比较 一、时间复杂度比较 排序方法 平均情况 最好情况 最坏情况 直接插入排序 O(n2) O(n) O(n2) 希尔排序 O(nlog2n) O(n1.3) O(n2) 冒泡排序 O(n2) O(n) O(n2) 快速排序 O(nlog2n) O(nlog2n) O(n2) 直接选择排序 O(n2) O(n2) O(n2) 堆排序 O(nlog2n) O(nlog2n) O(nlog2n) 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) 二、空间复杂度比较 排序方法 辅助空间 直接插入排序 O(1) 希尔排序 O(1) 冒泡排序 O(1) 快速排序 O(log2n)～O(n) 直接选择排序 O(1) 堆排序 O(1) 归并排序 O(n) 三、稳定性比较 排序方法 稳定性 直接插入排序 稳定 希尔排序 不稳定 冒泡排序 稳定 快速排序 不稳定 直接选择排序 不稳定 堆排序 不稳定 归并排序 稳定 9.8 回到工作场景 通过学习，同学们应该已经掌握了各种排序算法的定义以及实现代码，足以完成工作场景中的任务。下面回到9.1节的工作场景中，完成工作任务。 【工作过程一】项目分析与算法流程设计 ： 【工作过程二】编写代码： 【工作过程3】系统运行 9.9 应用实践：内部排序的综合应用 3.6.1嵌入式系统中断模拟设计 1. 实践内容 输入待排序记录关键字，选择不同的排序方式（插入排序、希尔排序、冒泡排序、快速排序、选择排序等），按递增方式实现数据的排序。 2. 实践目的 掌握各种内部排序算法。 培养学生利用排序的相关知识解决实际问题的能力。 3、实践过程 数据结构 主编 许绘香 段明义 中国水利水电出版社 第九章 排序 在查找中为了查找方便，通常希望待查找的数据表是按关键字有序的。就是说通过排序，可以为查找提供方便，也可以提高查找的效率，还可以提高数据表的直观性。所以我们需要对数据表进行排序。排序的应用领域十分的广泛，例如电话薄、档案、图书馆的图书、各种词典的目录表等等都要用到排序。 9.1工作场景导入  【工作场景】 一个学生成绩管理模块中，学生信息主要包括包括学号、数学成绩、C语言成绩、英语成绩和总成绩内容，输入学生信息后，要求按照总成绩从高到低的顺序输出，请编写程序实现之，得到如9-1-1所示的输出结果。 【引导问题】 （1）如何选择合适的排序算法 （2）如何实现该排序功能，效率如何？ 9.2 排序的基本概念 1、排序的定义：假设含n个记录的序列为{ R1, R2, …,Rn }， 按照关键字的递增（或递减），记录将形成新的序列为 { Rp1, Rp2, …，Rpn }。 2、举例 关键字：12，45，9，23，90，77，65 调整为：9，12，23，45，65，77，90 学号 姓名