排序外传——数组排序之二

Zamyi

写完了二维数组排序——http://club.excelhome.net/thread-821316-1-1.html，觉得数组排序还有很多内容，有很多特殊的排序要求，所以有了这个外传。

一、整型数组排序

在各种排序中，冒泡排序最直观，但效率却低，需要循环n*(n-1)/2次（n为排序个数），灰袍法师优化的希尔排序，循环可以达到1.25n，但其结构复杂，也同时降低了效率。对于快速排序，循环也约0.86n，但里面的小循环却要约10.4n：

Dim M1, M2

Sub test1() '循环次数统计

Dim r&(1 To 10000)

For k = 1 To 100

For i = 1 To 10000

  r(i) = (10000 * Rnd)

Next

M1 = 0: M2 = 0

QSort2 r, 1, 10000

MM = MM + M1

Mn = Mn + M2

Next

MsgBox "100次平均小循环：" & MM / 100 & "平均小循环:" & Mn / 100

End Sub

Public Sub QSort2(r&(), L&, H&)

Dim i&, j&, X, y

i = L

j = H

X = r(L + 1 + Int((H - L - 1) * Rnd))

While (i <= j)

  While (r(i) < X And i < H) ’小循环

    M1 = M1 + 1

    i = i + 1

  Wend

  While (X < r(j) And j > L) ’小循环

    M1 = M1 + 1

    j = j - 1

  Wend

  If (i <= j) Then

    y = r(i)

    r(i) = r(j)

    r(j) = y

    i = i + 1

    j = j - 1

  End If

Wend

M2 = M2 + 1

If (L < j) Then QSort2 r, L, j

If (i < H) Then QSort2 r, i, H

End Sub

对于整型数组的排序，其实还有更好的方法。先看下面一段程序：

sub test

dim b(9)

a=array(4,1,7,2,9,0,5,8,6,3)

for i=0 to 9

         b(a(i))=a(i)

next

msgbox join(b)

end sub

    只一层循环，也不必对数组元素进行交换，即可对数组进行排序，效率可以说是最高的，但其特点是数组元素是整型，不重复连续的序列，适应性不高，优化如下：   

Public Sub IntSort(a&(), Optional Ord%)

    Dim i&, j&, Ma&, Mi&, L&, U&, b&()

    L = LBound(a)

    U = UBound(a)

    Ma = a(L)

    Mi = Ma

    ReDim c(L To U + 1)

    For i = L + 1 To U

      If a(i) > Ma Then Ma = a(i)

      If a(i) < Mi Then Mi = a(i)

    Next

    ReDim b(Mi To Ma + 1)

    For i = L To U

      b(a(i)) = b(a(i)) + 1

    Next

    If Ord Then

      n = U

      For i = Mi To Ma

        For j = 1 To b(i)

          a(n) = i

          n = n - 1

        Next

      Next

      Else

      n = L

      For i = Mi To Ma

        For j = 1 To b(i)

          a(n) = i

          n = n + 1

        Next

      Next

    End If

    End Sub

    虽然上面进行了三个循环，对于数组值区间和数组元素数目相接近的时候，总的循环量约为3n，但每个循环都非常简单，效率也是很高，以100万个1~10^6数据测试，比快速排序快约8倍。以以100万个1~10^7数据测试，结果也是本程序快。

结论：对于整型数组，数组区间比数组元素数目小10倍并且内存允许，用本程序排序是最好的。本程序的一个很好应用实例是成绩排名，参考：

http://club.excelhome.net/thread-689873-6-1.html

二、序列排序

EXCEL自带排序中有一个是按序列排序，可惜序列的数目非常少，象是不可以超过1000个，确也有限，也想做一个按序列排序，想来想去，除了用字典外，确实想不出有什么好办法：

Public Sub XLSort(a(), x(), Optional Ord%)

Dim d As New Dictionary, i&, j&, n&, b&()

For Each c In x  

  n = n + 1

  d(c) = n

Next

ReDim b(n)

L = LBound(a)

U = UBound(a)

For i = L To U

  t = d(a(i))

  b(t) = b(t) + 1

Next

If Ord Then

  For i = 1 To n

    For j = 1 To b(i)

      a(U) = d(i)

      U = U - 1

    Next

  Next

  Else

  For i = 1 To n

    For j = 1 To b(i)

      a(L) = d(i)

      L = L + 1

    Next

  Next

End If

Set d = Nothing

End Sub

三、文本数字混合排序

日常中经常有一种按如下的序列：

DN20XXX，DN25XXX，DN32XXX，DN40XXX，DN50XXX，DN100XXX，DN125XXX，DN150XXX

如若按照文本排序，却得到如下结果：

DN100XXX，DN125XXX，DN150XXX，DN20XXX，DN25XXX，DN32XXX，DN40XXX，DN50XXX

非常不爽，这种排序的处理只能分解为DN，20，XXX，按多KEY二维数组排序处理。代码从略。

排序外传.rar (23.99 KB, 下载次数: 412)

2012-6-14 09:58 上传

点击文件名下载附件

kangatang

好东西，学习了

liucqa

支持一下            

sunny_8848

支持一下楼主

mjzxlmg

速度是挺快的。但是只能整数性，限制了使用范围，改进下就完美了。

Zamyi

mjzxlmg 发表于 2012-6-14 14:39
速度是挺快的。但是只能整数性，限制了使用范围，改进下就完美了。

本来就是为整型数组写的，利用数组有序的下标作排序，如用改进？

mjzxlmg

Zamyi 发表于 2012-6-15 09:33
本来就是为整型数组写的，利用数组有序的下标作排序，如用改进？

如果用*100000000000的方法是否可行呢？这样一般情况下应该可以满足了。能否行得通呢？

Zamyi

mjzxlmg 发表于 2012-6-15 10:25
如果用*100000000000的方法是否可行呢？这样一般情况下应该可以满足了。能否行得通呢？

你看了序列排序没有？不得已用字典引用索引，效率肯定没有普通排序快。

psh1102

正在学习中...

￡Ulikeme

只能是整数，不能是小数