从玩转扑克牌中挖掘冒泡排序算法

　　● 教材分析
　　《排序》是浙江教育出版社出版的《算法与程序设计•选修1》第二章第三节的内容。在计算机科学中，排序算法是基础算法，在实际编程中有着广泛的应用，而冒泡排序是其中一种很典型而且相对简单的方法。学习它为后面将学习的选择排序做了铺垫。通过冒泡排序的学习，可以提高学生的程序设计能力，为今后在算法与程序设计方面的进一步学习打下基础。
　　● 学生分析
　　学生已经掌握了算法设计的基本知识，能用自然语言和流程图解决问题，对循环结构的流程图以及数组的使用方法都较熟悉。考虑到我校学生整体素质一般，知识连贯和综合应用能力较弱，为了学生能更快地掌握冒泡排序算法，所以在课前安排了对“数组”及“两个变量的值交换”的复习。
　　● 教学目标
　　知识与能力目标：掌握冒泡排序的原理；理解冒泡排序的流程图；能编写简单冒泡排序的程序。
　　过程与方法目标：学会使用冒泡排序思想解决简单排序问题的算法；进一步理解程序设计的基本方法，体会程序设计在现实中的作用。
　　情感、态度与价值观目标：培养分析问题、解决问题的能力，培养探究能力，激发学习热情。
　　● 教学的重、难点
　　重点：理解冒泡排序原理。
　　难点：理解冒泡排序中的内外循环次数。
　　● 课时安排
　　本部分分三课时进行。第一课时讲解排序的广泛性、重要性，介绍冒泡排序原理，尤其是冒泡排序中的两重循环的次数。第二、三课时讲解冒泡与选择排序的区别以及结合第五章第三节进行程序实现等。
　　● 媒体准备
　　教学准备：冒泡排序的课件、冒泡排序Flash动画、扑克牌、纸杯。
　　教学环境设计与布置：多媒体网络教室、投影机、多媒体教学平台、Flash软件、Excel软件。
　　● 教学过程
　　1.导入新课
　　准备工作：课前教师先给每组（机房共8组，每组5人）随机分5张扑克牌，要求每人手里持一张牌。
　　师：排序在我们的学习生活中随处可见，如成绩排序、交易量排序等。可以说有数字，就有排序。这节课我们的任务就是把同学手中的牌按从小到大进行排序。在各组内进行排序。
　　每组同学根据手里的牌，从小到大进行排序（即小的牌在前面，大的牌在后面）。如何把一组的扑克牌数字进行排序呢？有什么方法呢？
　　生1：把这组数字存放在Excel里面，点击排序就可以了。
　　生2：与自己前排和后排同学分别进行比较，并进行交换。
　　师：Excel里面的升序和降序是很方便。今天，我们自己编一个程序来实现此功能。排序过程需要两两比较。如何进行两两比较呢？一组数字相当于存放在一个数组里面，如Excel中一列数据，每个数据都对应一个地址。一列数据定义为一个数组，如Dim a[1，5]as integer。即每个元素如表1。
　　表1
　　如何交换数组a中元素a[2]，a[3]呢？假如我拿出两个杯子，一杯装有热牛奶，另一杯装有橙汁，如何进行交换呢？
　　生：需要引入一个空杯子。
　　师：对，也就是说我们需要引入一个变量，代码如表2。
　　表2
　　2.亲身实践
　　小组学生亲身实践，从小到大排序手中扑克牌（给学生足够的时间）。
　　师：大家注意，在排序时，我们需要两两进行比较（从排尾出发）。
　　学生观看冒泡排序动画演示。
　　师：同学们有没有发现，每遍排序完成后，都会冒出一个较小的数字。顾名思义，这种排序方法称为冒泡排序。
　　3.突破重难点
　　问题1：5个数字需要加工几遍？即每遍加工后，都冒出一个数字。
　　生：5个数需要加工5遍。
　　师：加工5遍也正确，每一遍加工，确定了数组中一个数。但是从程序的优化设计考虑，5个数排序，加工4遍就可以。即数组中确定了n-1个数，第n个数自然就确定。
　　问题2：每一遍加工，有哪些数参与两两比较？如第1遍有哪些数参与交换？第2遍又有哪些数参与交换，还是跟第1遍数相同吗？
　　某生回答如表3。
　　师：能否让所有数每遍都参与比较交换呢？
　　生：可以，但从优化设计角度，没有必要每个元素每遍都参与。因为每一遍都已经冒泡出一个数字。此数字在第二遍中，就不需要参与排序。
　　教师在Excel中再次演示过程，如图1。
　　4.引出程序核心代码（如表4）
　　5.实践与提高
　　问题1：给出4个待排序数67、98、100、85，在Excel中写出外循环次数以及内循环交换次数。并得出结论，排序完后，两两之间的数据共交换几次呢？
　　问题2：根据流程图，进行程序填空。2008年北京奥运会有很多个国家或地区参加，开幕式按照国家或地区英文名首字母的前后次序出场，已知其中七个国家或地区的名字（如表5），请写出冒泡后出场的次序表（如表6、图2）。尤其要注意数组类型以及赋值。
　　表5
　　6.总结评价
　　冒泡排序的原理：把较小的数据逐次向上推移，从最后一个元素起，依次比较相邻的两个元素中的数据，将较小的数据调换到上面。
　　师：冒泡排序是最基本的排序。从程序优化考虑，4个数字经过冒泡排序后，共交换多少次？
　　学生回答如表7，并总结出n个数参与冒泡排序交换次数为n×(n-1)
　　÷2。
　　● 教学反思
　　冒泡排序算法是用多重循环实现的，学生初次接触在理解上有点困难。本节课教学过程突显“先动手后观看，先具体后抽象”的教学思路，体现了新课程教学原则的一种特征，它是指在教学的流程上先经过学生自主或合作性的学习、探究，教师再进行点拨。
　　新课程理念要求以学生为中心，引导学生注意寻找、发现身边的实际问题，进而设计出算法和计算机程序解决这些问题。计算机程序如果从全局上去看，会显得很复杂，设计“从具体例子过渡到抽象化程序”的教学思路，简化了难度，学生可以从已经掌握的基本语句出发，经过逐步完善，最终理解并设计出完整的程序，从而培养算法思维，提高能力，提升信息素养。
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文