浙江技术选考冒泡排序复习策略

姚春

信息技术自进入浙江高考以来，题目难度日益增加。算法做为选考考查的重要内容，重要性更是不言而喻，特别16、17两道压轴大题更是题型变化多样，是学生得分最主要的区分点。所以，对算法的复习就显得特别重要，一些考点频出的内容，如排序、对分查找、字符处理、矩阵转换等算法，要求学生掌握基本思想，能够灵活运用，以适应考试题材、题型的变化。这就要求教师在高三复习时要掌握基础，注重细节，让学生理解精髓。本文以选考中常出现的冒泡排序为例，共享复习策略。

冒泡排序的基本思想是n个待排序列，相邻两数两两比较，将较小（大）的数据向前或后进行交换，重复这一过程，直到选取排出一个最小（大）的数完成一趟，然后在进行第二趟，第三趟，直到最后完全排好序。升序程序段如图：

那么，有几个细节的地方，是需要我们帮助学生进行理解的。

1.升序、降序的理解判断

在程序段中，n个待排序列是按照升序還是降序排列，显然是由if语句中a（j）和a（j-1）的比较来确定的。假设条件是a（j）<=a（j-1）如何判定呢？首先我们要确定两数在数组中的位置，j在循环中初值是n，是数组中最后一个数的下标，a（j-1）代表前一个数，如果后一个数小于等于前一个数，把较小数交换到前一个位置，根据循环，小数不断的被交换到前面，第一趟以后，最小数就到数组中第一个位置了，所以判定是升序。同样，我们把条件改成a（j）>=a（j-1），大数被不断交换到前面，所以就变成降序序列了。

2.冒泡排序中趟数、比较次数和交换次数的理解和区别

我们先来看46，31，25，27，19这5个数的冒泡升序排序过程如下图（加粗数据为每趟原始数据）。在排序过程，我们从最后一个数开始，与前一个数依次进行比较，如果小于前面的数，则交换，然后在依次往前，两两比较，直到所有的数都比较过一次，我们把这样由后往前完整的经历一次称之为一趟（遍）。我们看到第一趟完成后，最小数19已排好，所以，每二趟不再参与排序，第二趟完成再排好一个数25，依此类推，当第四趟时，排好4个数，剩下最后一个就不用排了。所以5个数总共需要4趟，那么n个数，就只需要n-1趟。

关于比较次数，我们再看在第一趟中，从后往前相邻两数两两比较，19和27，19和25，19和31，19和46，5个数完全比较完需要4次。第二趟，排好一个数，只剩4个数需要比较3次。所以，第三趟2次，第四趟1次。5个数总的比较次数是4+3+2+1=10次，那么n个数，就需要比较（n-1）+（n-2）+（n-3）+……+1次，根据数列求公式，得到总比较次数公式n*（n-1）/2。

最后是交换次数，在冒泡排序中，相邻两数进行比较，但比较以后不一定要进行交换。比如，第二趟的第一次比较27和25，25小于27，小数在前，所以有比较但没有交换。在冒泡排序中，交换次数要根据排序数据实际交换情况进行计算，交换次数最少0次，最多和比较次数一样多，每次比较都进行交换。

在学习当中，只要我们理解了趟数，比较次数和交换交数。根据三者关系，可以很方便推导出冒泡排序VB程序段，更有助于我们更灵活的掌握应用。

3.从前往后，从后往前的不同

我们的冒泡排序的基本算法，都是从最后一数开始，相邻两数进行比较，把最小（大）值不断向前交换的过程。既然可以从后往前，当然也可以从前往后进行比较交换，虽然程序结果一样的，但中间的运算过程却不同。我们来看如图程序段。

如果我们按照基本算法，循环条件a（j）>a（j+1），j初值从1开始，前数a（j）大于后数a（j+1）交换，小数交换到前面，升序，外循环3次，可以排好3个最小数，所以选到A。当然选错了，因为对从前往后排序的理解不对。我们来看，从前往后，从a（1）开始，a（1）和a（2）比交换，如果a（1）大于a（2）交换，这次交换只是把a（1）和a（2）两数中相对小的数交换到a（1），并不是把数组中所有最小的数交换到a（1）的位置，而a（2）是两数中交换后相对较大的数，然后a（2）和a（3），a（3）和a（4），a（4）和a（5），a（5）和a（6）比较交换，两都比较大的数交换到后一位置。所以，虽然是升序，但第一趟，确定的却是最大数，放在数组中最后一个位置。所以上题中应选B这个答案。总结一下，冒泡排序，从后往前，升序首先确定的是最小值，放在数组第一个位置。从前往后，还是升序首先确定的是最大值，放在数组中最后一个位置，其从前往后的程序段如图。

综上所述，只要我们掌握了冒泡排序的基本思想，掌握了冒泡排序的一些基本变化，例如升序，降序关键点，从前往后比较，从后往前比较的不同。再加上一些练习题进行融会贯通，灵活应用，相信大家对于信息技术选考中11、12、16、17题中出现的冒泡排序问题将不再害怕。