希尔排序--用VB代码一步一步详解

一：源代码为：

Option Explicit

Sub shellsort(ByRef a() As Single) ' 子过程希尔排序算法, 对数组a 进行排序

Dim i, j, gap As Integer

Dim k, x, n As Integer

n = UBound(a)

gap = Int(n / 2)

While gap > 0 ' 第一while 循环

For i = gap + 1 To n ' 第二 for 循环

j = i - gap

While j > 0 ' 第三while 循环

If a(j) > a(j + gap) Then ' 按从小到大排序

x = a(j) ' 如果是If a(j) > a(j + gap)，那就是从大到小排序 a(j) = a(j + gap)

a(j + gap) = x

j = j - gap

Else

j = 0

End If

Wend

Next i

gap = Int(gap / 2)

Wend

End Sub

Private Sub Form_Activate() ' 当窗口激活的时候

Dim i, n As Integer

Dim a() As Single

Dim str As String

n = CInt(Val(InputBox("请输入要排序的数的个数，程序将用生成的随机数来排序:"))) ReDim a(n) As Single

str = "原始数据为:" & vbCrLf

For i = 1 To n '输入原始数据

a(i) = Int(Rnd * 100)

str = str & a(i) & " "

Next i

MsgBox str ' 这个窗口弹出原始数据为：

str = "排序后的数据为"

Call shellsort(a)

For i = 1 To n '输入原始数据

str = str & a(i) & " "

Next i

MsgBox str ' 这个窗口弹出排序后的数据为：

End Sub

二：用数据说明

比如输入的7个数为：(注：数组的下标是从1开始到7)

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

70 53 57 28 30 77 1

n = UBound(a) 既n=7

gap = Int(n / 2) 既gap=3

1：当gap=3的时候，进入大循环。

此时i=4 to 7 ， j = I – gap

(1) 当i=4 ，j=1

(2) 就对比a(1) 是否大于 a(1 + 3)，也就是对比70和28的值，因为70>28，所以互换两个

的值，互换之后a(1)=28，a(4)=70。

互换之后数组的排序为：

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

28 53 57 70 30 77 1

互换之后j 值=1-3= -2

(3) 因为不符合while j >0的条件，所以退出第三层循环；进入FOR 循环。

此时第一次结束第三个循环。

(4) 然后i=5,j=2

(5) 就对比a(2) 是否大于 a(2 + 3)，也就是对比53和30的值，因为53>30，所以互换两个

的值，互换之后a(2)=30，a(5)=53。

互换之后数组的排序为：

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

28 30 57 70 53 77 1

互换之后j 值=2-3= -1

(6) 因为不符合while j >0的条件，所以退出第三层循环；进入FOR 循环。

此时第二次结束第三个循环。

(7) 然后i=6,j=3

(8) 就对比a(3) 是否大于 a(3 + 3)，也就是对比57和77的值，因为57

此时数组的排序没变，任然为：

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

28 30 57 70 53 77 1

而j 值=0

（9）因为不符合while j >0的条件，所以退出第三层循环；进入FOR 循环。

此时第三次结束第三个循环。

-------------------------------------------------------------------------------------------------------

(10) 然后i=7 , j=4

(11) 就对比a(4) 是否大于 a(4 + 3)，也就是对比70和1的值，因为70>1，所以互换两个的值，互换之后a(4)=1，a(7)=70。

互换之后数组的排序为：

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

28 30 57 1 53 77 70

互换之后j 值=4-3= 1

(12) 这里要特别注意了:

因为j=1,符合while j >0的条件，所以不退出第三层循环；

继续执行第三个循环。也就是以下的代码：

While j > 0 ' 第三while 循环

If a(j) > a(j + gap) Then ' 按从小到大排序

x = a(j) ' 如果是If a(j) > a(j + gap)，那就是从大到小排序 a(j) = a(j + gap)

a(j + gap) = x

j = j - gap

Else

j = 0

End If

Wend

此时，j=1，对比a(1)是否大于a(1+3)，而28>1，所以互换两个的值，既a(1)=1，a(4)=28

互换之后数组的排序为：

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

1 30 57 28 53 77 70

互换之后j 值=1-3= -2

因为不符合while j >0的条件，所以退出第三层循环；进入FOR 循环。

此时第四次结束第三个循环。

但是for 循环里的i 值已经=7了，所以FOR 循环也结束了。

所以执行next I 之后的语句

既gap = Int(gap / 2) ，gap=1

2：因为gap=1，所以再次进入大循环。

此时的数组排序为：

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

1 30 57 28 53 77 70

此时i=2 to 7 ， j = I – gap

(1) 当i=2 ，j=1

(2) 就对比a(1) 是否大于 a(1 + 1)，也就是对比1和30的值，因为1

此时数组的排序没变，任然为：

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

1 30 57 28 53 77 70

而j 值=0

（3）因为不符合while j >0的条件，所以退出第三层循环；进入FOR 循环。

此时第五次结束第三个循环。

-----------------------------------------------------------------------------------------------------

(4) 当i=3 ，j=2

(5) 就对比a(2) 是否大于 a(2 + 1)，也就是对比30和57的值，因为30

此时数组的排序没变，任然为：

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

1 30 57 28 53 77 70

而j 值=0

(6) 因为不符合while j >0的条件，所以退出第三层循环；进入FOR 循环。

此时第六次结束第三个循环。

(7) 当i=4 ，j=3

(8) 就对比a(3) 是否大于 a(3 + 1)，也就是对比57和28的值，因为57>28，所以互换两个的值，互换之后a(3)=28，a(4)=57。

互换之后数组的排序为：

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

1 30 28 57 53 77 70

互换之后j 值=3-1= 2

(9) 因为j=2,符合while j >0的条件，所以不退出第三层循环；

继续执行第三个循环

此时，j=2，对比a(2)是否大于a(2+1)，而30>28，所以互换两个的值，既a(2)=28，a(3)=30

互换之后数组的排序为：

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

1 28 30 57 53 77 70

互换之后j 值=2-1= 1

因为j=1,符合while j >0的条件，所以不退出第三层循环；

继续执行第三个循环

此时再对比a(1)和a(2)的值，因为1

此时第七次结束第三个循环。

此时的数组排序为：

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

1 28 30 57 53 77 70

(10) 当i=5 ，j=4

(11) 就对比a(4) 是否大于 a(4 + 1)，也就是对比57和53的值，因为57>53，所以互换两个的值，互换之后a(4)=53，a(5)=57。

互换之后数组的排序为：

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

1 28 30 53 57 77 70

互换之后j 值=4-1= 3

(12) 这里又要特别注意了:

因为j=3,符合while j >0的条件，所以不退出第三层循环；

继续执行每三个循环。

此时，j=3，对比a(3)是否大于a(3+1)，而30

此时数组的排序没变，任然为：

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

1 28 30 53 57 77 70

而此时j 值= 0

因为不符合while j >0的条件，所以退出第三层循环；进入FOR 循环。

此时第八次结束第三个循环。

(13) 当i=6 ，j=5

(14) 就对比a(5) 是否大于 a(5 + 1)，也就是对比57和77的值，因为57

此时数组的排序没变，任然为：

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

1 28 30 53 57 77 70

而此时j 值=0

因为不符合while j >0的条件，所以退出第三层循环；进入FOR 循环。

此时第九次结束第三个循环。

(16) 当i=7 ，j=6

(17) 就对比a(6) 是否大于 a(6 + 1)，也就是对比77和70的值，因为77>70，所以互换两个的值，互换之后a(6)=70，a(7)=77。

互换之后数组的排序为：

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

1 28 30 53 57 70 77

互换之后j 值=6-1= 5

(18) 这里又要特别注意了:

因为j=5,符合while j >0的条件，所以不退出第三层循环；

继续执行每三个循环

此时要对比a(5)和a(6)的值，因为57

此时第十次结束第三个循环。

但是for 循环里的i 值已经=7了，所以FOR 循环也结束了。

所以执行next I 之后的语句

既gap = Int(gap / 2) ，gap=0

所以继续执行While gap > 0，但是条件不成立，直接执行END SUB。此时，SUB 子过程才算是真正的结束。而数组也已经排好序了。