张远骏
（浙江省浦江县第二中学 浦江 322200）
【摘 要】：自2015年高一新生开始，浙江省实行新高考改革，信息技术中的排序算法也成为必考考点之一。本文通过对冒泡排序的教学，在学生理解冒泡排序设计思想的基础上，提出了两种新的冒泡排序方法。一是根据可以同时选择出最大数和最小数的特点上提出了双向冒泡法，二是加入了标志位的新的冒泡排序法，以达到培养学生分析问题、发现规律的能力。经过算法分析得出，改进的算法时间复杂度也比传统冒泡排序方法有所改善。
【关键字】：排序算法， 冒泡排序，双向冒泡排序，标志位冒泡排序，时间复杂度
浙江的新高考改革将信息技术课作为技术科目的一部分纳入了高考选考科目中，原本是选修课内容的排序算法及程序实现也成为高考的加试考点。而冒泡排序也是计算机程序设计中的一种重要操作，特别是高效率的排序是计算机研究中的重要课题之一。
一、冒泡排序的基本思想
冒泡排序是排序中一种简单的排序方法。它的基本思想是对所有相邻记录关键字值进行比较，使较小的（大）关键字的记录值往上升，这样从上到下执行一遍后，关键字最大（小）的记录沉到最底下。在下一遍扫描是，可以不考虑这个关键字最大（小）的记录，而减少一次比较，上述比较过程反复执行，直到所有的记录不再上升为止。
冒泡排序算法的实现需要两重循环，我在教学中使用了5张扑克牌来演示冒泡排序的逐个过程（从小到大排序），以强化学生对冒泡排序的理解。5张扑克牌，要进行从小到大的排序。
1、第一轮冒泡排序首先比较第5个数与第4个数，将其中较小的数换到第4个数的位置，然后比较第4个数与第3个数，将其中较小的数换到第3个数的位置，重复这一过程，直到比较完第2个数与第1个数且完成交换，称为第1遍加工。第1遍加工完成后，最小的数据已经上升到第1个位置。
2、对余下的第2张到第5张扑克牌重复上述处理过程，直至最后进行余下的两个数据进行比较和交换。
具体的排序算法如下：
For i=1 to 4
For j=5 to i+1 step -1
If a(j)<a(j-1) then
t=a(j):a(j)=a(j-1):a(j-1)=t
End if
Next j
Next i
二、冒泡排序改进方法之一
从上述的分析算法我们可以发现，刚才使用的冒泡排序是从一端开始比较的，经过第1轮的排序后使得最小的数上浮到第1个位置，如此重复使得排序完成。那我们可以考虑，在上浮的同时也下沉。在每一趟比较中，最小数上浮，同时使得最大数下沉，这样就可以减少比较的次数，反复执行这一过程直到为1或0时为止，这就是双向冒泡排序的思想。
期刊文章分类查询,尽在期刊图书馆
具体的双向冒泡排序方法如下：
For i=1 to 5
If a(i)>a(5-i+1) Then
t=a(i):a(i)=a(5-i+1):a(5-i+1)=t
End if
For j=i+1 to 5-i
If a(j)<a(i) then
t=a(i):a(i)=a(j):a(j)=t
End if
If a(j)>a(5-i+1) Then
t=a(j):a(j)=a(5-i+1):a(5-i+1)=t
End if
Next j
Next i
三、冒泡排序的改进方法之二
考虑冒泡排序的基本思想，我们发现每一轮的比较交换中都有重复的比较交换，我们可以考虑结合选择排序的思想，在内循环中标示出交换发生的位置，这样可以避免一些重复的比较交换。具体的算法如下：
For i=1 to 4
n=n+1
For j=5 to n step -1
m=m+1
If a(j)<a(j-1) Then
t=a(j):a(j)=a(j-1):a(j-1)=t
n=j
End if
Next j
Next i
四、算法性能比较
对于传统的冒泡排序算法，每次比较都有可能交换数据，因此最多要进行n×（n-1）/2次数据的两两交换，所以传统冒泡排序算法的平均时间复杂度为O(n^2)。传统的冒泡排序算法整个排序过程需要n-1轮，而双向冒泡排序法只需要n/2轮，若记录的初始状态是（从小到大）的，则一轮扫描即可完成排序，所需的关键比较和记录移动的次数分别达到最小值n-1和0，即双向冒泡排序算法最好的时间复杂度为O(n)；若初始记录为反序的则需要进行n/2轮排序。对于标志位冒泡排序来说，从这种算法可以看出，若记录的初始状态是正序（从小到大）的，则一趟扫描即可完成排序。所需的比较和记录移动的次数分别达到最小值n- 1和0，即算法最好的时间复杂度为O(n)；若初始记录是反序（从大到小）的，则需要进行n-1趟排序，每趟排序要进行n-i次关键宇的比较，且每次比较都必须移动记录三次来达到交换记录位置。在这情况下比较和移动次数达到最大值：比较次数为Cmax= n(n-1)/2，移动次数： Mmax=3n(n-1)/2，因此这种改进方法的最坏时间复杂度也为O(n^2)。在平均情况下，算法可能在中间的某一趟排序完后就终止，但总的比较次数仍为O(n^2)，所以算法的平均时间复杂度为O(n^2)。因此，这种算法最好的时间复杂度为O(n)。最坏时间复杂度为O(n^2)。
冒泡排序是程序设计教学中的一个比较典型的算法，在本次vb程序教学中，我先用扑克牌举例引出了传统的冒泡排序算法，然后通过传统冒泡排序的缺陷提出了两种改进的算法，使学生能够对这些算法有一个比较深刻的认识，以达到巩固和掌握的目的。
参考文献：
1．浙江考试2015考试标准
2．周晖.《高中同步学习指南：算法与程序设计》
3．王晓东.《计算机算法设计与分析》
论文作者:张远骏
论文发表刊物:《读写算（新课程论坛）》2015年第5期（上）供稿
论文发表时间:2015/9/8
标签：算法论文; 复杂度论文; 个数论文; 时间论文; 双向论文; 到第论文; 次数论文; 《读写算（新课程论坛）》2015年第5期（上）供稿论文;