5.3.3 排序算法的应用 教学设计-数据 与数据结构-新浙教版（2019）《高中信息技术》选择性必修第一册.doc

1、数据排序的应用教学设计课程标准和教学目标数据排序的应用教材内容：5.3数据排序的应用适应的课程标准： 1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。教学目标： 能针对具体的问题情境，选择合适的数据组织形式。能够完整地进行抽象与建模、设计算法与数据结构、程序实现，解决排序算法的应用问题。指向的核心素养： 信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作

2、，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。数字化学习与创新：要使学生为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。学习环境：有教学控制软件的多媒体机房，python编程环境。建议课时：1课时教学环节教学过程设计意图情境导入导入1：奥运排行榜部分数据（Excel数据）编号国家/地区人口数量（万）金牌银牌

3、铜牌总数8中国13640751212810020印度130420102353美国3226236383611021印度尼西亚26110113513巴西205293481523尼日利亚18231013452俄罗斯14253232128726日本12703961025请学生操作Excel表，并按关键字“金牌”进行排序。并调换关键字排序。分析按不同关键字排序，对排序的结果有何影响？记录的位置变化？同一条记录的变化？设计意图：通过导入生活中的数据分析案例，体会排序过程中若要发生交换，则要将待排序的两条记录整体进行交换。新课讲解学习任务一：抽象与建模问题：从表中的数据可以看出，每个国家的信息是一条记录，包

4、括编号、国家/地区、人口数量、各奖牌数等数据项。根据刚才的实践体验，对记录按关键字排序，交换应当如何进行？教师总结：排序过程中若要发生交换，则要将待排序的两条记录整体进行交换。学习任务二：设计算法与数据结构对于每个国家，需要记录其一条完整的记录信息，排序之前要将所有国家的信息存储起来，可以选取数组结构来实现。有两种方案：一是采用7个一维数组按列存储，即每个数组分别存储每个国家的编号、国家/地区、人口数量、各奖牌数等，如定义b数组存储表中8个国家的金牌数量，其对应的值为51,1,36,1,3,0,23,9；二是采用1个一维数组（实际是二维数组）按行存储，每个数组元素对应某个国家的一条记录信息，如

5、8,中国,136407,51,21,28,100对应中国的相关信息。采用不同的存储方式，排序时数据的交换方式也何不同？学生可以展开小组讨论。老师总结：（1） 若采用采用7个一维数组按列存储，排序过程中，两条记录的对应数据项都要相应交换，即要考虑7个一维数组的操作。（2） 若采用1个一维数组按行存储，排序中的数据交换可对整条记录进行交换操作。设问：哪种存储形式处理起来更方便快捷？学习任务三：程序实现老师可以提供数据样例，并以csv格式文件分发给学生。读取数据文件时，选择一个一维数组，然后以金牌数为关键字进行降序排序。根据学习情况，读写csv文件的程序代码可以由老师提供给学生。示例程序：impor

6、t 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=)

7、writer = csv.writer(csvFile2, dialect=excel)m = len(a)for i in range(m): writer.writerow(ai)csvFile2.close()设计意图：引导学生思考复杂数据排序应当注意的事项。设计意图：引导学生总结不同数据存储形式，带来的数据交换形式不同。设计意图：可以在配合讲解程序的情况下，鼓励学生自己动手编写程序。老师可以巡视过程中发现问题，帮助解决问题。拓展学习老师提供大数据量的数据文件给学生，让学生体会冒泡排序的效率，并与python提供的库函数sort()的算法效率进行对比。通过对排序稳定性的讲解，让学生体会冒

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

9、间复杂度。对较特殊的数据比如在一定范围内的整数，使用桶排序，时间复杂度达到O (n),但空间复杂度会提高，需要较多的辅助空间。设计意图：排序问题涉及到算法效率的分析、稳定性分析、数据结构等各个方面，都可以有所涉及。课堂小结知识梳理：1. 记录的关键字排序注意事项；2. 不同数据组织形式对算法的实现影响； 3. 抽象与建模、设计算法与数据结构、程序实现的完整经过。设计意图：针对不同学习程度设计对应的任务，以满足不同学生的需求。作业布置完成课本实践体验“K- 近邻分类算法初步”。课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。教学设计思路本条目建议重点关注计算思维的培养与提高。建议从学生熟

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

11、养培养的设计考虑信息意识、信息社会责任：本节课在导入时选择了一个案例，导入“奥运排行榜部分数据（Excel数据）”，由于Excel表格进行排序操作时，直观形象，教师可以引导学生思考数据的组织形式、排序的关键字、记录在排序前后各行数据内部数据项之间的相对关系是否变化，从而形成对记录排序相关问题初步的意识。计算思维：本节中围绕较为复杂形式的数据如何进行排序展开，这是一个由抽象与建模、设计算法与数据结构、程序实现组成的完整经过。数字化学习与创新：本节的数据可以从真实环境中产生，或者由老师提前安排好并提供数据文件，或者由学生课前自主搜集相关数据。鼓励学生利用多途径方式收集数据，并采用不同的数据存储方式进行数据排序算法的探索。