《数据结构[Python语言描述]》教案第18课排序（9.4-9.5）.docx

课题第18课排序(949.5)课时2课时(90min)教学目标知识目标：(1)掌握选择排序的两种典型算法直接选择排序和堆排序的过程及算法实现(2)掌握归并排序的过程及算法实现技能目标：能用选择排序和归并排序算法解决实际应用中的排序问题素质目标：加强实践练习，注重学思结合、知行统一教学重难点教学重点：选择排序、归并排序教学难点：选择排序、归并排序教学方法问答法、讨论法、讲授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：什么是选择排序？【蚂思考、传授新知【教师】通过学生的回答引入要讲的知识，介绍选择排序、归用F序9.4选择排序选择排序是指不断从例E序数据元素序列中选出关键字最小的数据元素，并将其按顺序放在有序序列的最后，直到整个序列完全有序。9.4.1 直接选择排序直接选择排序的基本思想是通过关键字的比较，每次从例E序数据元素序列中选出关键字最小的数据元素，将其与待排序数据元素序列的第一个数据元素交换，直到全部数据元素都有序列.1.排序过程(1)从例E序数据元素序列中选择关键字最小的数据元素，将其与第一个数据元素进行交换。(2)从剩余待排序数据元素序列中继续选择关键字最小的数据元素，将其与第二个数据元素进行交换.(3)以此类推，直到得到一个按关键字递增有序的数据元素序列。【算法描述】defSelectSort(Self):#直接选择排序foriinrange(self.Ien-1):#进行n-1趟排序tmp-i#寻找关键字最小的数据元素的位置forjinrange(i+1,self.len):ifself.listj.key<self.listtmp.key:tmp=j#交换位置iftmp!=i:self.listi,self.listtmp=self.listtp,self.listi÷【教师】讲解实例9-5(详见教材)，并介绍直接选择排序的过程2.算法分析(1)时间复杂度。直接选择排序的时间复杂度为0()(2)空间复杂度。由于直接选择排序仅使用了一个辅助变量，与问题规模无关，故其空间复杂度为。(3)稳定性。直接选择排序是一种不稳定的排序算法。(详见教材)【教师】随机邀请学生回答以下问题直接选择排序有什么优缺点？÷【学生】聆听、思考、回答9.4.2堆排序堆排序是直接选择排序的改进，它属于树形选择排序方法。1 .堆的定义n个关键字序列/、依、公，当且仅当该序列满足如下性质时称为堆。(of<2j-i)若将此序列看作一棵完全二叉树，则堆实质上是满足如下性质的完全二叉树：树中任意一个非叶子结点的关键字均小于等于或大于等于其左、右孩子结点的关键字.其中，前者称为小根堆，后者称为大根堆。2 .排序过程堆排序的基本思想是首先将待排序数据元素序列初始化为大根堆(或小根堆)，然后将堆顶结点与最后一个叶子结点交换位置并将该叶子结点的数据元素输出；最后将剩余结点重新调整为大根堆(或小根堆)，重复以上操作，直到所有数据元素均输出。对于一个具有n个数据元素的序列(如3,2,堆排序(此处以递减序列，即创建大根堆为例)的具体过程如下。1)创建堆(1)将待排序数据元素序列构造成一棵完全二叉树，从最后一个非叶子结点(即第1个结点)开始，检查该结点是否满足大根堆的要求。(2)采用同样的方法继续调整其他非叶子结点，若与该结点交换的是非叶子结点，交换后可能使其不符合堆的定义，则还需对与该结点交换的结点的孩子结点进一步调整，使得完全二叉树仍然满足大根堆的要求。(3)重复以上步骤，直到完全二叉树初始化为一个大根堆。2)堆排序(1)将堆顶结点与最后一个叶子结点交换.(2)输出该叶子结点对应的数据元素并使其脱离堆。(3)将剩余数据元素组成的数据元素序列按创建堆的方法重新调整为大根堆。(4)重复以上步骤，直到所有数据元素有序输出.【算法描述】详见教材÷【教师】讲解实例9-6(详见教材)，并介绍堆排序的过程3.算法分析(1)时间复杂度。堆排序花费的时间主要由建立初始堆和反复重建堆这两部分构成，它们均是通过调用sift()方法实现的。堆排序的时间复杂度为O(dog20.(2)空间复杂度。由于堆排序仅使用了一个辅助变量，与问题规模无关，故其空间复杂度为O(I)e(3)稳定性。使用堆排序后，后面的数据元素可能会移到具有相同关键字的数据元素前面。因此，堆排序是一种不稳定的排序算法。(详见教材)9.5归吊晦"归并"是指将若干有序表合并成一个新的有序表。归并排序就是利用“归并"技术进行的排序，其中有序表个数为2的归并排序称为二路归并排序，其他称为多路归并排序。1 .排序过程对于一个具有n个数据元素的序列的.,M,.,s,二路归并排序的具体过程如下。(1)将待排序数据元素序列中的数据元素看成n个长度为I的有序子表，然后对其进行两两相邻有序子表的归并，即第1个子表与第2个子表归并，第3个子表与第4个子表归并，以此类推，从而得到/2个长度为2的有序表(若n为奇数，则最后一个有序表的长度为1)。(2继续进行两两归并从而得到/旬个长度为4的有序表(最后一个有序表的长度可能小于41(3)以此类推，直到得到一个长度为n的有序表。【算法描述】详见教材÷【教师】讲解实例9-7(详见教材)，并介绍归并排序的过程2 .算法分析(1)时间复杂度。归并排序的时间复杂度为0(mOg却。(2痊间复杂度。归并排序过程中需要一个与待排序雌元素序列等长的辅助单元来存放数据元素，故其空间复杂度为0(”).(3)稳定性。归并排序不会改变具有相同关键字的数据元素的相对位置。因此，归并排序是一种稳定的排序算法。(详见教材)【教师】随机邀请学生回答以下问题归并排序有什么优缺点？【学生】聆听、思考、回答【学生】聆听、思考、理解、记录任务一利用直接选择排序算法对学生成绩表进行排序【教师】描述问题，分析问题，要求学生完成任务【问题描述】设计算法创建一个学生成绩表(其中每个学生的成绩信息包括学号、姓名、计算机基础成绩、任务实施<C语言程序设计成绩、数据结构成绩)，利用直接选择排序算法按总成绩对学生成绩表进行排序。【问题分析】创建一个顺序表存储学生的成绩信息，首先输入学生人数确定要创建的顺序表长度；然后依次录入每个学生的成绩信息，并计算出其总成绩；最后以总成绩为关键字进行直接选择排序，并逆序显示排序后的成绩表。【学生】按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点选择排序：直接选择排序、堆排序归并排序【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的剩余练习。【学生】完成课后任务教学反思