5.3 数据排序 教学设计（3课时表格式）-2023新浙教版《高中信息技术》选择性必修第一册.rar

排序的概念、排序算法的思想教学设计排序的概念、排序算法的思想教学设计排序的概念、排序算法的思想教材内容：教材内容：5.3排序的概念、排序算法的思想适应的课程标准：适应的课程标准：1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。教学目标：教学目标：了解排序的主要作用，掌握排序的基本概念，知道常用的排序算法。熟练掌握冒泡排序的基本思想，并能应用。指向的核心素养：指向的核心素养：信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。数字化学习与创新：要使学生较为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。学习环境：学习环境：有教学控制软件的多媒体机房，python 编程环境。课程标准课程标准和和教学目标教学目标建议课时：建议课时：1 课时教学环节教学环节教学过程教学过程设计意图设计意图教学活动设计教学活动设计情境导入情境导入导入：在一次电视节目上,谷歌总裁施密特提出问题:“如何才能更有效地对一百万个 32 位长整数进行排序?”同在现场的奥巴马总统立刻响应道:“肯定不能用冒泡排序法。”施密特评价说:天哪!他是从谁那里听说这个的。”通过有趣的故事，涉及术语“冒泡排序”，激起学生对排序的兴趣，对排序概念形成初步认识，同 时 对“冒泡排序”是什么产生强烈好奇心。学习任务一学习任务一学习任务一：什么是排序问题：我们在日常生活中会经常经历排序的场景，比如体育课上按身高排列等等熟悉的生活体验。这种熟悉的经验，在计算机中的排序又有哪些？引导学生思考并回答问题。可以让学生列举一些计算中经常使用到排序实例。如：文件夹中图片文件可分别按名称、大小、类型、修改日期等方式进行排序；电子邮件列表一般按照日期排序，最新的邮件被放置在最顶端；购物网站上搜索到的某类商品可按价格、销量、信用等方式进行排序。设问：计算机要对数据排序，先要考虑数据的组织形式。如果有一组数（23，20，13，18，14，11）分别存储以数组、链表的形式，排序有什么不同呢？设问：为了分析问题方便，我们以后假设数据以数组形式存储，然后讨论它的排序算法。排序的基本要求是什么？对上面的数组 d 进行按升序排序后，数组 d 中数据的存储情况变为如图所示。排序后的数据存储情况教师总结：排序（sorting）就是整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。在排序的过程中，序列里的数据元素的值保持不变，但其排列顺序可能改变。设计意图：尽管学生对排序并不陌生，但如何严谨地定义排序，并与数据在计算机中存储形式结合起来思考问题，还需要进一步清晰化。通过三个问题，串起排序的作用与意义、数据排序的组织形式、排序的概念与要求等等。学习任务二学习任务二前面奥巴马总统提到的“冒泡排序”，它是如何进行的呢？1.冒泡排序的一般过程动画演示。使用现成的数字化学习工具，直观展示“冒泡排序”的动画。冒泡排序.gif考虑一般情形，讲解冒泡排序第一遍的加工过程：冒泡排序算法对数组 d 的第一遍加工过程设问：经过第一遍加工，是否能够确保数据中的最大元素下沉到最下面？2.设计算法可以安排小活动，比如打印 6 个数字卡片，让 6 位学生手持卡片，完成冒泡排序的整个过程。在理解冒泡排序算法思想的基础上，引导学生探究程序的实现过程，进一步理解数据排序的思想和方法。3.冒泡排序的自然语言描述老师展示动画后，让学生自主探究、相互启发，总结其规律，概括其算法，体现课堂的生成性。设问 1：若要排序的数有 n 个，最少需要进行几遍？设问 2：对于第一遍加工的基本过程，能用自然语言描述吗？欣赏动画，了解冒泡排序的一般过程。首要是寻找和发现冒泡排序的一般规律。能够由第一遍加工概括出一般规律，通过类推，实现整个排序过程。通过第一遍加工的细致分析，学生得到具体到抽象的基本思维训练。设计意图：重点在于第一遍加工处理，这个过程清楚了，那么对于后面的每遍加工，遵循同样的规则，以此类推，即可实现数据的完整排序。设计意图：对于 n 个元素，第一遍加工将最大元素下沉到第 n 个位置对于剩下的n-1 元素，反复 使 用 该 规则，直到最后余 下 两 个 元素 进 行 比 较和交换冒 泡 排 序 完成设问 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.冒泡排序的时间复杂度分析及其特点为 下 节 引入 程 序 实现 做 好 铺垫。作业布置作业布置基础作业（面向所有学生）：举例说明冒泡排序每一遍处理的结果。课 后 作 业是 课 堂 学习的延伸，是 巩 固 和升 华 知 识点 的 有 效途径。教学设计思路教学设计思路本节建议重点关注计算思维的培养与提高。数据排序是计算机中常见操作，排序的算法内容极为丰富，应用极为广泛。它是很多算法的重要组成部分，在许多算法里需要对数据先进行排序。比如二分查找等。建议从排序应用的典型场景从发，启发学生培养对排序的重要性和作用的意识，在分析数据存储形式的基础上，以数组中数据排序为例，体会排序的具体思想与方法。再以冒泡排序为例，引导学生深入体会排序的基本方法。针对针对核心素养核心素养信息意识、信息社会责任：本节课在导入时选择了一则小故事，调动学生深入探究的兴趣；然后通过学生思考并举例，列举、回顾学生生活与身边的排序相关的真实场景，引入计算机编程中常用的排序用途与定义，进而增强学生对排序具有广泛应用场景的认识。计算思维：首先，数据采用数组或者链表形式存储与排序算法的操作密切相关，这一点与本章第一节有紧密联系。其次，排序的基本定义。“排序”的定义包括两个重要方面：数据的物理存储结构、排序后数据之培养的培养的设计考虑设计考虑间的逻辑关系（有序）进行了梳理，重点在于培养学生对专业知识的科学严谨态度。而后介绍的冒泡排序，主要通过动画“模拟”的形式，直观呈现冒泡排序的一般过程。最后通过让学生参与其中，发现并描述整个排序过程，让学生总结其规律，概括其算法，体现课堂的生成性。这个模拟抽象概括的过程，能够较好地训练学生思维。数字化学习与创新：教师使用“冒泡排序”、“选择排序”动画，直观展示“冒泡排序”、“选择排序”的完整过程，学生可以使用思维导图软件描述算法的基本过程，从中整理思路、总结规律。排序算法的程序实现教学设计排序算法的程序实现教学设计排序算法的程序实现排序算法的程序实现教材内容：教材内容：5.3 排序算法的程序实现适应的课程标准：适应的课程标准：1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。教学目标：教学目标：掌握常用的冒泡排序的基本程序结构。能够编程实现冒泡排序。指向的核心素养：指向的核心素养：信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。数字化学习与创新：学生较为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。学习环境：学习环境：有教学控制软件的多媒体机房，python 编程环境。课程标准课程标准和和教学目标教学目标建议课时：建议课时：1 课时教学环节教学环节教学过程教学过程设计意图设计意图教学活动设计教学活动设计情境导入情境导入回顾旧知：请同学们写出冒泡排序第一趟的基本过程。设计意图：巩固旧知，联系新知。学习任务一学习任务一学习任务一：冒泡排序的基本过程与规则问题：冒泡排序应该对任意排列的 n 个数据都能实现最终的排序，这里面是否有规则，规则在哪里？引导学生思考并回答问题。引导学生总结：排序的最少遍数为 n-1，每遍进行的基本过程。第一遍，对 n 个元素冒泡，加工完毕，最大值 23“下沉”至数组最后第一个元素的位置；第二遍，对 n-1 个元素冒泡，加工完毕，最大值 20“下沉”至数组最后第二个元素的位置；第 n-1 遍，对 2 个元素冒泡，加工完毕，最大值 13“下沉”至数组最后第 n-1 个元素的位置；排序完成。以升序、“最大元素下沉”为例，提炼出一般规则：设问：再仔细观察某一遍里面的加工步骤，这种方法是否通用？教师引导学生总结：排序过程中，按下面的方式使用变量 i 和j:i：记录正进行的处理遍数，第 1 遍处理时值为 1，第 2 遍处理时值为 2，依次类推。j：记录当前数组元素的下标。每遍处理过程中，j 值总是从第一个数组元素的下标值 0 开始，按每次加 1 的方式，直至 j=n-i-1为止。每当 j 取定一个值后，当前数组元素 dj将与它的后一个元素 dj+1进行比较，若 dj dj+1，则互换这两个数组元素中的数据。设计意图：按照由粗到细、逐步求精的策略，推动学生加深对冒泡排序的深刻认识。学习任务二：学习任务二：冒泡排序的程序实现学生自主编写程序，教师及时跟踪、辅导、点评、总结1.先研究冒泡排序的第一遍的程序实现仍以这些数据为例，回顾冒泡排序第一遍的加工过程：冒泡排序算法对数组 d 的第一遍加工过程设问：经过第一遍加工，是否能够确保数据中的最大元素下沉到最下面？如何使用程序实现？for j in range(0,length-1):if LjLj+1:temp=Lj Lj=Lj+1 Lj+1=tempj 代表数组元素的下标，试问 j 从 0 开始，是否可以达到length-1？为什么？设计意图：从第一遍加工的实现中可以发现规律，进而引导学设计意图：从第一遍加工的实现中可以发现规律，进而引导学生概括出全部算法过程。生概括出全部算法过程。2.设计算法设问：上一步中，我们编写了第一遍加工的程序代码，如何修改一下，完成第 i 遍（i=1,2,3,）的加工过程？for j in range(0,length-i):if LjLj+1:temp=Lj Lj=Lj+1 Lj+1=temp设计意图：重点在于第一遍加工处理，这个过程清楚了，那么对于后面的每遍加工，遵循同样的规则，以此类推，即可实现数据的完整排序。此处在于引导学生意识到对第 i 遍加工来说，只需要将一个参数略微修改一下即可。3.学生动手编写冒泡排序的程序def bubble_sort(L):length=len(L)#序列长度为 length，需要执行 length-1 遍加工 for i in range(1,length):for j in range(0,length-i):if LjLj+1:temp=Lj Lj=Lj+1 Lj+1=temp设计意图：由第一遍加工的代码，概括出第 i 遍加工代码，是一种抽象思维的过程，最后将整个过程，进一步概括出一个外层循环和内层循环的程序结构，这是一个难点。可以多花些时间，鼓励学生多思考、多动手、多验证。设计意图：重点在于第一遍加工处理，这个过程清楚了，那么对于后面的每遍加工，遵循同样的规则，以此类推，即可实现数据的完整排序。此处在于引导学生意识到对第 i 遍加工来说，只需要将一个参数略微修改一下即可。设计意图：由第一遍加工的代码，概括出第 i 遍加工代码，是一种抽象思维的过程，最后将整个过程，进一步概括出一个外层循环和内层循环的程序结构，这是一个难点。可以多花些时间，鼓励学生多思考、多动手、多验证。拓展学习拓展学习冒泡排序算法的每一遍加工中，最小的元素“上浮”和最大的元素“下沉”这两种方式在程序实现时有何区别？建议在上节引入“选择排序”的基本思想与方法基础上。鼓励学生探索“选择排序”的程序实现。设计意图：根据学生的不同层次水平设置相应的教学任务课堂小结课堂小结知识梳理：1.冒泡排序的基本过程和结构；2.冒泡排序的程序实现。对于 n 个元素，第一遍加工将最大元素下沉到第 n 个位置对于剩下的 n-1 元素，反复使用该规则，直到最后余下两个元素进行比较和交换冒泡排序完成作业布置作业布置课后练习选择排序算法是在参加待排序序列的所有元素中找出最小（或最大）数据的元素，使它与第一个元素中的数据相互交换位置。然后再在余下的元素中找出最小（或最大）数据的元素，与第二个元素中的数据相互交换位置。以此类推，直到所有元素成为一个有序的序列。请根据该排序算法的思想，编程实现对数据序列23,20,13,18,14,11,98,4 的升序排列。课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。教学设计思路教学设计思路本课内容为排序算法的程序实现。建议分配 1 课时完成。首先，引导学生回顾旧知，与前面所学的冒泡排序基本思想与方法建立联系，学生可以较熟悉地对若干个数据进行冒泡排序。其次，引导学生能够从抽象的角度概括出冒泡排序的基本规则，并能以合适的数字化学习工具呈现出其每遍加工的基本过程。再次，在学生有了一定认知基础上，可以引入自然语言、流程图，帮助学生理解冒泡排序的基本程序结构，从而实现对程序实现这个难点的突破。本节主要内容为排序算法的核心模块。针对针对核心素养培养的核心素养培养的设计考虑设计考虑本节侧重于计算思维的训练。程序语言是表达算法思想的工具，为了实现冒泡排序，在数据组织形式上选择较为简单的整数，并从中概括出冒泡排序的基本过程和算法步骤。这是一个逐步求精的过程。为了照顾普通学生的需要，可以从分析冒泡排序的第一遍加工入手，然后再就其程序实现进行展开，这是一个由抽象到具体的过程；然后再从第一遍的实现，推广到第 i 遍加工，这是一个思维泛化的过程；再由此出发，抽象出冒泡排序的整体程序结构，并通过简洁的代码实现，提炼出了冒泡排序的基本算法。这个基本过程，是一种思维螺旋式上升的提升过程，较好地实现了教学意图。数据排序的应用教学设计数据排序的应用教学设计数据排序的应用数据排序的应用教材内容：教材内容：5.3 数据排序的应用适应的课程标准：适应的课程标准：1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。教学目标：教学目标：能针对具体的问题情境，选择合适的数据组织形式。能够完整地进行抽象与建模、设计算法与数据结构、程序实现，解决排序算法的应用问题。指向的核心素养：指向的核心素养：信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。数字化学习与创新：要使学生为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。学习环境：学习环境：有教学控制软件的多媒体机房，python 编程环境。课程标准课程标准和和教学目标教学目标建议课时：建议课时：1 课时教学环节教学环节教学过程教学过程设计意图设计意图情境导入情境导入导入 1：奥运排行榜部分数据（Excel 数据）编号编号国家/地区国家/地区人口数量（万）人口数量（万）金牌金牌银牌银牌铜牌铜牌总数总数8中国13640751212810020印度130420102353美国3226236383611021印度尼西亚26110113513巴西205293481523尼日利亚18231013452俄罗斯14253232128726日本12703961025请学生操作 Excel 表，并按关键字“金牌”进行排序。并调换关键字排序。分析按不同关键字排序，对排序的结果有何影响？记录的位置变化？同一条记录的变设计意图：通过导入生活中的数据分析案例，体会排序过程中若要发生交换，则要将待排序的两条记录整体进行交换。化？新课讲解新课讲解学习任务一：抽象与建模问题：从表中的数据可以看出，每个国家的信息是一条记录，包括编号、国家/地区、人口数量、各奖牌数等数据项。根据刚才的实践体验，对记录按关键字排序，交换应当如何进行？教师总结：排序过程中若要发生交换，则要将待排序的两条记录整体进行交换。学习任务二：设计算法与数据结构对于每个国家，需要记录其一条完整的记录信息，排序之前要将所有国家的信息存储起来，可以选取数组结构来实现。有两种方案：一是采用 7 个一维数组按列存储，即每个数组分别存储每个国家的编号、国家/地区、人口数量、各奖牌数等，如定义 b 数组存储表中 8 个国家的金牌数量，其对应的值为51,1,36,1,3,0,23,9；二是采用 1 个一维数组（实际是二维数组）按行存储，每个数组元素对应某个国家的一条记录信息，如8,中国,136407,51,21,28,100对应中国的相关信息。采用不同的存储方式，排序时数据的交换方式也何不同？学生可以展开小组讨论。老师总结：（1）若采用采用 7 个一维数组按列存储，排序过程中，两条记录的对应数据项都要相应交换，即要考虑 7 个一维数组的操作。（2）若采用 1 个一维数组按行存储，排序中的数据交换可对整条记录进行交换操作。设问：哪种存储形式处理起来更方便快捷？学习任务三：程序实现老师可以提供数据样例，并以 csv 格式文件分发给学生。读取数据文件时，选择一个一维数组，然后以金牌数为关键字进行降序排序。根据学习情况，读写 csv文件的程序代码可以由老师提供给学生。示例程序：设计意图：引导学生思考复杂数据排序应当注意的事项。设计意图：引导学生总结不同数据存储形式，带来的数据交换形式不同。设计意图：可以在配合讲解程序的情况下，鼓励学生自己动手编写程序。老师可以巡视过程中发现问题，帮助解决问题。import csv#数据读入csvFile=open(jp.csv,r)#打开相应数据文件reader=csv.reader(csvFile)#建立一个读入数据的对象a=for item in reader:a.append(item)csvFile.close()#排序for i in range(1,len(a)-1):#排序不包含第一行数据 for j in range(1,len(a)-i):if int(aj3)int(aj+13):temp=aj aj=aj+1 aj+1=temp#数据写入csvFile2=open(jp2.csv,w,newline=)writer=csv.writer(csvFile2,dialect=excel)m=len(a)for i in range(m):writer.writerow(ai)csvFile2.close()拓展学习拓展学习老师提供大数据量的数据文件给学生，让学生体会冒泡排序的效率，并与 python提供的库函数 sort()的算法效率进行对比。通过对排序稳定性的讲解，让学生体会冒泡排序的稳定性如何。一般情况下，数据规模较小，各种排序方法的时间耗费差异较小，选择面较大；当数据规模较大时，冒泡排序、选择排序的时间复杂度为 O(n2)，一般不会选用，常用的有快速排序、归并排序、堆排序、希尔排序等，时间复杂度为 O(n log2 n)，python中使用的排序方法为 TimSort，它实质上是对归并排序的优化，目前认为是最优秀的排序方法。稳定性是指排序前后，相同的数据项前后关系会不会带来变化，冒泡排序是稳定的，快速排序是不稳定的；数据结构也对排序有很大影响，编程的复杂度不同，空间复杂度不同。一般情况下，降低了时间复杂度，就会带来较高的空间复杂度；降低了空间复杂度，会带来较高的时间复杂度。对较特殊的数据比如在一定范围内的整数，使用桶排序，时间复杂度达到 O(n),但空间复杂度会提高，需要较多的辅助空间。设计意图：排序问题涉及到算法效率的分析、稳定性分析、数据结构等各个方面，都可以有所涉及。课堂小结课堂小结知识梳理：1.记录的关键字排序注意事项；2.不同数据组织形式对算法的实现影响；3.抽象与建模、设计算法与数据结构、程序实现的完整经过。设计意图：针对不同学习程度设计对应的任务，以满足不同学生的需求。作业布置作业布置完成课本实践体验“K-近邻分类算法初步”。课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。教学设计思路教学设计思路本条目建议重点关注计算思维的培养与提高。建议从学生熟悉的生活情境出发，由学生已经获得的编程经验自然延伸，针对具体问题展开。可从抽象与建模、设计算法与数据结构、程序实现三个方面进行。即通过合适途径让学生明晰排序算法应用时应当注意的问题，特别是面对较复杂结构的数据时，如果数据以记录的形式呈现，各条记录的排序如何进行，涉及排序的具体操作时，有哪些注意事项。据此再讨论算法的设计，对数据的组织形式展开讨论，并详细剖析在不同组织形式下的排序方法有什么差异。厘清问题是程序实现的关键所在，选择合适的数据结构之后，再针对具体实现讲解要点，鼓励学生自主完成。同时可以就不同的数据组织形式对程序实现的难度进行分析，帮助学生认识到数据结构对排序算法的重要影响。针对针对核心素养培养的核心素养培养的设计考虑设计考虑信息意识、信息社会责任：本节课在导入时选择了一个案例，导入“奥运排行榜部分数据（Excel 数据）”，由于 Excel 表格进行排序操作时，直观形象，教师可以引导学生思考数据的组织形式、排序的关键字、记录在排序前后各行数据内部数据项之间的相对关系是否变化，从而形成对记录排序相关问题初步的意识。计算思维：本节中围绕较为复杂形式的数据如何进行排序展开，这是一个由抽象与建模、设计算法与数据结构、程序实现组成的完整经过。数字化学习与创新：本节的数据可以从真实环境中产生，或者由老师提前安排好并提供数据文件，或者由学生课前自主搜集相关数据。鼓励学生利用多途径方式收集数据，并采用不同的数据存储方式进行数据排序算法的探索。