高中信息技术浙教版 (2019)选修1 数据与数据结构第五章 数据结构与算法5.3 数据排序教案

课程标准

和

教学目标

数据排序的应用

教材内容：5.3数据排序的应用

适应的课程标准：

1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。

教学目标：

●能针对具体的问题情境，选择合适的数据组织形式。

●能够完整地进行抽象与建模、设计算法与数据结构、程序实现，解决排序算法的应用问题。

指向的核心素养：

●信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。

●计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。

●数字化学习与创新：要使学生为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。

●信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。

学习环境：有教学控制软件的多媒体机房，python编程环境。

建议课时：1课时

教学环节

教学过程

设计意图

情境导入

导入1：奥运排行榜部分数据（Excel数据）

请学生操作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文件的程序代码可以由老师提供给学生。

示例程序：

设计意图：引导学生思考复杂数据排序应当注意的事项。

设计意图：引导学生总结不同数据存储形式，带来的数据交换形式不同。

设计意图：可以在配合讲解程序的情况下，鼓励学生自己动手编写程序。老师可以巡视过程中发现问题，帮助解决问题。

拓展学习

老师提供大数据量的数据文件给学生，让学生体会冒泡排序的效率，并与python提供的库函数sort()的算法效率进行对比。

通过对排序稳定性的讲解，让学生体会冒泡排序的稳定性如何。

一般情况下，数据规模较小，各种排序方法的时间耗费差异较小，选择面较大；当数据规模较大时，冒泡排序、选择排序的时间复杂度为O (n2)，一般不会选用，常用的有快速排序、归并排序、堆排序、希尔排序等，时间复杂度为O (n log2 n)，python中使用的排序方法为TimSort，它实质上是对归并排序的优化，目前认为是最优秀的排序方法。稳定性是指排序前后，相同的数据项前后关系会不会带来变化，冒泡排序是稳定的，快速排序是不稳定的；数据结构也对排序有很大影响，编程的复杂度不同，空间复杂度不同。一般情况下，降低了时间复杂度，就会带来较高的空间复杂度；降低了空间复杂度，会带来较高的时间复杂度。对较特殊的数据比如在一定范围内的整数，使用桶排序，时间复杂度达到O (n),但空间复杂度会提高，需要较多的辅助空间。

设计意图：排序问题涉及到算法效率的分析、稳定性分析、数据结构等各个方面，都可以有所涉及。

课堂小结

知识梳理：

1. 记录的关键字排序注意事项；

2. 不同数据组织形式对算法的实现影响；

3. 抽象与建模、设计算法与数据结构、程序实现的完整经过。

设计意图：针对不同学习程度设计对应的任务，以满足不同学生的需求。

作业布置

完成课本实践体验“K- 近邻分类算法初步”。

课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。

教学设计思路

本条目建议重点关注计算思维的培养与提高。建议从学生熟悉的生活情境出发，由学生已经获得的编程经验自然延伸，针对具体问题展开。可从抽象与建模、设计算法与数据结构、程序实现三个方面进行。即通过合适途径让学生明晰排序算法应用时应当注意的问题，特别是面对较复杂结构的数据时，如果数据以记录的形式呈现，各条记录的排序如何进行，涉及排序的具体操作时，有哪些注意事项。据此再讨论算法的设计，对数据的组织形式展开讨论，并详细剖析在不同组织形式下的排序方法有什么差异。厘清问题是程序实现的关键所在，选择合适的数据结构之后，再针对具体实现讲解要点，鼓励学生自主完成。同时可以就不同的数据组织形式对程序实现的难度进行分析，帮助学生认识到数据结构对排序算法的重要影响。

针对

核心素养培养的

设计考虑

信息意识、信息社会责任：本节课在导入时选择了一个案例，导入“奥运排行榜部分数据（Excel数据）”，由于Excel表格进行排序操作时，直观形象，教师可以引导学生思考数据的组织形式、排序的关键字、记录在排序前后各行数据内部数据项之间的相对关系是否变化，从而形成对记录排序相关问题初步的意识。

计算思维：本节中围绕较为复杂形式的数据如何进行排序展开，这是一个由抽象与建模、设计算法与数据结构、程序实现组成的完整经过。

数字化学习与创新：本节的数据可以从真实环境中产生，或者由老师提前安排好并提供数据文件，或者由学生课前自主搜集相关数据。鼓励学生利用多途径方式收集数据，并采用不同的数据存储方式进行数据排序算法的探索。