插入排序
从数组的第二个元素往下循环，每一个数字都要和他上面的所有数字进行比较，如果遇到比他大的数字，那么比他大的数字就要下沉一个，比他小的数字不变，大数字下沉后就会留出来一个空间，那么当前数字就会插入到那个空间
Sub 插入排序()
Dim arr, temp, x, y, imax, k, k1, k2
arr = Range("a1:a10")
For x = 2 To UBound(arr)
temp = arr(x, 1)
For y = x - 1 To 1 Step -1
If arr(y, 1) <= temp Then Exit For '如果上面的数都没有它大，没必要再找，跳出for循环，直接到下一步
arr(y + 1, 1) = arr(y, 1)
k1 = k1 + 1
Next y
arr(y + 1, 1) = temp '接上一步跳出for循环的语句
k2 = k2 + 1
Next x
Range("b2").Resize(UBound(arr)) = arr
MsgBox k1
End Sub
希尔排序
是插入排序法的改进版，大大提高了插入排序法的效率。
原理：插入排序是挨着的，希尔排序是间隔的比较。插入排序下降一个位置，希尔排序下降一个间隔。需要设置很多间隔。
Sub 希尔排序()
Dim arr
Dim 总大小, 间隔, x, y, temp, t
t = Timer
arr = Range("a1:a30")
总大小 = UBound(arr) - LBound(arr) + 1
间隔 = 1 '间隔初始值为1
If 总大小 > 13 Then '这里记住13，大于13计算间隔数，小于的话就用插入排序法，也就是间隔为1
Do While 间隔 < 总大小
间隔 = 间隔 * 3 + 1 '经验证这是最有效的间隔设置方法
Loop
间隔 = 间隔 \ 9 '反斜杠是四舍五入取整数的意思，比如9\4就是2
End If
Do While 间隔 '使用多个间隔来计算，使用do while 循环
For x = LBound(arr) + 间隔 To UBound(arr) '从这里开始就是插入排序法了
temp = arr(x, 1)
For y = x - 间隔 To LBound(arr) Step -间隔
If arr(y, 1) <= temp Then Exit For
arr(y + 间隔, 1) = arr(y, 1)
k1 = k1 + 1
Next y
arr(y + 间隔, 1) = temp
Next x
间隔 = 间隔 \ 3
Loop
MsgBox k1 'k是计数器，可以看到多少次
Range("b2").Resize(UBound(arr)) = arr
End Sub
总结：希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
算法思路：
先取一个正整数 d1(d1 < n)，把全部记录分成 d1 个组，所有距离为 d1 的倍数的记录看成一组，然后在各组内进行插入排序
然后取 d2(d2 < d1)
重复上述分组和排序操作；直到取 di = 1(i >= 1) 位置，即所有记录成为一个组，最后对这个组进行插入排序。一般选 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。
上述信息摘自http://bubkoo.com/2014/01/15/sort-algorithm/shell-sort/
关于希尔排序的间隔一点补充，涉及到步长的选择
内容摘自http://blog.csdn.net/u010383982/article/details/42302623
网友评论