选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。

选择.gif

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

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

✅1轮. 首先在未排序序列中找到最小元素,存放到排序序列的起始位置。

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

If a(m) > a(1) Then m = 1
If a(m) > a(2) Then m = 2
If a(m) > a(3) Then m = 3
If a(m) > a(4) Then m = 4

Print a(m)

'交换0号元素与m号元素的值,保证最小值存在a(0)中
t = a(m)
a(m) = a(0)
a(0) = t
End Sub

改进:

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

For i = 1 To 4 Step 1
If a(m) > a(i) Then m = i
Next i

Print a(m)

'交换0号元素与m号元素的值,保证最小值存在a(0)中
t = a(m)
a(m) = a(0)
a(0) = t
End Sub
a(0) a(1) a(2) a(3) a(4)
1 5 2 7 3

✅2轮. 现在,不考虑0号元素,对剩下的几个元素用相同的办法,找出它们中最小值,并且记住下标,把最小值更换到1号元素中。

1
2
3
4
5
6
7
8
9
10
11
m = 1
If a(m) > a(2) Then m = 2
If a(m) > a(3) Then m = 3
If a(m) > a(4) Then m = 4

Print a(m)

'交换1号元素与m号元素的值,保证最小值存在a(1)中
t = a(m)
a(m) = a(1)
a(1) = t

改进:

1
2
3
4
5
6
7
8
9
10
11
m = 1
For i = 2 To 4 Step 1
If a(m) > a(i) Then m = i
Next i

Print a(m)

'交换1号元素与m号元素的值,保证最小值存在a(1)中
t = a(m)
a(m) = a(1)
a(1) = t
a(0) a(1) a(2) a(3) a(4)
1 2 5 7 3

✅3轮. 现在,不考虑0号与1号元素,对剩下的几个元素用相同的办法,找出它们中最小值,并且记住下标,把最小值更换到2号元素中。

1
2
3
4
5
6
7
8
9
10
m = 2
If a(m) > a(3) Then m = 3
If a(m) > a(4) Then m = 4

Print a(m)

'交换2号元素与m号元素的值,保证最小值存在a(2)中
t = a(m)
a(m) = a(2)
a(2) = t

改进:

1
2
3
4
5
6
7
8
9
10
11
m = 2
For i = 3 To 4 Step 1
If a(m) > a(i) Then m = i
Next i

Print a(m)

'交换2号元素与m号元素的值,保证最小值存在a(2)中
t = a(m)
a(m) = a(2)
a(2) = t
a(0) a(1) a(2) a(3) a(4)
1 2 3 7 5

✅4轮. 现在,不考虑0号、1号、2号元素,对剩下的几个元素用相同的办法,找出它们中最小值,并且记住下标,把最小值更换到3号元素中。

1
2
3
4
5
6
7
8
9
m = 3
If a(m) > a(4) Then m = 4

Print a(m)

'交换3号元素与m号元素的值,保证最小值存在a(3)中
t = a(m)
a(m) = a(3)
a(3) = t

改进:

1
2
3
4
5
6
7
8
9
10
11
m = 3
For i = 4 To 4 Step 1
If a(m) > a(i) Then m = i
Next i

Print a(m)

'交换3号元素与m号元素的值,保证最小值存在a(3)中
t = a(m)
a(m) = a(3)
a(3) = t
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

所以,这个数列已经按照升序的顺序排列好了!

💪用双层嵌套循环改进一下:

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

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

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

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

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

Call selectionSort(a)

For Each e In a
Print e;
Next e
End Sub
Private Sub selectionSort(ByRef arr)
Dim m As Integer
For j = LBound(arr) To UBound(arr) - 1 Step 1
m = j
For i = j + 1 To UBound(arr) Step 1
If arr(m) > arr(i) Then m = i
Next i
t = arr(m): arr(m) = arr(j): arr(j) = t
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
22
23
Private Sub Form_Click()
Dim a: a = Array(2, 5, 1, 7, 3)

Call selectionSort(a)

For Each e In a
Print e;
Next e
End Sub
Private Sub selectionSort(ByRef arr)
Dim m As Integer
For j = LBound(arr) To UBound(arr) - 1 Step 1
m = j
For i = j + 1 To UBound(arr) Step 1
If arr(m) > arr(i) Then m = i
Next i
Call swap(arr(m), arr(j))
Next j
End Sub

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

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

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
Private Sub Form_Click()
Dim a: a = Array(2, 5, 1, 7, 3)

Call selectionSort(a)

For Each e In a
Print e;
Next e
End Sub
Private Sub selectionSort(ByRef arr, Optional order = "asc")
Dim m As Integer
For j = LBound(arr) To UBound(arr) - 1 Step 1
m = j
For i = j + 1 To UBound(arr) Step 1
If order = "asc" Then
If arr(m) > arr(i) Then m = i
Else
If arr(m) < arr(i) Then m = i
End If
Next i
Call swap(arr(m), arr(j))
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


 评论


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