有史以来最快的希尔排序 - 比历史贴快10倍，比Excel排序更快 - 兼论堆排序和快速排序

camle · 发表于 2010-12-13 20:51

收藏,学习.....

longming3 · 发表于 2010-12-13 21:04

太高级了，这样的东西对我等菜鸟来说太玄了，慢慢理解学习

Zamyi · 发表于 2010-12-14 10:52

不错，学习。不过换成两维的要慢不少，与工作表排序相比，反而慢一点点：
Option Base 1

Public Sub Test()
Dim b(), a(), m As Long, n As Long
n = 1000000
ReDim a(n, 1)
For i = 1 To n
  a(i, 1) = Int(n * Rnd())
  Next
b = a

t = Timer
m = 1
Call SortA(b(), m, n)
[e1] = Timer - t
[d1] = "灰袍法师的希尔排序用时："
Range("a1").Resize(n) = b

Range("b1").Resize(n) = a
t = Timer
Range("b1").Resize(n).Sort [b1]
[e2] = Timer - t
[d2] = "工作表排序用时："
End Sub

Sub SortA(ArrKey(), L As Long, R As Long)
Dim i As Long, j As Long, k As Long, h As Long, max_h As Long, offset As Long, swap_count As Long, one As Long
Dim Insert, h_arr() As Long, temp_h, temp_h2
temp_h = Array(1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769, 146305, 260609, 587521, 1045055, 2354689, 4188161, 9427969)
'此增量序列也是拥有 O(N^1.25)的阶，但是明显比 h(n+1) = 3 * h(n) + 1更高效
temp_h2 = Array(1, 5, 19, 41, 109, 211, 503, 929, 2161, 3907, 8929, 16001, 36293, 64763, 146309, 260609, 587527, 1045055, 2354689, 4188161, 9427969)

ReDim h_arr(LBound(temp_h2) To UBound(temp_h2))
h_arr(LBound(h_arr)) = 1
For i = LBound(h_arr) + 1 To UBound(h_arr)
'  h_arr(i) = 2.25 * h_arr(i - 1) + 1  '此增量序列拥有 O(N^1.25)的阶，但是速度也略为不如上面的序列1,5,19,41
'  h_arr(i) = 3 * h_arr(i - 1) + 1 '此增量序列拥有 O(N^1.25)的阶，但是速度明显不如上面的2.25序列
  h_arr(i) = temp_h2(i)
  If h_arr(i) < (R - L) / 9 Then max_h = i
'  If h_arr(i) > 2 ^ 31 / 2.25 Then Exit For
Next i
If max_h < LBound(h_arr) Then max_h = LBound(h_arr)

one = 1
For i = max_h To LBound(h_arr) Step -one
  h = h_arr(i)
  swap_count = 0
  For offset = 0 To h - 1
For j = L + offset To R Step h
   Insert = ArrKey(j, 1)
   For k = j - h To L + offset Step -h
      If Insert < ArrKey(k, 1) Then
      ArrKey(k + h, 1) = ArrKey(k, 1)
      ArrKey(k, 1) = Insert
      swap_count = swap_count + 1
      Else
      Exit For
      End If
   Next k
Next j
If swap_count = 0 And h <> 1 Then offset = offset + 5 '假如没有发生数据交换，那么假定数据是已经比较有序的，跳过若干次排序
  Next offset
  If swap_count = 0 Then                   '假如没有发生数据交换，那么假定数据非常有序，跳过2次h序列的扫描
i = i - 1
If i < 1 Then i = 1
  End If
Next i
End Sub

chenzyyysl · 发表于 2010-12-14 13:30

需仰望的高度，拜一个

lmecho · 发表于 2010-12-14 14:04

大家好才是真的好

secowu · 发表于 2010-12-14 14:08

另外一个高度，瞻仰先

cxh2010 · 发表于 2010-12-14 14:56

谢谢，太厉害了

lrlxxqxa · 发表于 2010-12-14 15:16

感谢分享：）

yubenjamin · 发表于 2010-12-14 15:25

虽然还看不懂，但是还是很感谢分享。

zhaobw1964 · 发表于 2010-12-14 16:12

是懂非懂，收藏学习。

		自动登录	找回密码
密码			免费注册

[原创] 有史以来最快的希尔排序 - 比历史贴快10倍，比Excel排序更快 - 兼论堆排序和快速排序