[原創] 快速穩定排序法測試

linyancheng

快速穩定排序法測試
ˉ
一般的快速排序演算法為不穩定的排序法，
將之改良為穩定的排序法，
命名為「快速穩定排序法」。
（不穩定是指相等元素會被改變順序，反之相等元素會保持相對位置。）
ˉ
測試結果：
一維陣列，10000筆數字，
氣泡排序法為14.299秒
快速穩定排序法為0.082秒
（氣泡排序法為入門的排序法，亦為不穩定的排序法。）
二維陣列，10000x2筆數字
快速穩定排序法為0.198秒（看最右一行資料遞增，表示為穩定排序。）
（不同電腦或Excel版本下，會有不同結果；同電腦或Excel版本下，每次演算也會有些微差距。）

jackyq

10000x2  = 0.198秒 算慢了
排序如果用得很兇
應該要用 VC 封裝1下
會是 0.198秒 的 10 倍速

linyancheng

我已經夠用了
而且我沒研究封裝
VBA用那個方便嗎？

而且你有測試過嗎？真有10倍速，懷疑！

測試條件：
陣列用Variant資料型態，因功能需要
二維陣列要能設定排序維度、排序維度的元素起迄範圍、另一維度的元素範圍(1個)，因功能需要
排序後相等元素要保持相對位置，不能被調換。

linyancheng

漏掉了，再加一個條件：
比較模式用option compare text，功能需要

jackyq

夠用就好

每個人 CPU 等級不一樣
只能自己和自己比
計算量 720萬筆
EXCEL + VBA  不穩排 = 15.567 sec
EXCEL + VBA      穩排 = 18.398 sec
EXCEL + VC    不穩排   =   1.547 sec
EXCEL + VC        穩排   =   1.603 sec

linyancheng

回復 5# jackyq


所以封裝的是相同的代碼嗎？
還是有做語言的調整？

真的差那麼多，
難怪Excel本身的排序速度這麼快！

其實我的測試是因為本來用的氣泡排序法太慢，而且是不穩定排序，
所以才寫一個快速穩定排序法來測試看看，
兩者的差距對我已經很夠了！

linyancheng

我的代碼，可幫忙優化嗎？謝謝！

Option Explicit
Option Base 1
Option Compare Text

Public Sub S_二維陣列快速穩定遞增排序_01(ByRef 原始二維陣列 As Variant, ByVal 排序維度 As Long, ByVal 排序元素序 As Long, ByVal 起限 As Long, ByVal 迄限 As Long)

    On Error Resume Next
   
    Dim N As Long
    Dim H As Long
    Dim K As Long
    Dim X As Long
    Dim Y As Long
   
    Dim 陣列限數 As Long
    Dim 基準 As Variant
    Dim 原始二維陣列數 As Long
    Dim 陣列累計數 As Long
   
    Dim 起陣列() As Variant
    Dim 迄陣列() As Variant
    Dim 基陣列() As Variant
   
    陣列限數 = 迄限 - 起限 + 1
   
    If 陣列限數 < 2 Then
        Exit Sub
    End If
   
    If 排序維度 = 1 Then
        基準 = 原始二維陣列((起限 + 迄限) \ 2, 排序元素序)
        原始二維陣列數 = UBound(原始二維陣列, 2) - LBound(原始二維陣列, 2) + 1
        
        ReDim 起陣列(陣列限數 - 1, 原始二維陣列數) As Variant
        ReDim 迄陣列(陣列限數 - 1, 原始二維陣列數) As Variant
        ReDim 基陣列(陣列限數, 原始二維陣列數) As Variant
        
        N = 0
        H = 0
        K = 0
        For X = 起限 To 迄限
            If 原始二維陣列(X, 排序元素序) < 基準 Then
                N = N + 1
               
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    起陣列(N, Y) = 原始二維陣列(X, Y)
                Next Y
            ElseIf 原始二維陣列(X, 排序元素序) = 基準 Then
                H = H + 1
               
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    基陣列(H, Y) = 原始二維陣列(X, Y)
                Next Y
            Else
                K = K + 1
               
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    迄陣列(K, Y) = 原始二維陣列(X, Y)
                Next Y
            End If
        Next X
        
        If N > 1 Then
            S_二維陣列快速穩定遞增排序_01 起陣列, 1, 排序元素序, 1, N
        End If
        
        If K > 1 Then
            S_二維陣列快速穩定遞增排序_01 迄陣列, 1, 排序元素序, 1, K
        End If
        
        陣列累計數 = 0
        For X = 起限 To 迄限
            陣列累計數 = 陣列累計數 + 1
            
            If 陣列累計數 <= N Then
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    原始二維陣列(X, Y) = 起陣列(陣列累計數, Y)
                Next Y
            ElseIf 陣列累計數 <= (N + H) Then
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    原始二維陣列(X, Y) = 基陣列(陣列累計數 - N, Y)
                Next Y
            Else
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    原始二維陣列(X, Y) = 迄陣列(陣列累計數 - N - H, Y)
                Next Y
            End If
        Next X
    Else
        基準 = 原始二維陣列(排序元素序, (起限 + 迄限) \ 2)
        原始二維陣列數 = UBound(原始二維陣列, 1) - LBound(原始二維陣列, 1) + 1
        
        ReDim 起陣列(原始二維陣列數, 陣列限數 - 1) As Variant
        ReDim 迄陣列(原始二維陣列數, 陣列限數 - 1) As Variant
        ReDim 基陣列(原始二維陣列數, 陣列限數) As Variant
        
        N = 0
        H = 0
        K = 0
        For Y = 起限 To 迄限
            If 原始二維陣列(排序元素序, Y) < 基準 Then
                N = N + 1
               
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    起陣列(X, N) = 原始二維陣列(X, Y)
                Next X
            ElseIf 原始二維陣列(排序元素序, Y) = 基準 Then
                H = H + 1
               
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    基陣列(X, H) = 原始二維陣列(X, Y)
                Next X
            Else
                K = K + 1
               
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    迄陣列(X, K) = 原始二維陣列(X, Y)
                Next X
            End If
        Next Y
        
        If N > 1 Then
            S_二維陣列快速穩定遞增排序_01 起陣列, 2, 排序元素序, 1, N
        End If
        
        If K > 1 Then
            S_二維陣列快速穩定遞增排序_01 迄陣列, 2, 排序元素序, 1, K
        End If
        
        陣列累計數 = 0
        For Y = 起限 To 迄限
            陣列累計數 = 陣列累計數 + 1
            
            If 陣列累計數 <= N Then
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    原始二維陣列(X, Y) = 起陣列(X, 陣列累計數)
                Next X
            ElseIf 陣列累計數 <= (N + H) Then
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    原始二維陣列(X, Y) = 基陣列(X, 陣列累計數 - N)
                Next X
            Else
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    原始二維陣列(X, Y) = 迄陣列(X, 陣列累計數 - N - H)
                Next X
            End If
        Next Y
    End If

End Sub

jackyq

http://jackyq.pixnet.net/blog/post/103456672-2017_02_14

linyancheng

回復 8# jackyq


    感謝，真的太強了，先生是讀資訊科系的嗎？

我看出主要利用Index，只要排序一維，再利用Index作多維移動，有效減少排序過程中不必要的反覆移動，維度元素愈多，提速愈明顯，聰明！

另外幾個問題請教：

像：
      Dim value
      For X = 起限 To 迄限
             value = 原始1維陣列(X)
          If value < 基準 Then
             N = N + 1: 起陣列(N) = value: 起陣列_ID(N) = IndexAR(X)
使用 value 一定比較快嗎？雖然不用反覆進行提取「原始1維陣列(X)」，但多一個「value = 原始1維陣列(X)」的動作，以前也想過這個問題。

像：
ReDim Preserve 起陣列(0 To N), 起陣列_ID(0 To N)  'reduce ram consumption
根據我的經驗，ReDim Preserve很耗時，此例可以不用嗎？當然次數或許不多，但也不少。

linyancheng

回復 8# jackyq


    像 UBound(原始二維陣列, 2) 也先代入變數，之後多次則以變數引用，如此是否也會提速？