什么是冒泡排序?

我们今天再来学习下冒泡排序。

冒泡排序(Bubble Sort),是一种最基础的交换排序,有朋友甚至认为它比计数排序还简单。那么它为什么叫冒泡排序,而不是……潜水排序呢?这种排序方法是通过相邻的两个元素两两比较,根据大小来交换位置,最值元素就像气泡一样从左侧向右侧移动,故名冒泡排序。呃,这话说的似乎和没说也没多大差别?举个例子就好明白了。

如下图所示,A列有一组无序数据。接下来,我们会使用冒泡排序对数据作升序排列。

什么是冒泡排序?

首先,我们将数据装入数组r,此时数组内的元素是无序的。

什么是冒泡排序?

然后我们将数组内相邻的两个元素两两比较,先比大小,再决定是否交换位置,也就是冒泡。我们先让第1个元素6和它相邻的第2个元素1作比较,6比1大,所以6和1交换下位置,于是气泡来到了r(2)。

什么是冒泡排序?

然后6再和5作比较,6比5大,所以6和5再交换下位置

什么是冒泡排序?

6再和7作比较,6没有7大,不用交换,元素位置不变,但7比较大,所以气泡还是来到了7的位置,也就是r(4)。

什么是冒泡排序?

7和4比较,7比4大,7和4交换位置

什么是冒泡排序?

7和3比较,7比3大,7和3交换位置

什么是冒泡排序?

最后7和最后一个元素2比较,7比2大,7和2交换位置。于是气泡冒出,第一轮比试结束。

什么是冒泡排序?

第一轮比试结束后,获胜者最大值7站到了数组最右侧的位置,这个位置我们现在可以认为是一个有序区间,我们用红色填充,目前这个区间只有一个元素,那就是7号。另一边区域则依然为无序区。革命尚未成功,同志还需吃香的喝辣的努力生活呐。然后我们进行第2轮比试,选出第2个最大值,第2轮比试结束后,右侧的有序区间扩大了,有了两个元素。

什么是冒泡排序?

第3轮比试结果

什么是冒泡排序?

第4轮:

什么是冒泡排序?

第5轮:

什么是冒泡排序?

第6轮:

什么是冒泡排序?

至此,所有元素都是有序的了。我们也就实现了升序排列数据的目标。

……

通过观察以上比较过程,不难发现两个规律。

1),数组内有7个元素,我们只进行了6轮比试,为什么不进行7轮比试呢?484傻……剩下的那一个肯定是最小的嘛,还比啥子类。于是我们得出这样一个公式:元素的总个数-1=比试的总轮数

2),有序区间是在不断递增的,每轮至少增加1个元素。反过来说,无序区间是在不断缩小的,每轮至少缩小一个元素。而我们只需要在无序区间内作冒泡比较即可。

……

那么如何使用VBA代码实现这样一个比较过程呢?我们需要内外两层循环。外层的循环用于控制排序的轮数,前面讲过了,元素的总个数-1=比试的总轮数,于是代码也就是:

for i=1 to ubound(r)-1

内层循环用于控制每一轮比试的过程,相邻的两个元素作比较,它的循环代码表示为:

for  j=1 to ubound(r)

不过由于有序区间是递增的,因此并不需要每次都将所有的元素进行比较,我们只需要比较无序区间内的元素。比如,第1轮我们需要将1-7所有的元素进行比较。但第2轮,右侧有序区间存在了一个元素,我们只需要将左侧剩余的1-6元素进行比较。第3轮,我们只需要比较1-5之间的元素。以此类推

……

考虑到这个规律,我们可以将内循环代码修改为:for j=1 to ubound(r)-i。于是就得出一个较为完整的冒泡排序代码:

Sub VBABubbleSort()
Dim r, i&, j&, n
r = Range(“a2:a” & Cells(Rows.Count, 1).End(xlUp).Row)
‘数据源装入数组r
For i = 1 To UBound(r) – 1
‘外层循环,排序的轮数
For j = 1 To UBound(r) – i
‘内层循环,无序区间内相邻元素两两比较
If r(j, 1) > r(j + 1, 1) Then
‘升序排列,以大为交换依据,若是降序排序,则相反
n = r(j, 1) ‘取出r(j)的元素,准备交换位置
r(j, 1) = r(j + 1, 1)
r(j + 1, 1) = n
End If
Next
Next
Range(“c2”).Resize(UBound(r), 1) = r
End Sub

……

3,

事情似乎到此就结束了?然而并没有。我们上面的代码只是原始的冒泡排序,还有蛮多可以优化的地方。我们前面说过一句话,我们只需要比较无序区间的数据,于是这就出现了两个问题:

1),

有序区间是递增的,但每次都只递增一个元素吗?很显然并不是。如下图所示的原始数据,第一轮比试过后,右侧有4个元素已经形成了有序区间,此时再让相邻的元素对他们进行多次两两比较完全是多余的。

什么是冒泡排序?

如何避免这种情况呢?也就是说我们如何动态标记无序区间的边界,让每轮比试只存在于无序区间,避免没必要的内部循环?

……

2),

我们前面总结出一个公式,元素的总个数-1=比试的总轮数,但是这个总轮数并不是每次都是必须的。在上述示例,第5轮比试后我们就已经得出了有序数列,第六轮比试完全是多余的。

什么是冒泡排序?

甚至在极端情况下,比如上图所示的数据,我们只进行一轮比试,就可以将全部元素形成有序区间了。这大概就是传说中的一轮游吧?甚至在更极端的情况下,原始数据就已经是有序的了,比如1到100万之间递增的序列号,只是我们肉眼看不出来而已——但更没有必要进行多轮排序了不是?一轮过后代码就应该知道数据是有序的!不然我要代码何用?嗯哼?熬夜装深沉吗?好吧~虽然我就是这样的人啊~事实上,通常8个数据只进行5轮左右的比较就有很大的概率得到有序数列了,剩下的多轮计算完全是多余的。那么如何避免这种情况呢?也就是说我们如何判断元素已经是有序数列了,及时退出没必要的外层循环?

……

我们先来解决第2个问题,它比较简单,比较容易欺负。冒泡排序的思想是相邻的两个元素作比较,根据大小交换位置——意思也就是当比试的过程中不存在位置交换时,整个数据区间就已经是有序,没必要再比较下去。那么,我们根据这一特点,在代码中加上个布尔值标记一下是否进行了数据交换,就可以及时退出没必要的轮次循环了不是?修改后代码如下:

Sub VBABubbleSort2()
Dim r, i&, j&, n, blnIsSorted As Boolean
r = Range(“a2:a” & Cells(Rows.Count, 1).End(xlUp).Row)
‘数据源装入数组r
For i = 1 To UBound(r) – 1
‘外层循环,排序的轮数
blnIsSorted = True
‘判断是否有序的标记,每一轮比试开始都假定为true
For j = 1 To UBound(r) – i
‘内层循环,无序区间内相邻元素两两比较
If r(j, 1) > r(j + 1, 1) Then
‘升序排列,以大为交换依据,若是降序排序,则相反
n = r(j, 1) ‘取出r(j)的元素,准备交换位置
r(j, 1) = r(j + 1, 1)
r(j + 1, 1) = n
blnIsSorted = False
‘有元素交换,说明数据还不是有序,标记为false
End If
Next
If blnIsSorted Then Exit For ‘如果数据已经是有序的,则退出循环
Next
Range(“c2”).Resize(UBound(r), 1) = r
End Sub

然后我们再来解决第一个问题:如何动态标记有序区间的位置,让比试只存在于无序区域?相信你已经想到了,在每轮比试中,最后发生元素交换的位置就是无序区间的边界,因此我们只需要在开始:最后发生元素交换的位置之间的区域进行比较就可以了。修改后代码如下:

Sub VBABubbleSort3()
Dim r, i&, j&, n, blnIsSorted As Boolean
Dim lngBorder&
r = Range(“a2:a” & Cells(Rows.Count, 1).End(xlUp).Row)
‘数据源装入数组r
lngBorder = UBound(r)
‘原始的无序区间可能的最大边界
For i = 1 To UBound(r) – 1
‘外层循环,排序的轮数
blnIsSorted = True
‘判断是否有序的标记,每一轮比试开始都假定为true
For j = 1 To lngBorder – 1
‘内层循环,无序区间内相邻元素两两比较
If r(j, 1) > r(j + 1, 1) Then
‘升序排列,以大为交换依据,若是降序排序,则相反
n = r(j, 1) ‘取出r(j)的元素,准备交换位置
r(j, 1) = r(j + 1, 1)
r(j + 1, 1) = n
blnIsSorted = False
‘有元素交换,说明数据还不是有序,标记为false
lngBorder = j
‘更新无序区间出现的最后边界
End If
Next
If blnIsSorted Then Exit For ‘如果数据已经是有序的,则退出循环
Next
Range(“c2”).Resize(UBound(r), 1) = r
End Sub

……

4,

做个小结。在数据支持计数排序的情况下,也就是数据最大值和最小值之间跨度不是很大的整数的时候,当然首选计数排序。但当数据不支持计数排序,而数据量又不是很大的情况下,可以使用冒泡排序。打个响指,由于大部分VBA爱好者并不是专业的程序员,所以我们在推文里刻意回避了时间复杂度的描述,不过不得不说的是(家传三不主义,哈哈),冒泡排序的计算效率并不高,即便优化之后也是如此~所以……假如数据量很大,比如百万啊千万啊,冒泡排序就有点不甚理想了。

分享到:

评论抢沙发

评论前必须登录!