Board logo

標題: [原創] 快速插入排序 [打印本頁]
作者: linyancheng    時間: 2017-2-19 19:44     標題: 快速插入排序

排序陣列：10000 x 2 的整數（但我的引數代碼是Variant）
（重複數字大概在5~20個之間）
執行100次秒數總合：

一維重複順序（非穩）        3.296
一維重複逆序（非穩）        3.641
一維重複亂序（非穩）        5.499
一維不重複順序（非穩）        2.814
一維不重複逆序（非穩）        3.166
一維不重複亂序（非穩）        6.153
一維重複順序（穩定）        4.687
一維重複逆序（穩定）        4.876
一維重複亂序（穩定）        5.479
一維不重複順序（穩定）        6.56
一維不重複逆序（穩定）        8.148
一維不重複亂序（穩定）        9.1
二維重複順序（穩定）        5.176
二維重複逆序（穩定）        5.517
二維重複亂序（穩定）        5.89
二維不重複順序（穩定）        7.598
二維不重複逆序（穩定）        9.238
二維不重複亂序（穩定）        9.462
  1. Option Explicit
  2. Option Base 1
  3. Option Compare Text

  5. Public Sub S_一維陣列快速插入排序_01(ByRef 原始一維陣列 As Variant, ByVal 起限 As Long, ByVal 迄限 As Long, ByVal 遞增或遞減 As String)

  7.     On Error Resume Next
  8.    
  9.     If 起限 >= 迄限 Then
  10.         Exit Sub
  11.     End If
  12.    
  13.     '------------------------------------------------------
  14.    
  15.     Select Case 遞增或遞減
  16.         Case "遞增"
  17.             一維陣列快速插入遞增排序 原始一維陣列, 起限, 迄限
  18.         Case "遞減"
  19.             一維陣列快速插入遞減排序 原始一維陣列, 起限, 迄限
  20.     End Select

  22. End Sub

  24. Public Sub 一維陣列快速插入遞增排序(ByRef 原始一維陣列 As Variant, ByVal 起限 As Long, ByVal 迄限 As Long)

  26.     On Error Resume Next
  27.    
  28.     If 起限 >= 迄限 Then
  29.         Exit Sub
  30.     End If
  31.    
  32.     '------------------------------------------------------
  33.    
  34.     Dim X As Long
  35.     Dim Y As Long
  36.     Dim S As Long
  37.     Dim E As Long
  38.    
  39.     Dim 暫存 As Variant
  40.     Dim 基準 As Variant
  41.    
  42.     '------------------------------------------------------
  43.    
  44.     If 迄限 - 起限 < 16 Then
  45.         For X = 起限 + 1 To 迄限
  46.             暫存 = 原始一維陣列(X)
  47.             
  48.             For Y = X - 1 To 起限 Step -1
  49.                 If 暫存 >= 原始一維陣列(Y) Then
  50.                     Exit For
  51.                 End If
  52.                
  53.                 原始一維陣列(Y + 1) = 原始一維陣列(Y)
  54.             Next Y
  55.             
  56.             原始一維陣列(Y + 1) = 暫存
  57.         Next X
  58.     Else
  59.         Dim 基準陣列(3) As Variant
  60.         
  61.         基準陣列(1) = 原始一維陣列(起限)
  62.         基準陣列(2) = 原始一維陣列((起限 + 迄限) \ 2)
  63.         基準陣列(3) = 原始一維陣列(迄限)
  64.         
  65.         For X = 2 To 3
  66.             暫存 = 基準陣列(X)
  67.             
  68.             For Y = X - 1 To 1 Step -1
  69.                 If 暫存 >= 基準陣列(Y) Then
  70.                     Exit For
  71.                 End If
  72.                
  73.                 基準陣列(Y + 1) = 基準陣列(Y)
  74.             Next Y
  75.             
  76.             基準陣列(Y + 1) = 暫存
  77.         Next X
  78.         
  79.         基準 = 基準陣列(2)
  80.         
  81.         '------------------------------------------------------
  82.         
  83.         S = 起限 - 1
  84.         E = 迄限 + 1
  85.         Do
  86.             Do
  87.                 S = S + 1
  88.                
  89.                 If 原始一維陣列(S) >= 基準 Then
  90.                     Exit Do
  91.                 End If
  92.             Loop
  93.             
  94.             Do
  95.                 E = E - 1
  96.                
  97.                 If 原始一維陣列(E) <= 基準 Then
  98.                     Exit Do
  99.                 End If
  100.             Loop
  101.             
  102.             If E <= S Then
  103.                 Exit Do
  104.             End If
  105.             
  106.             暫存 = 原始一維陣列(S)
  107.             原始一維陣列(S) = 原始一維陣列(E)
  108.             原始一維陣列(E) = 暫存
  109.         Loop
  110.         
  111.         '------------------------------------------------------
  112.         
  113.         If 起限 < E And E < 迄限 Then
  114.             一維陣列快速插入遞增排序 原始一維陣列, 起限, E
  115.         End If
  116.         
  117.         If 起限 < S And S < 迄限 Then
  118.             一維陣列快速插入遞增排序 原始一維陣列, S, 迄限
  119.         End If
  120.     End If

  122. End Sub

  124. Public Sub 一維陣列快速插入遞減排序(ByRef 原始一維陣列 As Variant, ByVal 起限 As Long, ByVal 迄限 As Long)

  126.     On Error Resume Next
  127.    
  128.     If 起限 >= 迄限 Then
  129.         Exit Sub
  130.     End If
  131.    
  132.     '------------------------------------------------------
  133.    
  134.     Dim X As Long
  135.     Dim Y As Long
  136.     Dim S As Long
  137.     Dim E As Long
  138.    
  139.     Dim 暫存 As Variant
  140.     Dim 基準 As Variant
  141.    
  142.     '------------------------------------------------------
  143.    
  144.     If 迄限 - 起限 < 16 Then
  145.         For X = 起限 + 1 To 迄限
  146.             暫存 = 原始一維陣列(X)
  147.             
  148.             For Y = X - 1 To 起限 Step -1
  149.                 If 暫存 <= 原始一維陣列(Y) Then
  150.                     Exit For
  151.                 End If
  152.                
  153.                 原始一維陣列(Y + 1) = 原始一維陣列(Y)
  154.             Next Y
  155.             
  156.             原始一維陣列(Y + 1) = 暫存
  157.         Next X
  158.     Else
  159.         Dim 基準陣列(3) As Variant
  160.         
  161.         基準陣列(1) = 原始一維陣列(起限)
  162.         基準陣列(2) = 原始一維陣列((起限 + 迄限) \ 2)
  163.         基準陣列(3) = 原始一維陣列(迄限)
  164.         
  165.         For X = 2 To 3
  166.             暫存 = 基準陣列(X)
  167.             
  168.             For Y = X - 1 To 1 Step -1
  169.                 If 暫存 >= 基準陣列(Y) Then
  170.                     Exit For
  171.                 End If
  172.                
  173.                 基準陣列(Y + 1) = 基準陣列(Y)
  174.             Next Y
  175.             
  176.             基準陣列(Y + 1) = 暫存
  177.         Next X
  178.         
  179.         基準 = 基準陣列(2)
  180.         
  181.         '------------------------------------------------------
  182.         
  183.         S = 起限 - 1
  184.         E = 迄限 + 1
  185.         Do
  186.             Do
  187.                 S = S + 1
  188.                
  189.                 If 原始一維陣列(S) <= 基準 Then
  190.                     Exit Do
  191.                 End If
  192.             Loop
  193.             
  194.             Do
  195.                 E = E - 1
  196.                
  197.                 If 原始一維陣列(E) >= 基準 Then
  198.                     Exit Do
  199.                 End If
  200.             Loop
  201.             
  202.             If E <= S Then
  203.                 Exit Do
  204.             End If
  205.             
  206.             暫存 = 原始一維陣列(S)
  207.             原始一維陣列(S) = 原始一維陣列(E)
  208.             原始一維陣列(E) = 暫存
  209.         Loop
  210.         
  211.         '------------------------------------------------------
  212.         
  213.         If 起限 < E And E < 迄限 Then
  214.             一維陣列快速插入遞減排序 原始一維陣列, 起限, E
  215.         End If
  216.         
  217.         If 起限 < S And S < 迄限 Then
  218.             一維陣列快速插入遞減排序 原始一維陣列, S, 迄限
  219.         End If
  220.     End If

  222. End Sub
複製代碼
作者: linyancheng    時間: 2017-2-19 19:51

  1. Option Explicit
  2. Option Base 1
  3. Option Compare Text

  5. Public Sub S_一維陣列快速插入穩定排序_01(ByRef 原始一維陣列 As Variant, ByVal 起限 As Long, ByVal 迄限 As Long, ByVal 遞增或遞減 As String)

  7.     On Error Resume Next
  8.    
  9.     If 起限 >= 迄限 Then
  10.         Exit Sub
  11.     End If
  12.    
  13.     '------------------------------------------------------
  14.    
  15.     Dim X As Long
  16.    
  17.     Dim 索引陣列() As Long
  18.    
  19.     '------------------------------------------------------
  20.    
  21.     ReDim 索引陣列(起限 To 迄限) As Long
  22.    
  23.     For X = 起限 To 迄限
  24.         索引陣列(X) = X
  25.     Next X
  26.    
  27.     '------------------------------------------------------
  28.    
  29.     Select Case 遞增或遞減
  30.         Case "遞增"
  31.             一維陣列快速插入穩定遞增排序 原始一維陣列, 索引陣列, 起限, 迄限
  32.         Case "遞減"
  33.             一維陣列快速插入穩定遞減排序 原始一維陣列, 索引陣列, 起限, 迄限
  34.     End Select
  35.    
  36.     '------------------------------------------------------
  37.    
  38.     Dim 複製原始一維陣列 As Variant
  39.    
  40.     複製原始一維陣列 = 原始一維陣列
  41.    
  42.     For X = 起限 To 迄限
  43.         原始一維陣列(X) = 複製原始一維陣列(索引陣列(X))
  44.     Next X

  46. End Sub

  48. Public Sub S_二維陣列快速插入穩定排序_01(ByRef 原始二維陣列 As Variant, ByVal 排序維度 As Long, ByVal 排序鍵值 As Long, ByVal 起限 As Long, ByVal 迄限 As Long, ByVal 遞增或遞減 As String)

  50.     On Error Resume Next
  51.    
  52.     If 起限 >= 迄限 Then
  53.         Exit Sub
  54.     End If
  55.    
  56.     '------------------------------------------------------
  57.    
  58.     Dim X As Long
  59.     Dim Y As Long
  60.    
  61.     Dim 擷取成一維陣列 As Variant
  62.     Dim 索引陣列() As Long
  63.    
  64.     '------------------------------------------------------
  65.    
  66.     ReDim 擷取成一維陣列(起限 To 迄限) As Variant
  67.     ReDim 索引陣列(起限 To 迄限) As Long
  68.    
  69.     If 排序維度 = 1 Then
  70.         For X = 起限 To 迄限
  71.             擷取成一維陣列(X) = 原始二維陣列(X, 排序鍵值)
  72.             索引陣列(X) = X
  73.         Next X
  74.     Else
  75.         For Y = 起限 To 迄限
  76.             擷取成一維陣列(Y) = 原始二維陣列(排序鍵值, Y)
  77.             索引陣列(Y) = Y
  78.         Next Y
  79.     End If
  80.    
  81.     '------------------------------------------------------
  82.    
  83.     Select Case 遞增或遞減
  84.         Case "遞增"
  85.             一維陣列快速插入穩定遞增排序 擷取成一維陣列, 索引陣列, 起限, 迄限
  86.         Case "遞減"
  87.             一維陣列快速插入穩定遞減排序 擷取成一維陣列, 索引陣列, 起限, 迄限
  88.     End Select
  89.    
  90.     '------------------------------------------------------
  91.    
  92.     Dim 複製原始二維陣列 As Variant
  93.    
  94.     複製原始二維陣列 = 原始二維陣列
  95.    
  96.     If 排序維度 = 1 Then
  97.         For X = 起限 To 迄限
  98.             For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
  99.                 原始二維陣列(X, Y) = 複製原始二維陣列(索引陣列(X), Y)
  100.             Next Y
  101.         Next X
  102.     Else
  103.         For Y = 起限 To 迄限
  104.             For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
  105.                 原始二維陣列(X, Y) = 複製原始二維陣列(X, 索引陣列(Y))
  106.             Next X
  107.         Next Y
  108.     End If

  110. End Sub
複製代碼
作者: linyancheng    時間: 2017-2-19 19:51

  1. Public Sub 一維陣列快速插入穩定遞增排序(ByRef 原始一維陣列 As Variant, ByRef 索引陣列() As Long, ByVal 起限 As Long, ByVal 迄限 As Long)

  3.     On Error Resume Next
  4.    
  5.     If 起限 >= 迄限 Then
  6.         Exit Sub
  7.     End If
  8.    
  9.     '------------------------------------------------------
  10.    
  11.     Dim X As Long
  12.     Dim Y As Long
  13.     Dim S As Long
  14.     Dim M As Long
  15.     Dim E As Long
  16.     Dim N As Long
  17.    
  18.     Dim 暫存 As Variant
  19.     Dim 索引暫存 As Long
  20.    
  21.     '------------------------------------------------------
  22.    
  23.     If 迄限 - 起限 < 16 Then
  24.         Dim 還原陣列 As Variant
  25.         
  26.         ReDim 還原陣列(起限 To 迄限) As Variant
  27.         
  28.         For X = 起限 To 迄限
  29.             還原陣列(X) = 原始一維陣列(索引陣列(X))
  30.         Next X
  31.         
  32.         For X = 起限 + 1 To 迄限
  33.             暫存 = 還原陣列(X)
  34.             索引暫存 = 索引陣列(X)
  35.             
  36.             For Y = X - 1 To 起限 Step -1
  37.                 If 暫存 >= 還原陣列(Y) Then
  38.                     Exit For
  39.                 End If
  40.                
  41.                 還原陣列(Y + 1) = 還原陣列(Y)
  42.                 索引陣列(Y + 1) = 索引陣列(Y)
  43.             Next Y
  44.             
  45.             還原陣列(Y + 1) = 暫存
  46.             索引陣列(Y + 1) = 索引暫存
  47.         Next X
  48.     Else
  49.         Dim 基準 As Variant
  50.         Dim 基準陣列(3) As Variant
  51.         
  52.         基準陣列(1) = 原始一維陣列(索引陣列(起限))
  53.         基準陣列(2) = 原始一維陣列(索引陣列((起限 + 迄限) \ 2))
  54.         基準陣列(3) = 原始一維陣列(索引陣列(迄限))
  55.         
  56.         For X = 2 To 3
  57.             暫存 = 基準陣列(X)
  58.             
  59.             For Y = X - 1 To 1 Step -1
  60.                 If 暫存 >= 基準陣列(Y) Then
  61.                     Exit For
  62.                 End If
  63.                
  64.                 基準陣列(Y + 1) = 基準陣列(Y)
  65.             Next Y
  66.             
  67.             基準陣列(Y + 1) = 暫存
  68.         Next X
  69.         
  70.         基準 = 基準陣列(2)
  71.         
  72.         '------------------------------------------------------
  73.         
  74.         Dim 索引起陣列() As Long
  75.         Dim 索引基陣列() As Long
  76.         Dim 索引迄陣列() As Long
  77.         
  78.         ReDim 索引起陣列(迄限 - 起限) As Long
  79.         ReDim 索引基陣列(迄限 - 起限 + 1) As Long
  80.         ReDim 索引迄陣列(迄限 - 起限) As Long
  81.         
  82.         S = 0
  83.         M = 0
  84.         E = 0
  85.         For X = 起限 To 迄限
  86.             索引暫存 = 索引陣列(X)
  87.             暫存 = 原始一維陣列(索引暫存)
  88.             
  89.             If 暫存 = 基準 Then
  90.                 M = M + 1
  91.                 索引基陣列(M) = 索引暫存
  92.             ElseIf 暫存 < 基準 Then
  93.                 S = S + 1
  94.                 索引起陣列(S) = 索引暫存
  95.             Else
  96.                 E = E + 1
  97.                 索引迄陣列(E) = 索引暫存
  98.             End If
  99.         Next X
  100.         
  101.         '------------------------------------------------------
  102.         
  103.         If S > 1 Then
  104.             一維陣列快速插入穩定遞增排序 原始一維陣列, 索引起陣列, 1, S
  105.         End If
  106.         
  107.         If E > 1 Then
  108.             一維陣列快速插入穩定遞增排序 原始一維陣列, 索引迄陣列, 1, E
  109.         End If
  110.         
  111.         '------------------------------------------------------
  112.         
  113.         N = 起限 - 1
  114.         For X = 1 To S
  115.             N = N + 1
  116.             索引陣列(N) = 索引起陣列(X)
  117.         Next X
  118.         
  119.         For X = 1 To M
  120.             N = N + 1
  121.             索引陣列(N) = 索引基陣列(X)
  122.         Next X
  123.         
  124.         For X = 1 To E
  125.             N = N + 1
  126.             索引陣列(N) = 索引迄陣列(X)
  127.         Next X
  128.     End If

  130. End Sub

  132. Public Sub 一維陣列快速插入穩定遞減排序(ByRef 原始一維陣列 As Variant, ByRef 索引陣列() As Long, ByVal 起限 As Long, ByVal 迄限 As Long)

  134.     On Error Resume Next
  135.    
  136.     If 起限 >= 迄限 Then
  137.         Exit Sub
  138.     End If
  139.    
  140.     '------------------------------------------------------
  141.    
  142.     Dim X As Long
  143.     Dim Y As Long
  144.     Dim S As Long
  145.     Dim M As Long
  146.     Dim E As Long
  147.     Dim N As Long
  148.    
  149.     Dim 暫存 As Variant
  150.     Dim 索引暫存 As Long
  151.    
  152.     '------------------------------------------------------
  153.    
  154.     If 迄限 - 起限 < 16 Then
  155.         Dim 還原陣列 As Variant
  156.         
  157.         ReDim 還原陣列(起限 To 迄限) As Variant
  158.         
  159.         For X = 起限 To 迄限
  160.             還原陣列(X) = 原始一維陣列(索引陣列(X))
  161.         Next X
  162.         
  163.         For X = 起限 + 1 To 迄限
  164.             暫存 = 還原陣列(X)
  165.             索引暫存 = 索引陣列(X)
  166.             
  167.             For Y = X - 1 To 起限 Step -1
  168.                 If 暫存 <= 還原陣列(Y) Then
  169.                     Exit For
  170.                 End If
  171.                
  172.                 還原陣列(Y + 1) = 還原陣列(Y)
  173.                 索引陣列(Y + 1) = 索引陣列(Y)
  174.             Next Y
  175.             
  176.             還原陣列(Y + 1) = 暫存
  177.             索引陣列(Y + 1) = 索引暫存
  178.         Next X
  179.     Else
  180.         Dim 基準 As Variant
  181.         Dim 基準陣列(3) As Variant
  182.         
  183.         基準陣列(1) = 原始一維陣列(索引陣列(起限))
  184.         基準陣列(2) = 原始一維陣列(索引陣列((起限 + 迄限) \ 2))
  185.         基準陣列(3) = 原始一維陣列(索引陣列(迄限))
  186.         
  187.         For X = 2 To 3
  188.             暫存 = 基準陣列(X)
  189.             
  190.             For Y = X - 1 To 1 Step -1
  191.                 If 暫存 >= 基準陣列(Y) Then
  192.                     Exit For
  193.                 End If
  194.                
  195.                 基準陣列(Y + 1) = 基準陣列(Y)
  196.             Next Y
  197.             
  198.             基準陣列(Y + 1) = 暫存
  199.         Next X
  200.         
  201.         基準 = 基準陣列(2)
  202.         
  203.         '------------------------------------------------------
  204.         
  205.         Dim 索引起陣列() As Long
  206.         Dim 索引基陣列() As Long
  207.         Dim 索引迄陣列() As Long
  208.         
  209.         ReDim 索引起陣列(迄限 - 起限) As Long
  210.         ReDim 索引基陣列(迄限 - 起限 + 1) As Long
  211.         ReDim 索引迄陣列(迄限 - 起限) As Long
  212.         
  213.         S = 0
  214.         M = 0
  215.         E = 0
  216.         For X = 起限 To 迄限
  217.             索引暫存 = 索引陣列(X)
  218.             暫存 = 原始一維陣列(索引暫存)
  219.             
  220.             If 暫存 = 基準 Then
  221.                 M = M + 1
  222.                 索引基陣列(M) = 索引暫存
  223.             ElseIf 暫存 > 基準 Then
  224.                 S = S + 1
  225.                 索引起陣列(S) = 索引暫存
  226.             Else
  227.                 E = E + 1
  228.                 索引迄陣列(E) = 索引暫存
  229.             End If
  230.         Next X
  231.         
  232.         '------------------------------------------------------
  233.         
  234.         If S > 1 Then
  235.             一維陣列快速插入穩定遞減排序 原始一維陣列, 索引起陣列, 1, S
  236.         End If
  237.         
  238.         If E > 1 Then
  239.             一維陣列快速插入穩定遞減排序 原始一維陣列, 索引迄陣列, 1, E
  240.         End If
  241.         
  242.         '------------------------------------------------------
  243.         
  244.         N = 起限 - 1
  245.         For X = 1 To S
  246.             N = N + 1
  247.             索引陣列(N) = 索引起陣列(X)
  248.         Next X
  249.         
  250.         For X = 1 To M
  251.             N = N + 1
  252.             索引陣列(N) = 索引基陣列(X)
  253.         Next X
  254.         
  255.         For X = 1 To E
  256.             N = N + 1
  257.             索引陣列(N) = 索引迄陣列(X)
  258.         Next X
  259.     End If

  261. End Sub
複製代碼




歡迎光臨 麻辣家族討論版版 (http://forum.twbts.com/)