死磕 Dictionary！ 关于字典排序的 最终方案！ 。。。

山中老人

2020-07-22 整理代码和注释，排序部分代码 的 可读性提高些！

zopey

是否 边插入边排序？

山中老人

zopey 发表于 2020-7-22 17:46
是否 边插入边排序？

【插入法】比冒泡法速度快，但对逆向的数据，就是一个悲剧。
【快速排序法】，对顺序或逆序数据，都是个悲剧！
我只好自己写了个【二分法】先进行粗略排序。

目前的排序算法顺序：
      1、先用快速排序法，如果快速排序法掉坑里了，调用【插入法】。
      2、【插入法】检测数据量大，就先用【二分法】粗略排序（有限次数）。
      3、【二分法】每次排序前，先检查数据是否已经完成排序，已经完成就跳出去了！

代码：
Private Function InsertSort(Arr() As Long, Operator As Boolean, Optional ByVal low As Variant = Null, Optional ByVal high As Variant = Null) '插入算法
    Dim MinI As Long, MaxI As Long
    If VBA.IsNull(low) Then
        MinI = LBound(Arr)
    Else
        MinI = low
    End If
    If VBA.IsNull(high) Then
        MaxI = UBound(Arr)
    Else
        MaxI = high
    End If

    If MinI >= MaxI Then Exit Function '1个元素
    Dim i As Long
    i = MaxI - MinI
    If i > 100 Then '利用二分算法 粗略排序
        i = Int(i ^ (1 / 3)) '开3次方
        Call DichotomySort(Arr(), MinI, MaxI, Operator, i) '二分算法
    End If

    Dim Tmp As Long '临时变量
    Dim PreI As Long '插入指针
    For i = MinI + 1 To MaxI
        Tmp = Arr(i)
        PreI = i - 1
        Do While PreI >= MinI
            If Operator Then
                If Not SortCArr_(Arr(PreI)) < SortCArr_(Tmp) Then Exit Do
            Else
                If Not SortCArr_(Arr(PreI)) > SortCArr_(Tmp) Then Exit Do
            End If
            Arr(PreI + 1) = Arr(PreI) '数据右移
            PreI = PreI - 1 '指针左移
        Loop
        Arr(PreI + 1) = Tmp '插入
    Next i
End Function



Private Function DichotomySort(Arr() As Long, ByVal low As Long, ByVal high As Long, Operator As Boolean, Optional ByVal Depth As Long = 0) As Long '二分法排序(粗略排序)
    'Depth 深度计，<=0 退出
    If low >= high Then Exit Function
    If ScanSort(Arr, low, high, Operator) Then '检查排序
        Exit Function
    End If
    If (high - low) < 10 Then
        InsertSort Arr, Operator, low, high
        Exit Function
    End If
    On Error GoTo Err1
    Dim l As Long, h As Long, js As Long, LoopJs As Long, Str As String
    Do While True
        LoopJs = LoopJs + 1
        l = low
        h = high
        js = 0
        Do While l < h
            Str = "A"
            If Operator Then
                If Not SortCArr_(Arr(l)) < SortCArr_(Arr(h)) Then GoTo Loop1
            Else
                If Not SortCArr_(Arr(l)) > SortCArr_(Arr(h)) Then GoTo Loop1
            End If
            swap Arr, l, h
            js = js + 1
Loop1:
            l = l + 1
            h = h - 1
        Loop
        DichotomySort = l
        l = low
        Do While l < h And h <= high
            Str = "B"
            If Operator Then
                If Not SortCArr_(Arr(l)) < SortCArr_(Arr(h)) Then GoTo Loop2
            Else
                If Not SortCArr_(Arr(l)) > SortCArr_(Arr(h)) Then GoTo Loop2
            End If
            swap Arr, l, h
            js = js + 1
Loop2:
            l = l + 1
            h = h + 1
        Loop
        If js = 0 Then Exit Do
    Loop
    If high - low <= 2 Then Exit Function
    Depth = Depth - 1
    If Depth <= 0 Then Exit Function
    Call DichotomySort(Arr(), low, DichotomySort, Operator, Depth)
    Call DichotomySort(Arr(), DichotomySort + 1, high, Operator, Depth)
    Exit Function
Err1:
    Debug.Print LoopJs & " ERR:" & Err.Description
End Function

blackttea1

好东西，谢谢！

TB肥仔

先mark一下

山中老人

这里讲讲排序算法吧！
我用到的经典排序算法没啥可讲的，打家看看十大经典排序算法（动图演示）就好了！

我就讲讲比较特殊的地方：

1、【分组】 将相同的数据元素合并为一组，再进行排序。我是用的字典来实现的，实际效果非常好！大大降低后面排序的压力。同时还有一个好处，能保证【数据稳定】。
     【数据稳定】：相同数据再排序后能保持相对位置一致。例如： 先给班上学生按【成绩】排序，再按【性别】排序，最终结果 男生这部分成绩好的仍然保持在前，就称为【稳定】；否则，男生们的成绩顺序是乱的，就是【不稳定】。
      【数据稳定】在大多数场景，都是必要的。
2、【二分法】排序
     非常简单！ 就是简单的将要排序的数据等分为前后两段。取两段交界处的中点，通过比较交换，让中点之前的元素都小于等于它，中点以后的元素都大于等于它。再分别对前后两段，分别进行【二分法】排序。如此：1分2 ,2分4 ,4分8。
     这种算法，效率并不高，也不能保持【数据稳定】。但对一些特殊的情况非常好，例如：数据已经进行过排序，无论是顺序、还是逆序。
     它也很适合，给【插入法】进行预排序，大大提高【插入法】的速度。

山中老人

十大经典排序算法（动图演示）
https://www.cnblogs.com/onepixel/articles/7674659.html

山中老人

2020-07-24
没啥可更新的了，稍稍优化了点代码，增加了测试用属性.

Private Property Get MonitorSortArr(Arr() As Long) As Variant()
'监视排序数组。(实时监视排序每一步效果)
'用法：在要监视的函数内，右键【添加监视】将表达式“MonitorSortArr(Arr())”加入


实测：2百万的随机数，实际【排序算法执行】1秒多，但是【数据准备】生成2百万随机数据花费近2分钟；【分组】花了二十秒；【应用排序结果】花费了1分钟！


对各种类型、混乱程度的数据都能有较好的表现，这基本是算法优化到极限了吧！

山中老人

修订了一个bug.

橘子7027

谢谢楼主分享，菜鸟学习分享知识