算法实例之排序与查找.docx

算法实例之排序与查找
执教者：栾海栋
一、教学目标
知识、技能目标
使学生掌握冒泡排序、选择排序、顺序查找、对分查找的步骤流程。
过程与方法
演示法、问答与课堂练习。使学生通过观察与模仿，理解排序与查找算法的每一个过程。
情感态度与价值观
从实例出发，使学生了解计算机算法在解决实际问题中的运用，培养学生对算法的学习兴趣。
二、教学重点与难点分析
教学重点
排序算法、查找算法。
教学难点
冒泡排序、对分查找。
三、教学过程
教学环节
教学活动
设计意图
情景导入
课代表“陈明宇”同学在知道了自己的分数前提下，还想了解他的信息成绩在班级中的名次。于是，在老师的操作下，计算机完成了“排序”操作，得到了下面这张表。
由学生关心的成绩导入，引出“排序”这个概念。
计算机是如何帮助老师完成“排名次”的这个任务的呢？
学习新知
排序法：对批量的数据按照一定的顺序进行排列的一种操作方法。
升序：从小到大排列
降序：从大到小排列
冒泡排序：逐遍加工，每一遍排好一个数据，最后一遍加工后完成整个排序。根据题意按照一定的方向，依次比较相邻的2个元素（数据），符合题意的不做任何变动，不符合题意的交换两个元素（数据）的位置。
例一、有4个数据：18、15、2、9，按照升序排列，采用冒泡排序算法自右向左进行比较和交换，请完成排序过程。（校本P62-1）
讲授第一种排序：冒泡排序。
例一完全由老师讲解，教授学生冒泡排序的每一个步骤。
原始数据
18
15
2
9
第一遍
2
18
15
9
第二遍
第三遍
例二、已知数组A中数据存储情况如图所示，拟对数组中的数据采用冒泡排序法进行降序排序，自下而上进行比较和交换，请完成表格。（校本P62-4改）
例二巩固新知，由学生在老师的带领下回答出每一个步骤。
冒泡排序小结
例一，四个数据，比较了3遍，第一遍比较了3次，第二遍比较了2次，第三遍比较了一次。
例二，五个数据，比较了4遍，第一遍比较了4次，第二遍比较了3次，最后一遍比较了一次。
若有N个数据，则需要比较 N-1 ；第一遍需要比较 N-1 次；第二遍需要比较 -2 次；最后一遍需要比较 1 次。
由老师给出冒泡排序算法中规律性的数据。
课堂练习
1、校本P63-5
通过练习，加深对冒泡排序的理解。并由老师通过分析，强调“比较次数”与“交换次数”的区别。
2、校本P63-6
选择排序：通过遍历，记录下最值的位置，最后再将最值所在位置的数据与最值进行交换，因此每一遍加工只需交换一次位置。大大减少了算法的复杂度。
例三、用选择排序法对下列数据按照升序进行排列。
讲授第二种排序：选择排序
例三完全由老师讲解，让学生了解选择排序的每一个步骤。
课堂练习
校本P62-2
有4个数据：18，15，2，9，按照从小到大的顺序排列，过程如下：
原始数据
18
15
2
9
第一遍
2
15
18
9
第二遍
第三遍
巩固新知，通过练习 加深对选择排序的理解。
顺序查