5.3.1 排序的概念、排序算法的思想课件+教案

展开

排序的概念、排序算法的思想教学设计

课程标准和教学目标	排序的概念、排序算法的思想
	教材内容：5.3　排序的概念、排序算法的思想
	适应的课程标准： 1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。
	教学目标： ●了解排序的主要作用，掌握排序的基本概念，知道常用的排序算法。 ●熟练掌握冒泡排序的基本思想，并能应用。		指向的核心素养： ●信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。 ●计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。 ●数字化学习与创新：要使学生较为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。 ●信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。
	学习环境：有教学控制软件的多媒体机房，python编程环境。
	建议课时：1课时
教学活动设计	教学环节	教学过程		设计意图
	情境导入	导入：在一次电视节目上,谷歌总裁施密特提出问题:“如何才能更有效地对一百万个32位长整数进行排序?”同在现场的奥巴马总统立刻响应道:“肯定不能用冒泡排序法。”施密特评价说:"天哪!他是从谁那里听说这个的。”		通过有趣的故事，涉及术语“冒泡排序”，激起学生对排序的兴趣，对排序概念形成初步认识，同时对“冒泡排序”是什么产生强烈好奇心。
	学习任务一	●学习任务一：什么是排序问题：我们在日常生活中会经常经历排序的场景，比如体育课上按身高排列等等熟悉的生活体验。这种熟悉的经验，在计算机中的排序又有哪些？引导学生思考并回答问题。可以让学生列举一些计算中经常使用到排序实例。如：文件夹中图片文件可分别按名称、大小、类型、修改日期等方式进行排序；电子邮件列表一般按照日期排序，最新的邮件被放置在最顶端；购物网站上搜索到的某类商品可按价格、销量、信用等方式进行排序。设问：计算机要对数据排序，先要考虑数据的组织形式。如果有一组数（23，20，13，18，14，11）分别存储以数组、链表的形式，排序有什么不同呢？设问：为了分析问题方便，我们以后假设数据以数组形式存储，然后讨论它的排序算法。排序的基本要求是什么？对上面的数组d进行按升序排序后，数组d中数据的存储情况变为如图所示。排序后的数据存储情况教师总结：排序（sorting）就是整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。在排序的过程中，序列里的数据元素的值保持不变，但其排列顺序可能改变。		设计意图：尽管学生对排序并不陌生，但如何严谨地定义排序，并与数据在计算机中存储形式结合起来思考问题，还需要进一步清晰化。通过三个问题，串起排序的作用与意义、数据排序的组织形式、排序的概念与要求等等。
	学习任务二	前面奥巴马总统提到的“冒泡排序”，它是如何进行的呢？ 1. 冒泡排序的一般过程动画演示。使用现成的数字化学习工具，直观展示“冒泡排序”的动画。考虑一般情形，讲解冒泡排序第一遍的加工过程：冒泡排序算法对数组d的第一遍加工过程设问：经过第一遍加工，是否能够确保数据中的最大元素下沉到最下面？ 2. 设计算法可以安排小活动，比如打印6个数字卡片，让6位学生手持卡片，完成冒泡排序的整个过程。在理解冒泡排序算法思想的基础上，引导学生探究程序的实现过程，进一步理解数据排序的思想和方法。 3. 冒泡排序的自然语言描述老师展示动画后，让学生自主探究、相互启发，总结其规律，概括其算法，体现课堂的生成性。设问1：若要排序的数有n个，最少需要进行几遍？设问2：对于第一遍加工的基本过程，能用自然语言描述吗？设问3：完整的冒泡排序，你能使用语言描述清楚吗？教师总结：若要排序的数有n个，则需要n-1遍加工，第j遍加工中，从第一个数开始，相邻两数比较，若反序则交换两者的位置；直到第n+1-j个数为止，第一个数与第二个数比较，第二个数与第三个数比较，......，第n-j个与第n+1-j个比较，共比较n-j次。此时第n+1-j个位置上的数已经按要求排好，所以不参加以后的比较和交换操作。对n个元素的数组，用冒泡法进行排序时，共需比较 (n-1)+(n-2)+…+1=次其时间复杂度为O（n2）。设问4：冒泡排序算法的每一遍加工中，最小的元素“上浮”和最大的元素“下沉”这两种方式在程序实现时有何区别？		欣赏动画，了解冒泡排序的一般过程。首要是寻找和发现冒泡排序的一般规律。能够由第一遍加工概括出一般规律，通过类推，实现整个排序过程。通过第一遍加工的细致分析，学生得到具体到抽象的基本思维训练。设计意图：重点在于第一遍加工处理，这个过程清楚了，那么对于后面的每遍加工，遵循同样的规则，以此类推，即可实现数据的完整排序。设计意图：弄清楚冒泡排序的基本思想与方法，是本节的重点与难点，可以多花些时间，总结规律，并用自然语言准确地表达算法的操作步骤。这是下一节的重要铺垫。
	拓展学习	建议引入“选择排序”的基本思想与方法。并与冒泡排序相比较，分析为什么奥巴马总统说:“肯定不能用冒泡排序法。”		设计意图：与导入相响应，引入算法的时间复杂度的分析，以及对比较次数、交换次数的细致分析。
	课堂小结	知识梳理 1. 排序的基本概念； 2. 冒泡排序的基本思想与方法； 3. 冒泡排序的时间复杂度分析及其特点		为下节引入程序实现做好铺垫。
	作业布置	基础作业（面向所有学生）：举例说明冒泡排序每一遍处理的结果。		课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。
教学设计思路	本节建议重点关注计算思维的培养与提高。数据排序是计算机中常见操作，排序的算法内容极为丰富，应用极为广泛。它是很多算法的重要组成部分，在许多算法里需要对数据先进行排序。比如二分查找等。建议从排序应用的典型场景从发，启发学生培养对排序的重要性和作用的意识，在分析数据存储形式的基础上，以数组中数据排序为例，体会排序的具体思想与方法。再以冒泡排序为例，引导学生深入体会排序的基本方法。
针对核心素养培养的设计考虑	信息意识、信息社会责任：本节课在导入时选择了一则小故事，调动学生深入探究的兴趣；然后通过学生思考并举例，列举、回顾学生生活与身边的排序相关的真实场景，引入计算机编程中常用的排序用途与定义，进而增强学生对排序具有广泛应用场景的认识。计算思维：首先，数据采用数组或者链表形式存储与排序算法的操作密切相关，这一点与本章第一节有紧密联系。其次，排序的基本定义。“排序”的定义包括两个重要方面：数据的物理存储结构、排序后数据之间的逻辑关系（有序）进行了梳理，重点在于培养学生对专业知识的科学严谨态度。而后介绍的冒泡排序，主要通过动画“模拟”的形式，直观呈现冒泡排序的一般过程。最后通过让学生参与其中，发现并描述整个排序过程，让学生总结其规律，概括其算法，体现课堂的生成性。这个模拟——抽象——概括的过程，能够较好地训练学生思维。数字化学习与创新：教师使用“冒泡排序”、“选择排序”动画，直观展示“冒泡排序”、“选择排序”的完整过程，学生可以使用思维导图软件描述算法的基本过程，从中整理思路、总结规律。