跟着校长学VBA之第26集:VBA数组7之排序算法（下）

hwc2ycy

一、插入排序法
原理：假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后，可以保证a[1…k]是局部有序的，保证了插入过程的正确性.

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2

1. Sub 插入排序单元格演示()
   
2.     On Error Resume Next
   
3.     Dim arr, temp, x, y, t, iMax, k
   
4.    
   
5.     Application.ScreenUpdating = False
   
6. 
   
7.     '清除原有数据
   
8.     Range("c1").CurrentRegion.Clear
   
9.     Range("a1").CurrentRegion.Clear
   
10.    
    
11.     For x = 1 To 10
    
12.         Range("a" & x) = Application.WorksheetFunction.RandBetween(1, 1000)
    
13.     Next
    
14.    
    
15.     Range("a1:a10").Copy
    
16.     Range("d1").PasteSpecial Transpose:=True
    
17.     Range("c1") = "原始序列"
    
18.     Application.CutCopyMode = False
    
19. 
    
20.     For x = 2 To 10
    
21.         temp = Cells(x, 1)    '记得要插入的值
    
22.         Range("A" & x).Interior.ColorIndex = 3
    
23.         For y = x - 1 To 1 Step -1
    
24.             If Cells(y, 1) <= temp Then Exit For
    
25.             Range("A" & y).Interior.ColorIndex = 4  '交换过的值填上绿色背景
    
26.             Cells(y + 1, 1) = Cells(y, 1)
    
27.             Range("A" & y + 1).Interior.ColorIndex = 4 '交换过的值填上绿色背景
    
28.         Next y
    
29.         
    
30.         Cells(y + 1, 1) = temp                          '插入值
    
31.         Range("a1:a10").Copy
    
32.         Range("d" & x).PasteSpecial Transpose:=True
    
33.         Range("c" & x) = "第 " & x - 1 & " 轮"
    
34.         Application.CutCopyMode = False
    
35.         Range("a1:a10").ClearFormats
    
36.     Next
    
37. End Sub

复制代码

附上效果图，绿色区域为交换过后区域，红色代表每一轮循环的起点


二、希尔排序法
        先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
        比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除 多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
        一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：
5，3，1