对数据进行排序 全国优质课一等奖

对数据进行排序3.4.1冒泡法排序算法队列排序

成绩排序

工资排序

……

生活中大家常见的排序有哪些？看看下面这个表格，要想了解火箭队这五场客场比赛得分的排序情况，我们该怎么做？得分得分

排序问题在我们生活中随处要见，许多软件也都提供了排序操作，如Excel强大的排序功能就是它的重要特色。因为已经排好序的数据跟未经排序杂乱无章数据相比，处理起来要容易得多。排序的使用是非常频繁的，在实践中，人们设计出了许多好的算法来实现数据的排序，今天我们来学习其中人们较常用的一种：冒泡排序法。排序的概念所谓排序，就是指将一个无序序列排列成一个有序序列的过程。什么是排序算法？无序

数据有序

数据排序观看并思考：视频中队列排序规律。A(i-1)A(i+1)数组中第i个数前一个数后一个数数据

位置

改变交换

数据

位置比较

数据

大小A(i)复习：数组的概念视频中数据排序体现什么样的规律。数据

位置

改变交换

数据

位置比较

数据

大小排序的途径：视频中数据排序前后有什么不同？排序前的数据排序后的数据数组元素及下标在排序前后都没有发生改变，只是在排序后数组元素的值发生了变化。冒泡法排序算法分析

冒泡排序法是简单的排序方法之一，它和气泡从水中往上冒的情况有些类似：对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素放在后面，比较完毕后，一个最大的数沉底成为数组中的最后一个元素，一些较小的数如同气泡一样上浮一个位置，依次类推，数列由后往前逐渐成型。冒泡法排序算法学法指导作业展示团队讨论自主探究开始向A（n-1）中读入n个元素i=0，j=n-1A(j)<A(j-1)交换A(j)和A(j-1)的值j=j-1j=iNi=i+1NYYi>n-2输出排序结果结束NY

冒泡法排序流程图

图3-13若要交换A(j)和A(j-1)的值，利用程序代码是如何实现的？冒泡法排序演示：

冒泡法排序思想：顺序扫描数组元素，将相邻两个数进行比较，将大数调到后面，小数调到前面。如果有n个数，则要进行轮排序。在第i轮排序中，要进行次两两比较。

冒泡法排序的特点是：n-1n-i排序(冒泡法)的算法设计：将n个存放在数组a中的数据按从小到大排序。“趟”的设计“次”的设计

课堂练习基础任务1：写出一个数组N趟排序后的排列结果。基础任务2：认真阅读找到图3-14中冒泡法排序示意图的排序特点并将实践练习中的伪代码填写完整。基础任务3：把课堂作业文件夹中冒泡法排序VB源程序的升序方式的代码补充完整，运行程序验证结果。拓展任务：先完成升序排序代码者可对程序进一步完善，并考虑如果将数组a从大到小降序排列，应该如何设计程序？

课堂小结冒泡法排序是通过顺序扫描数组元素，将相邻两个数进行比较，将小数调到前面，大数调到后面。如果有n个数，则要进行n—1轮排序。在第i轮排序中，要进行n—i次两两比较。可以从前往后排序，也可以从后往前排序。请你继续思考的问题：1、有没有效率更高的排序方法或者能否对冒泡排序法加以改进？

（建议：希望你能去学习更多更好的排序方法，比如选择排序法、插入排序法、分组排序法、快速排序法、堆排序法等等。）2、今天我们一起设计的排序算法要真正在计算机上实现，我们还需做哪些事？（提示：要在计算机上真正实现算法，还得将算法用计算机语言表示出来。）3.4.2插入排序算法时隔13年，中国再次作为东道主举办APEC会议。APEC会议其中一个重大的成果就是21个国家签约成立法定资本为1000亿美元的亚洲基础设施投资银行，（简称亚投行），总部设北京。排序无序有序13576248插入排序：将一个数据序列看作两部分，前一部分是有序的，后一部分是无序的；排序时，将无序序列中的一个或几个元素逐个“插入”到有序序列中，使得有序部分的元素个数不断增加，无序部分的个数相应减少，最后所有的元素成为有序序列。有序序列无序序列提示：请带着以下两个问题来观看视频：程序“猿”进军文艺界。（1）他们做了什么？（2）为什么这样做？了解插入排序的基本思想。基础任务一观看视频后，根据视频中数据移动的规律，从第四次循环开始，在学案中用【】标出每次排序时的有序序列并通过划箭头，模拟数据位置的移动。

游戏规则：

（1）请一组同学上台参与，上台后抽取一个数据牌，背对观众，模拟视频中数据元素的排序方式，实现数据元素的升序排序。

（2）轮到哪位同学进入排序过程，需先举牌示意观众；

（3）进行比较的两个数据，需面对面示意。

模拟演示“插入排序的基本思想”

了解插入排序的基本思想。基础任务一自学探究小组讨论展示成果完成任务一你需要观看微课：程序“猿”进军文艺界。我们需要通力合作完成两个任务提高任务二完成任务二你需要观看微课：计算机数据如何交换、插入排序算法演示。了解插入排序规则。拓展任务详见任务卡片三。循环次数A（0）A（1）A（2）A（3）A（4）A（5）第1次

【4】1532

第2次

1【14】532

第3次

【145】32

第4次

13452

第5次

12345用【】标出每次排序时的有序序列，通过划线，模拟数组数据位置的移动，用标出每次排序哨兵的值。

一组数字序列：49,38,65,97,13,25,65,51。第二个65是否会和第一个65交换位置？排好序需要经过

次比较？

在下图的表格中,用下划线标识第二个65，在比较次数一列，填写比较次数。拓展练习比较次数A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)49386597132565513849659713256551384965971325655138496597132565511338496597256551132538496597655113253849656597511325384951656597合计在下图的表格中,用下划线标识第二个65，在比较次数一列，填写比较次数，最后合计比较次数。评价内容☆☆☆☆☆

☆☆☆☆

☆☆☆☆☆遇到哪些困难？如何改进？课堂合作互助

课堂讨论发言

活动参与

基础任务一:了解插入排序的基本思想。

提高任务二：了解插入排序的规则。

学生学习活动小组评价表（小组内自评）根据各位小组成员的表现，请组长对本节课小组的表现评分