《选择排序算法分析及程序实现》教学案例:十大排序算法

　　本节教学内容选自浙江教育出版社出版的《算法与程序设计》。出于理论与实践相结合的考虑，将教材第二章第三节的“排序”和第五章第三节的“排序算法的程序实现”教学内容合并起来教学，以加深学生对算法和程序设计的关系的体会。排序算法是程序设计中的重要算法，对它的学习既是对已经学过的三种程序设计结构的综合运用，又能为后续对分查找的学习作好铺垫。
　　一、教学目标
　　知识与技能：理解选择排序算法；能解释冒泡排序、选择排序的优势；能由此及彼，归纳排序中的数字规律，探索更有效率的排序算法；能在VB中规范地编写程序。
　　过程与方法：在回顾冒泡排序算法的过程中自然引出选择排序，并以任务分解、逐级递进的方式化解难点。以讲授法和探究法相结合的方式，让学生在自主探索中思考发现、归纳总结，逐步将排序方法用程序语言表达出来，最终实现程序，解决问题。
　　情感、态度与价值观：培养学生对程序设计的兴趣，激发学生探索新知的欲望和热情，让学生体会将自己的逻辑思维通过程序设计的方式实现的喜悦感和成就感。
　　二、学情分析
　　选择排序算法的学习是在学生学习了“冒泡排序”的基础上进行的，而且学生对VB的基本语句、三种程序结构、数组变量、随机数的生成，以及事件、过程等能较好地理解、应用，因此，程序界面的设计、无序的随机数的生成、通用变量（n、数组变量）的定义等预备工作事先由教师准备。
　　三、教学重点、难点
　　教学重点：理解选择排序算法，以及算法在VB中的实现。
　　教学难点：如何找到一组数中的最小数（或最大数），用来记录最小值（或最大值）的变量t的初值为什么是i，用来记录查找的位置的循环变量j的初值与终值的确定。
　　四、素材准备
　　1.学生素材：Form1.frm
　　该窗体的程序界面如图1所示，其中“自动生成数据”这一事件已能实现，“选择排序”的代码留空。
　　2.教师素材：PPT课件
　　五、教学过程
　　1.复习回顾，自然引出选择排序
　　问题：若要将34、45、32、12、33这组数据按从小到大的顺序进行冒泡排序，则需进行几次冒泡排序，每次的排序结果分别是什么，整个排序过程中进行了几次数据交换，是否能减少交换次数？
　　设计意图：复习冒泡排序算法，并通过分析数据交换的次数，提问学生是否有办法让数据交换的次数变少，引发学生思考与发现，进而引出选择排序算法。
　　2.实例示范，初步了解选择排序
　　教师以对四个无序整数进行递增排序处理为例（假定数据已存放在数组中），简要阐述选择排序算法。
　　第一遍：从第一个位置到最后一个位置中，找出最小值所在的位置，将该位置的值与第一个位置的值交换。
　　第二遍：从第二个位置到最后一个位置中，找出最小值所在的位置，将该位置的值与第二个位置的值交换。
　　依次类推，直到所有数都有序（如图2）。
　　随后，学生在了解选择排序的基础上完成以下课堂练习：
　　若要将34、45、32、12、33这一组数据按从小到大的顺序进行选择排序，则需进行几次选择排序，每次的排序结果分别是什么，整个排序过程中进行了几次数据交换？
　　学生在完成的过程中，与一开始对这组数据进行冒泡排序的过程进行比较，发现对这组数据来说，选择排序的交换次数仅为三次，大大优于冒泡排序。
　　设计意图：本部分仅对选择排序作简要阐述，未对其中“如何找到最小数问题”进行具体说明，旨在让学生先了解选择排序算法，对其有总体认识，树立信心。
　　3.层层递进，深入理解选择排序
　　在学生初步了解选择排序后，教师进而引导学生将选择排序的每一遍排序分解为两个步骤，即：
　　第一步：从位置1到位置n中，找到最小数的位置；若最小数不在位置1，则将最小数与位置1的数据进行交换。
　　第二步：从位置2到位置n中，找到最小数的位置；若最小数不在位置2，则将最小数与位置2的数据进行交换。
　　……
　　步骤分解后，接下来的关键是如何将这些步骤一一实现。教师以第一遍选择排序为例，对算法进行演示，具体如下：
　　先预设两个变量：变量t和j。其中变量t用来记录最小值所在的位置；变量j用来记录查找的位置。
　　【算法演示】
　　第一步：从位置1到位置4中，找到最小数的位置，具体过程如图3所示。
　　【分析】第一遍选择时，令记录最小值所在的位置的初始值为1，即t=1。故将d(t)依次与d(2)、d（3）、d(4)进行比较，每次比较可描述为：
　　第一次：当 j=2时
　　如果d(t)>d(j)，则令t=j
　　第二次：当 j=3时
　　如果d(t)>d(j)，则令t=j
　　第三次：当 j=4时
　　如果d(t)>d(j)，则令t=j
　　经过这样三次比较后，就完成了第一遍选择排序。
　　【观察】学生比较上述三次描述，发现j=2、3、4时，所执行的操作都是“如果d(t)>d(j)，则令t=j”，也就是说执行的是重复操作，继而就想到了用循环语句来实现这个操作，也就是说，上面三次比较可整合为如下语句：
　　t=1
　　for j=2 to 4
　　如果d(t)>d(j)，则令t=j
　　Next j
　　第二步：若最小数不在位置1，则将最小数与位置1的数据进行交换。
　　这一步学生普遍较容易理解，教师给出伪代码：如果t<>1，则交换d(1)和d(t)。
　　此时，教师引导学生到教师事先分发的form1窗体中完成第一次选择排序的程序代码，并进行调试运行。
　　当然，调试运行过程中，学生会发现单击“选择排序”按钮后，不能将排好序的数据输出到列表框2中，随后找到原因，将输出语句补充完整。由于输出语句学生已在冒泡排序中接触过，故能自行完成。
　　当学生完成了第一遍选择排序后，略有成就感，教师顺势提出第二遍选择排序。理解了第一遍选择排序，学生对第二遍、第三遍就不再那么陌生了，理解起来也更容易了。教师简单演示第二遍、第三遍选择排序算法后，学生便能在第一遍选择排序的基础上对代码略作修改，完成第二遍、第三遍选择排序的程序代码。
　　设计意图：分解问题难点，并能让学生自己总结归纳出解决的办法，既能落实知识点，又能激发学生的求知与探索欲望。
　　4.归纳总结，由特殊到一般
　　当学生通过三遍选择排序完成了对四个数进行排序的操作时，便跃跃欲试，想要对更多的数进行排序，于是就开始找寻规律，他们会发现这三部分程序的主体大部分是相似的，只不过变量t与变量j的值有所变化。教师再继续引导学生去找出变量t和变量j的变化规律。
　　为了便于学生更好地发现规律，教师在PPT上将三遍选择的代码放在一起，并将关键部分用红色字体标出，如图4所示。经过观察、分析，学生得出第i遍选择的程序代码。
　　至此，选择排序的核心代码已基本完成，只要学生将变量i的范围确定即可，而i的范围即为选择排序进行的遍数。这一点学生已经在一开始的算法分析中明确了，即：如果有n个数，需进行的选择遍数为n-1次。
　　故，学生可得出选择排序代码如下：
　　Fori= 1 to n-1
　　 t = i
　　For j = i+1 to n
　　 If d(t) > d(j) Thent=j
　　Next j
　　If t <> i Then
　　 temp = d(i)
　　 d(i)=d(t)
　　 d(t) = temp
　　 End If
　　Next i
　　整个过程下来，算法的基本框架以及程序的结构变得一目了然。
　　设计意图：将选择排序像剥洋葱一样一层层剥离，又慢慢地将其整合。整个过程中引导学生自己探索、发现规律、找寻方法，进而解决问题，不仅排除了学生对复杂算法的畏惧感，同时还激发了学生的学习热情。
　　5.调试运行，完成课堂任务
　　基本任务：学生先完成将一组数进行从小到大顺序排序的程序调试。然后，修改程序，使其能将一组无序数据进行降序排列。
　　拓展任务：时间充裕的学生可以根据知识拓展内容比较冒泡排序和选择排序的耗时，并在程序中体现出交换次数。
　　知识拓展：比较冒泡排序和选择排序的消耗时间。
　　T1=timer (timer是取得当前时间的函数)
　　T2=timer
　　Label4.caption=“冒泡排序运行时间:”& t2-t1 &“秒”
　　设计意图：通过由将一组数据进行递增排序改为递减排序，使学生明白程序中决定递增或递减的关键语句是什么。而拓展任务则是为了给有能力的学生提供更多的学习机会和展示自我的平台。
　　（作者单位：浙江宁波市北仑中学）