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

《《数据结构[Python语言描述]》教案第17课排序（9.1-9.3）.docx》由会员分享，可在线阅读，更多相关《《数据结构[Python语言描述]》教案第17课排序（9.1-9.3）.docx（7页珍藏版）》请在优知文库上搜索。

1、课题第17课排序(9.1-93)课时2课时(90min)教学目标知识目标：(1)了解排序的相关概念(2)掌握插入排序的两种典型算法直接插入排序和希尔排序的过程及算法实现(3)掌握交换排序的两种典型算法冒泡排序和快速排序的过程及算法实现技能目标：能利用插入排序、交换排序算法解决实际应用中的排序问题素质目标：加强实践练习，注重学思结合、知行统一教学重难点教学重点：排序概述、插入排序教学睚点：插入排序教学方法问答法、讨论法、i并授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：什么是排

2、序？排序的目的是什么？【学生】思考、举手回答传授新知【教师】通过学生的回答引入要讲的知识，介绍排序概述、插入排序、交换排序9.1 排序概述排序是指将一个数据元素的任意序列按关键字的递增或递减次序重新排列起来，使其成为一个按关键字有序排列的序列.(1)排序的分类.排序可分为两类，分别是内部排序和外部排序.内部排序是指W待排序雌元素完全放置在计算机内存中进行排序；外部排序是指因待排序数据元素数量较大，排序过程中不仅需要占用内存，还需要借助外存来进行排序。(2)排序的稳定性。假设待排序数据元素序列中存在两个及以上关键字相同的数据元素,若经过排序后，这些数据元素的相对次序保持不变，则称所用的排序算法是

3、稳定的；反之，若经过排序后，这些数据元素的相对次序发生变化，则称所用的排序算法是不稳定的。(3)排序算法的性能评价。通常情况下，使用时间复杂度、空间复杂度和稳定性来综合衡量一个排序算法性能的高低.9.2 插入排序【教师】随机邀请学生回答以下问题什么是插入排序？*【学生】聆听、思考、回答插入排序是指将待排序数据元素按其关键字大小插入有序序列的合适位置，直到全部数据元素均完成插入.9.2.1 直接插入排序直接插入排序是一种最简单的排序算法，其基本思想是将待排序数据元素按其关键字大小插入已排好序的有序表中，从而得到一个新的有序表。1.排序过程对于一个具有个数据元素的序列丽,无必,当,直接插入排序的具

4、体过程如下。(1)初始状态下，将数据元素丽看作有序表，将(仇,2.,为看作无序序列。(2A各无序序列中第一个佛E序数据元素的关键字攵”依次与有序表中数据元素的关键字进行比较，将所有关键字大于的数据元素依次向后移动一个位置，直到某个数据元素的关键字小于或等于Z”时，此时将关键字为的数据元素插入关键字小于或等于4”的数据元素后面,即可完成第一个数据元素的插入。此时，有序表扩充一个数据元素，无序序列减少一个数据元素。(3)重复步骤(2),经过T趟排序后，最终得到一个按关键字递增有序的数据元素序列。【算法描述】详见教材【教师】讲解实例9-1(详见教材)，并介绍直接插入排序的过程2.算法分析(1)时间复

5、杂度.直接插入排序花费的时间主要由关键字的比较和数据元素的移动这两部分构成，因此，数据元素最初的位置直接影响算法花费的时间。(2)空间复杂度。由于直接插入排序仅使用了一个辅助变量，与问题规模无关，故其空间复杂度为O。(3)稳定性。使用直接插入排序后，后面的数据元素不会移到具有相同关键字的数据元素前面。因此，直接插入排序是一种稳定的排序算法。(详见教材)9.2.2希尔排序希尔排序是在直接插入排序的基础上进行改进的排序算法，其基本思想是首先将待排序数据元素序列划分为若干个子序列，其中每个子序列由相隔某个“增量的数据元素组成；然后对这些子序列分别进行直接插入排序；接着通过不断缩小增量”对子序列进行调

6、整，直到当整个序列基本有序时，再对全部数据元素进行一次直接插入排序。1 .排序过程对于一个具有个数据元素的序列加,出at,.lan.l,希尔排序的具体过程如下。(1)按选定增量d1(dn)将所有距离为cK的数据元素划分为一个子序列，对各子序列进行直接插入排序。(2)按选定增量d2d2ch)对所有健元素重新划分子序列，并对各子序列进行直接插入排序。(3)以此类推，直到增量cfl-=l,即将所有数据元素放在一个子序列中进行直接插入排序，最终得到一个按关键字递增有序的数据元素序列。【算法描述】详见教材【教师】讲解实例9-2(详见教材)，并介绍希尔排序的过程2 .算法分析(1)时间复杂度。希尔排序的时

7、间复杂度由所选取的增量序列决定。希尔排序的时间复杂度难以分析，一般认为其平均时间复杂度为0(2)。(2)空间复杂度。由于希尔排序仅使用了一个辅助变量，与问题规模无关，故其空间复杂度为0(1).(3)稳定性。希尔排序在移动数据元素时采取跳跃式移动，使用希尔排序后，后面的数据元素可能会移到具有相同关键字的数据元素前面。因此，希尔排序是一种不稳定的排序算法。(详见教材)【拓展阅读】当使用算法解决实际应用问题时，如果同一个问题采用不同的算法实现，那么解决问题的效率也是不同的。因此，人们不断自主探究算法的优化与改进，以使问题获得高效解决。在这样的过程中，努力创新、精益求精、追求卓越的精神值得每个人学习.

8、*【教师】随机邀请学生回答以下问题分析直接插入排序与希尔排序的优缺点。*【学生】聆听、思考、回答9.3交换排序【教师】随机邀请学生回答以下问题什么是交换排序？+【学生】聆听、思考、回答交换排序是指两两比较待HE序孀元素的关键字，一旦发现这两个数据元素不满足次序要求时就进行交换，直到整个序全部满足次序要求.9.3.1 冒泡排序冒泡排序是一种简单的交蹴E序算法，其基本思想是依次比较相邻两个数据元素的关键字大小，如果逆序，则交换它们的位置，从而逐步将无序序列变成有序序列。1.排序过程对于一个具有4个数据元素的序列龙贝,all.an-l冒泡排序的具体过程如下。(1)对待排序数据元素序列进行第一趟排序，

9、依次比较相邻两个数据元素的关键字大小，如果前面数据元素的关键字大于后面数据元素的关键字，则将它们交换，这样具有较大关键字的数据元素将不断后移.最终，具有最大关键字的数据元素移到最后一个位置.(2)第二趟排序仅针对前n-1个数据元素，重复以上操作，使具有次大关键字的数据元素移到倒数第二个位胤(3)以此类推，直到某一趟排序过程中没有发生数据元素的交换，则可结束冒泡排序。因此，冒泡排序最多进行n-1趟排序。【算法描述】详见教材【教师】讲解实例9-3(详见教材)，并介绍冒泡排序的过程2.算法分析(1)时间复杂度。冒泡排序花费的时间主要由关键字的比较和数据元素的移动这两部分构成。冒泡排序的时间复杂度为0

10、(2)(2)空间复杂度。由于冒泡排序仅使用了一个辅助变量，与问题规模n无关，故其空间复杂度为0(1),(3)稳定性。在冒泡排序过程中，相邻两个孀元素进行比较时，只有具有较大关键字的数据元素才向后移动，这就保证了具有相同关键字的数据元素的相对位置不会发生变化。因此，冒泡排序是一种稳定的排序算法。(详见教材)9.3.2快速排序快速排序是由冒泡排序改进而来的，其基本思想是从待排序数据元素序列中选取一个数据元素作为基准，通过一趟排序将待排序数据元素序列分成两部分，一部分数据元素的关键字都小于基准数据元素的关键字，而另一部分数据元素的关键字都大于基准数据元素的关键字。然后对各部分不断划分，直到整个序列按

11、关键字有序排列。1 .排序过程对于一个具有0个数据元素的序列为,aa,l.lan.1l快速排序的具体过程如下。(1)设置两个变量和high,分别记录待排序数据元素序列的起始位置和终止位置。同时选取待WE序数据元素序列的第一个数据元素IiStMo叼作为基准.(2)从位置打。力开始从后向前依次扫描，若数据元素的关键字大于或等于基准关键字，则力/。力向前移动一个位置,直到数据元素的关键字小于基准关键字，将该数据元素移到位置Iowk,同时low加Ie(3)从位置/。山开始从前向后依次扫描，若数据元素的关键字小于或等于基准关键字，则ow向后移动T位置，直到数据元素的关键字大于基准关键字,将该数据元素移到

12、位置high上,同时high减1。(4)重复步骤(2)和步骤(3)重心w=high,将基准关键字放到位置/。卬上.此时，以listovM为基准将待排序数据元素序列划分为前后两部分，第一次划分完成。(5)参照以上方法，对各部分不断划分，直到各部分中只有一个数据元素，表示整个序列排序完成。【算法描述】详见教材【教师】讲解实例9-4(详见教材)，并介绍快速排序的过程2 .算法分析(1)时间复杂度。快速排序花费的时间主要取决于排序的趟数。快速排序的时间复杂度为0(川。国八)。(2)空间复杂度。在最好情况下为O(log2”),在最坏情况下为0(”).(3)稳定性。使用快速排序后，后面的数据元素可能会移到

13、具有相同关键字的数据元素前面。因此,快速排序是一种不稳定的排序算法。【教师】随机邀请学生回答以下问题分析冒泡排序与快速排序的优缺点。【学生】聆听、思考、回答【学生】聆听、思考、理解、记录任务实施任务1利用直接插入排序算法对学生成绩表进行排序【教师】描述问题，分析问题，要求学生完成任务【问题描述】设计算法创建一个学生成绩表(其中每个学生的成绩信息包括学号、姓名、计算机基础成绩、c语言程序设计成绩、数据结构成绩)，利用直接插入排序算法按总成绩对学生成绩表进行排序。【问题分析】创建一个顺序表存储学生的成绩信息，首播入学生人数确定要创建的顺序表长度；然后依次录入每个学生的成绩信息，并计算出其总成绩；最

14、后以总成绩为关键字进行直接插入排序，并逆序显示排序后的成绩表。【学生】按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题任务2利用冒泡排序算法对学生成绩表进行排序【教师】描述问题，分析问题,安丹浮生扫描微课二维码现看视频“利用冒泡排序算法对学生成绩表进行排序”（详见教材），要求学生完成任务【问题描述】设计算法创建一个学生成绩表（其中每个学生的成绩信息包括学号、姓名、计算机基础成绩、C语言程序设计成绩、雌结构成绩），利用冒泡排序算法按总成绩对学生成绩表进行排序。【问Sg分析】创建一个顺序表存储学生的成绩信息，首先输入学生人数确定要创建的顺序表长度；然后依次录入每个学生的成绩信息，并计算出其总成绩；最后以总成绩为关键字进行冒泡排序，并逆序显示排序后的成绩表。【学生】自行扫码观看配套微课，按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点排序概述插入排序：直接插入排序、希尔排序交换排序：冒泡排序、快速排序【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的相关练习。【学生】完成课后任务教学反思