冒泡排序(Bubble Sort)之所以叫冒泡排序,是因为这种排序算法的每一个元素都像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。

冒泡.gif

🎯 给出5个数值:2,5,1,7,3 进行升序排序⤴

a(0) a(1) a(2) a(3) a(4)
2 5 1 7 3

✅1轮. 通过两两相邻比较,如果发生逆序则进行交换的方式,找出2,5,1,7,3中的最大值。

1
2
3
4
5
6
7
8
Dim a: a = Array(2, 5, 1, 7, 3)

If a(0) > a(1) Then t = a(0): a(0) = a(1): a(1) = t '2与5比较,不交换 -> 2,5,1,7,3
If a(1) > a(2) Then t = a(1): a(1) = a(2): a(2) = t '5与1比较,交换 -> 2,1,5,7,3
If a(2) > a(3) Then t = a(2): a(2) = a(3): a(3) = t '5与7比较,不交换 -> 2,1,5,7,3
If a(3) > a(4) Then t = a(3): a(3) = a(4): a(4) = t '7与3比较,交换 -> 2,1,5,3,7

Print "最大值是:"; a(4)

结果:最大值是:7
改进:

1
2
3
4
5
6
7
Dim a: a = Array(2, 5, 1, 7, 3)

For i = 0 To 3 Step 1
If a(i) > a(i + 1) Then t = a(i): a(i) = a(i + 1): a(i + 1) = t
Next i

Print "最大值是:"; a(4)
a(0) a(1) a(2) a(3) a(4)
2 1 5 3 7

✅2轮. 下面,不考虑最大值7,那么剩下的数列为2,1,5,3,用上面的方式继续找出其中的最大值。

1
2
3
4
5
If a(0) > a(1) Then t = a(0): a(0) = a(1): a(1) = t     '2与1比较,交换    ->  1,2,5,3,7
If a(1) > a(2) Then t = a(1): a(1) = a(2): a(2) = t '2与5比较,不交换 -> 1,2,5,3,7
If a(2) > a(3) Then t = a(2): a(2) = a(3): a(3) = t '5与3比较,交换 -> 1,2,3,5,7

Print "最大值是:"; a(3)

结果:最大值是:5
改进:

1
2
3
4
5
For i = 0 To 2 Step 1
If a(i) > a(i + 1) Then t = a(i): a(i) = a(i + 1): a(i + 1) = t
Next i

Print "最大值是:"; a(3)
a(0) a(1) a(2) a(3) a(4)
1 2 3 5 7

✅3轮. 接着,找出1,2,3中的最大值 。

1
2
3
4
If a(0) > a(1) Then t = a(0): a(0) = a(1): a(1) = t     '1与2比较,不交换  ->  1,2,3,5,7
If a(1) > a(2) Then t = a(1): a(1) = a(2): a(2) = t '2与3比较,不交换 -> 1,2,3,5,7

Print "最大值是:"; a(2)

结果:最大值是:3
改进:

1
2
3
4
5
For i = 0 To 1 Step 1
If a(i) > a(i + 1) Then t = a(i): a(i) = a(i + 1): a(i + 1) = t
Next i

Print "最大值是:"; a(2)
a(0) a(1) a(2) a(3) a(4)
1 2 3 5 7

✅4轮. 接着,找出1,2中的最大值 。

1
2
3
If a(0) > a(1) Then t = a(0): a(0) = a(1): a(1) = t     '1与2比较,不交换  ->  1,2,3,5,7

Print "最大值是:"; a(1)

结果:最大值是:2
改进:

1
2
3
4
5
For i = 0 To 0 Step 1
If a(i) > a(i + 1) Then t = a(i): a(i) = a(i + 1): a(i + 1) = t
Next i

Print "最大值是:"; a(1)
a(0) a(1) a(2) a(3) a(4)
1 2 3 5 7

✅5. 最后,剩余的最后一个值不需要进行排序了。

a(0) a(1) a(2) a(3) a(4)
1 2 3 5 7

这个时候,
最大值 7 存在 a(4) 中;
次之的 5 存在 a(3) 中;
次之的 3 存在 a(2) 中;
次之的 2 存在 a(1) 中;
最小的 1 存在 a(0) 中;
所以,这个数列已经按照升序的顺序排列好了!

a(0) a(1) a(2) a(3) a(4)
1 2 3 5 7

#### 💪用双层嵌套循环改进一下:
1
2
3
4
5
6
7
8
9
For j = 0 To 3 Step 1
For i = 0 To 3 - j Step 1
If a(i) > a(i + 1) Then t = a(i): a(i) = a(i + 1): a(i + 1) = t
Next i
Next j

For Each e In a
Print e;
Next e
⚡如果数组的下标是从0开始的:
⚡外层 j 循环的次数:数组上界 - 1
⚡内层 i 循环的次数:数组上界 - 1 - j
⚡不等符号:取逆序符号(本例为升序,所以取">"号)

💪最后结合过程,改进为适用于任何大小的数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Private Sub Form_Click()
Dim a: a = Array(2, 5, 1, 7, 3, 0, 4)

Call bubbleSort(a)

For Each e In a
Print e;
Next e
End Sub

Private Sub bubbleSort(arr)
For j = LBound(arr) To UBound(arr) - 1 Step 1
For i = LBound(arr) To UBound(arr) - 1 - j Step 1
If arr(i) > arr(i + 1) Then t = arr(i): arr(i) = arr(i + 1): arr(i + 1) = t
Next i
Next j
End Sub

💪把2个值交换的步骤也抽象出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Private Sub Form_Click()
Dim a: a = Array(2, 5, 1, 7, 3, 0, 4)

Call bubbleSort(a) ' 调用冒泡排序

For Each e In a ' 迭代输出数组中的每个值
Print e;
Next e
End Sub
' 冒泡排序过程
Private Sub bubbleSort(arr)
For j = LBound(arr) To UBound(arr) - 1 Step 1
For i = LBound(arr) To UBound(arr) - 1 - j Step 1
If arr(i) > arr(i + 1) Then Call swap(arr(i), arr(i + 1))
Next i
Next j
End Sub
' 交换两个值的过程
Private Sub swap(m, n)
t = m: m = n: n = t
End Sub


👀思考:在上面的例子中,其实在第3轮中已经排序完成,那么如何进行优化呢?

利用flag做标记。如果在本轮排序中,元素有交换,则说明数列无序,如果没有交换,则说明数列已然有序,跳出外循环,也就是排序结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Private Sub Form_Click()
Dim a: a = Array(1, 2, 3, 4, 5)

Call bubbleSort(a)

For Each e In a
Print e;
Next e

End Sub

Private Sub bubbleSort(arr)
Dim flag As Boolean ' 设置一个flag,如果已经排好序那么设为true;如果不是有序的,那么设为false
For j = LBound(arr) To UBound(arr) - 1 Step 1
flag = True
For i = LBound(arr) To UBound(arr) - 1 - j Step 1
If arr(i) > arr(i + 1) Then Call swap(arr(i), arr(i + 1)): flag = False
Next i
If flag Then Exit For
Next j
End Sub

Private Sub swap(m, n)
t = m: m = n: n = t
End Sub

⚡在未优化的代码中,双层嵌套循环了10次:4+3+2+1 = 10;
⚡优化后的代码中,嵌套循环了9次,因为在第二轮中已经完成(其实直到第三轮才检测完),所以是:4+3+2 = 9 次。

👀最后,再加上排序的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Private Sub Form_Click()
Dim a: a = Array(1, 2, 3, 4, 5)

Call bubbleSort(a)

For Each e In a
Print e;
Next e

End Sub

Private Sub bubbleSort(ByRef arr, Optional order = "asc")
Dim flag As Boolean ' 设置一个flag,如果已经排好序那么设为true;如果不是有序的,那么设为false
For j = LBound(arr) To UBound(arr) - 1 Step 1
flag = True
For i = LBound(arr) To UBound(arr) - 1 - j Step 1
If order = "asc" Then
If arr(i) > arr(i + 1) Then Call swap(arr(i), arr(i + 1)): flag = False
Else
If arr(i) < arr(i + 1) Then Call swap(arr(i), arr(i + 1)): flag = False
End If
Next i
If flag Then Exit For
Next j
End Sub

Private Sub swap(m, n)
t = m: m = n: n = t
End Sub

```


📝 Optional(可选参数) 拓展:

声明子过程的名称,参数,以及构成其主体的代码。

语法

[Private | Public | Friend] [Static] Sub name [(arglist)]
[statements]
[Exit Sub]
[statements]

End Sub

Sub 语句的语法包含下面部分:

部分 描述
Public 可选的。表示所有模块的所有其它过程都可访问这个 Sub 过程。 如果在包含 Option Private 的模块中使用,则这个过程在该工程外是不可使用的。
Private 可选的。表示只有在包含其声明的模块中的其它过程可以访问该 Sub 过程。
Friend 可选的。只能在类模块中使用。表示该 Sub 过程在整个工程中都是可见的,但对对象实例的控制者是不可见的。
Static 可选的。表示在调用之间保留 Sub 过程的局部变量的值。Static 属性对在 Sub 外声明的变量不会产生影响,即使过程中也使用了这些变量。
name 必需的。Sub 的名称;遵循标准的变量命名约定。
arglist 可选的。代表在调用时要传递给 Sub 过程的参数的变量列表。多个变量则用逗号隔开。
statements 可选的。Sub 过程中所执行的任何语句组。

其中的 arglist 参数的语法以及语法各个部分如下:

[Optional] [ByVal | ByRef] [ParamArray] varname[( )] [As type] [= defaultvalue]

部分 描述
Optional 可选的。表示参数不是必需的关键字。如果使用了该选项,则 arglist 中的后续参数都必须是可选的,而且必须都使用 Optional 关键字声明。如果使用了 ParamArray,则任何参数都不能使用 Optional
ByVal 可选的。表示该参数按值传递。
ByRef 可选的。表示该参数按地址传递。ByRef 是 Visual Basic 的缺省选项。
ParamArray 可选的。只用于 arglist 的最后一个参数,指明最后这个参数是一个 Variant 元素的 Optional 数组。使用 ParamArray 关键字可以提供任意数目的参数。ParamArray 关键字不能与 ByValByRef,或 Optional 一起使用。
varname 必需的。代表参数的变量的名称;遵循标准的变量命名约定。
type 可选的。传递给该过程的参数的数据类型,可以是 ByteBooleanIntegerLongCurrencySingleDoubleDecimal(目前尚不支持)、DateString(只支持变长)、ObjectVariant。如果没有选择参数 Optional,则可以指定用户定义类型,或对象类型
defaultvalue 可选的。任何常数或常数表达式。只对 Optional 参数合法。如果类型为 Object,则显式的缺省值只能是 Nothing


 评论


载入天数...载入时分秒...