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