返回列表 上一主題 發帖

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

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

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

本帖最後由 jackyq 於 2017-2-12 22:23 編輯

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

TOP

本帖最後由 linyancheng 於 2017-2-12 22:49 編輯

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

而且你有測試過嗎?真有10倍速,懷疑!

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

TOP

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

TOP

夠用就好

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

TOP

本帖最後由 linyancheng 於 2017-2-13 01:39 編輯

回復 5# jackyq


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

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

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

TOP

我的代碼,可幫忙優化嗎?謝謝!

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

TOP

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

TOP

回復 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很耗時,此例可以不用嗎?當然次數或許不多,但也不少。

TOP

回復 8# jackyq


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

TOP

        靜思自在 : 要用心,不要操心、煩心。
返回列表 上一主題