胡锋
绍兴市高级中学 312000
【摘要】冒泡排序是高三信息技术选考中常见的排序算法，是浙教版《算法与程序设计》的重点内容之一。针对学生容易入门，但很难熟练应用的弊端。本文通过对冒泡排序算法的特点、冒泡算法的核心代码、冒泡排序的优化、各种冒泡排序变式四个方面对冒泡排序算法进行由浅入深地分析，探讨解题策略，增强学生灵活应变的计算思维能力。
【关键字】冒泡排序 核心代码 优化 变式
一、冒泡排序算法的特点
冒泡排序从字面上看有冒泡二字，寓意就是水泡从底下逐渐往上冒，最终冒到水面。对于数据排序来讲，每次冒泡，就是将一个最值从底部冒到头部。如果总共N个元素，第1次冒泡产生第1个最值，第2次冒泡产生第2个最值（该最值次于第1个最值）……显然N-1次冒泡后，只剩下一个元素，当剩余一个元素时，就不需要比较和排序了。因此冒泡排序共需要进行N-1次冒泡。当某次冒泡时，先从底部开始比较相邻元素，如果两者顺序符合要求则不交换，否则交换，继续向前推进，直到头部为止。每次冒泡产生一个最值，这个最值不需要参加到下一轮冒泡过程中，因此每次冒泡长度都比前一次短1个长度。因此第1次冒泡比较N-1次，第2次冒泡比较N-2次……。而交换次数必定小于等于比较次数，因为两两比较时不一定满足交换条件。最差请况下，交换次数等于比较次数，如一个完全降序的序列要变成完成升序的序列。
二、冒泡算法的核心代码
结合冒泡排序算法的特点，冒泡排序共需要进行N-1次，每次冒泡长度比前一次减1。冒泡方向可以从前往后，也可以从后往前。当从前往后冒最大值时排升序；当从前往后冒最小值时排降序；当从后往前冒最大值时排降序；当从后往前冒最小值时排升序；
将上述文字描述变为VB核心代码(范例中数据存放在数组A(1)至A(N)中)：
【范例1】假设从前往后冒泡排升序
For i=1 To N-1 ‘冒泡排序共需要进行N-1次
For j=1 To N-i ‘从前往后冒泡，一般从第1个开始冒泡
If A(j)>A(j+1) Then ‘当前数比后一个数大
C=A(j) ‘交换A(j)和A(j+1)
A(j)=A(j+1)
A(j+1)=C
End If
Next j
Next i
【范例2】假设从前往后冒泡排降序
只要将范例1中的比较语句A(j)>A(j+1)改为A(j)<A(j+1)即可。
【范例3】假设从后往前冒泡排升序
For i=1 To N-1 ‘冒泡排序共需要进行N-1次
For j=N To i+1 Step -1 ‘从前往后冒泡，一般从第N个开始冒泡
If A(j)<A(j-1) Then ‘当前数比后一个数大
C=A(j) ‘交换A(j)和A(j-1)
A(j)=A(j-1)
A(j-1)=C
End If
Next j
Next i
【范例4】假设从前往后冒泡排降序
只要将范例3中的比较语句A(j)<A(j-1)改为A(j)>A(j-1)即可。
核心代码的重点：确定每次冒泡的起止位置，相邻元素的比较和交换。
核心代码的难点：确定每次冒泡的起止位置。
我们用范例1来说明如何确定每次冒泡的起止位置。
在这个例子中我们用A(j)和A(j+1)作为相邻元素，那么从前往后冒泡时，每一轮开始肯定是A(1)和A(2)进行比较，显然j应该从1开始。而结束位置每一次都不同，该如何确定呢？不妨列个表观察一下：
.png)
观察发现，每次冒泡的起止位置都与当前的次数有关，即第i次冒泡排序的起止位置是1至N-i。
还是假设从前往后冒泡排升序，如果我们用A(j)和A(j-1)作为相邻元素，相当于当前位置与前一个位置比较，那么第i次冒泡排序的起止位置是2至N-i+1。
用相同的方法可以推导出从后往前冒泡时，如果是A(j)和A(j-1)作为相邻元素，则j的起止位置是N至2；如果是A(j)和A(j+1)作为相邻元素，则j的起止位置是N-1至1。
三、冒泡排序的优化
【优化范例1】当某次冒泡排序时没有发生数据交换，说明数据已经完全有序了，不用继续冒泡过程，从而减少排序次数。
原始数据： 3 5 6 1 9 12
第1次冒泡： 1 3 5 6 9 12 有数据交换
第2次冒泡： 1 3 5 6 9 12 没有数据交换
第3次冒泡： 1 3 5 6 9 12
第4次冒泡： 1 3 5 6 9 12
第5次冒泡： 1 3 5 6 9 12
显然按照正常冒泡排序，6个元素要进行5次冒泡过程，但第2次冒泡后发现没有数据交换，说明数据已经有序，则第3次、第4次、第5次冒泡可跳过。
For i=1 To N-1
Flag=True ’设定标记
For j=N To i+1 Step -1
If A(j)<A(j-1) Then
C=A(j)
A(j)=A(j-1)
A(j-1)=C
Flag=False ‘修改标记
End If
Next j
If Flag Then Exit For ‘没有交换则退出排序
Next i
修改标记语句“Flag=False”不能用“Flag=Not Flag”。因为当某次冒泡过程中，交换次数为偶数时Flag又变回True。所以做标记的语句不能用来回变换的值的代码。
【优化范例2】当数据的后一段已经有序，我们可以大幅减少比较次数。
.png)
显然某次排序最后发生交换的位置为pos，那么pos后面的序列一定有序。例如100个元素排序，采用从前往后标准冒泡，第1次排序比较99次，第2次排序比较98次。但如果第1次排序时发现最后发生交换的位置是8，则第2次冒泡排序只要从位置1到位置8即可，大大缩短了冒泡长度。
Last=n-1 ‘默认第1次比较n-1次
For i=1 To n-1
pos=0
For j=1 To Last
If A(j)>A(j+1) Then
c=A(j)
A(j)=A(j+1)
A(j+1)=c
pos=j ‘记录发生交换的位置
End If
Next j
Last=pos ‘最后发生交换的位置作为下次排序的终点
Next i
程序中“pos=0”不能去掉，因为如果某次排序时没有数据交换，则pos就保留了前一次排序时最后发生交换的位置。从而后面每一次排序的结束位置都被固定。而实际上我们知道没有数据交换就是有序了。有了“pos=0”，那么没有数据交换时，pos的值就是0，那么后面每一次排序都将直接跳过。因为“For j=1 To 0”的循环一次也不进行。
四、各种冒泡排序变式
第1类:隔项冒泡排序，即奇数位和偶数位上的元素分别排序。一次排序后，奇数位产生一个最值，偶数位产生一个最值，即一次排序产生两个最值，故排序次数为n \ 2。
假设奇数位和偶数位分别排升序
For i=1 To n\2
For j=1 To n-2*i
If A(j)>A(j+2) Then
‘交换A(j)和A(j+2)，代码略
End If
Next j
Next i
如果希望奇数位和偶数位的升降序不同，可以巧妙的利用正负1来控制升降序，可以省下奇数位和偶数位的判断，相应语句修改如下：
If f*A(j)>f*A(j+2) Then
‘交换A(j)和A(j+2)，代码略
f=-f
End If
第2类：双向冒泡排序，即从前往后冒泡和从后往前冒泡都进行。相当于一次双向冒泡排序中包含两个不同方向的冒泡排序，分别在两端产生一个最大值和一个最小值，共两个最值，故排序次数为n \ 2。
假设排升序
For i=1 To n\2
‘第1次从第1位开始， 第2次从第2位开始， …
‘第1次到第n-1位结束， 第2次到第n-2位结束， …
For j=i To n-i
If A(j)>A(j+1) Then
‘交换A(j)和A(j+1)，代码略
End If
Next j
‘第1次从第n-1位开始， 第2次从第n-2位开始，…
‘第1次到第2位结束， 第2次到第3位结束， …
For j=n-i To i+1 Step -1
If A(j)<A(j-1) Then
‘交换A(j)和A(j-1)，代码略
End If
Next j
Next i
双向冒泡的关键是无论从前往后冒泡还是从后往前冒泡，其冒泡的起止位置是不断变化，相互靠近。
第3类：特异规则的冒泡排序。如将元素中的奇数偶数分开要求奇数在前并升序，又如将元素中的质数和非质数分开，等等。这种冒泡排序其实和标准冒泡排序最接近，只是控制交换的条件不是简单的比大小，而要根据规则进行相应的改变。
假设将元素中的奇数和偶数分开，奇数在前并升序
For i=1 To N-1
For j=1 To N-i
If A(j+1) Mod 2=1 And A(j) Mod 2=0 Then
C=A(j)
A(j)=A(j+1)
A(j+1)=C
ElseIf A(j+1) Mod 2=1 And A(j) Mod 2=1 And A(j+1)<A(j) Then
C=A(j)
A(j)=A(j+1)
A(j+1)=C
End If
Next j
Next i
当后面是奇数前面是偶数，则无论大小关系都交换；当前后都是奇数，则后面的更小再交换。
第4类：调整步长的冒泡排序，标准冒泡排序可以看成步长为1，隔项冒泡排序可以看成步长为2，当然还可以是其他的步长。
步长为1时所有元素为一组，步长为2时所有元素分为2组。显然步长为m时所有元素分为m组。由此可见只有步长为1时才能将所有元素完成排序，步长为其他数时，只能每组分别排序。为了使每组中的元素大于等于2，因此最大步长一般取元素个数的一半。同时如果步长不变只能每组分别排序，故一次排序后需要缩小步长进行下一次排序，直到步长为1，常见的步长缩小方式为m=m\2。
既然最后步长要变为1，那调整步长的意义何在？为什么不直接采用步长为1的冒泡排序呢？
这样做的意义在与可以减少数据交换的次数！
例如：9 8 7 6 5 4 3 2 1 要排升序
如果采用标准冒泡，显然9需要和后面的8个元素各交换一次才能冒到最后，一共需要交换8次。
如果先采用步长为4的冒泡，那么9只要与5和1分别交换一次，一共只需要交换2次。
假设排升序
m = n \ 2
Do While m > 0 ‘步长不为0时，继续排序
For i = 1 To m ‘步长m时共有m组数据
‘i为起始位置，m为步长，共需进行(n - i) \ m次排序
For j = 1 To (n - i) \ m
‘For k = i+m To n Step m 比较A(k)和A(k - m)
For k = i To n - m Step m
If A(k) > A(k + m) Then
C = A(k)
A(k) = A(k + m)
A(k + m) = C
End If
Next k
Next j
Next i
m = m \ 2 ‘调整步长
Loop
五、结语
冒泡排序是一种比较容易理解的排序方法，一般用于元素不是很多的情况。学习冒泡排序有利于学生对循环结构的理解和应用能力的提升，有利于高三学生
在选考算法中对冒泡排序本质的理解和兴趣的培养。同时冒泡排序也是信息技术选考中的一个高频高点，通常进行适当的变形，有一定难度。要熟练掌握冒泡排序算法，就要熟悉它的工作原理，熟识它的核心代码，有利于提高学生善于分析问题和了解一般规律的能力。
参考文献：
【期刊】：中国信息技术教育
【题目】：不一样的冒泡排序
【作者】：陈凯
【年(卷),期】：2019年05期