我对这种气泡排序算法使用VBA的速度如此之慢感到惊讶。所以我的问题是我做错了什么/效率低下,或者这仅仅是最好的VBA和冒泡排序吗?例如,可能使用VARIANT,太多变量等会大大降低性能。我知道Bubble Sort并不是特别快,但是我不认为会这么慢。
算法输入:2D数组和一或两列以asc或desc排序。我不一定需要快如闪电,但是5,000行30秒是完全不能接受的
Option Explicit Sub sortA() Dim start_time, end_time start_time = Now() Dim ThisArray() As Variant Dim sheet As Worksheet Dim a, b As Integer Dim rows, cols As Integer Set sheet = ArraySheet rows = 5000 cols = 3 ReDim ThisArray(0 To cols - 1, 0 To rows - 1) For a = 1 To rows For b = 1 To cols ThisArray(b - 1, a - 1) = ArraySheet.Cells(a, b) Next b Next a Call BubbleSort(ThisArray, 0, False, 2, True) end_time = Now() MsgBox (DateDiff("s", start_time, end_time)) End Sub 'Array Must Be: Array(Column,Row) Sub BubbleSort(ThisArray As Variant, SortColumn1 As Integer, Asc1 As Boolean, Optional SortColumn2 As Integer = -1, Optional Asc2 As Boolean) Dim FirstRow As Integer Dim LastRow As Integer Dim FirstCol As Integer Dim LastCol As Integer Dim lTemp As Variant Dim i, j, k As Integer Dim a1, a2, b1, b2 As Variant Dim CompareResult As Boolean FirstRow = LBound(ThisArray, 2) LastRow = UBound(ThisArray, 2) FirstCol = LBound(ThisArray, 1) LastCol = UBound(ThisArray, 1) For i = FirstRow To LastRow For j = i + 1 To LastRow If SortColumn2 = -1 Then 'If there is only one column to sort by a1 = ThisArray(SortColumn1, i) a2 = ThisArray(SortColumn1, j) If Asc1 = True Then CompareResult = compareOne(a1, a2) Else CompareResult = compareOne(a2, a1) End If Else 'If there are two columns to sort by a1 = ThisArray(SortColumn1, i) a2 = ThisArray(SortColumn1, j) b1 = ThisArray(SortColumn2, i) b2 = ThisArray(SortColumn2, j) If Asc1 = True Then If Asc2 = True Then CompareResult = compareTwo(a1, a2, b1, b2) Else CompareResult = compareTwo(a1, a2, b2, b1) End If Else If Asc2 = True Then CompareResult = compareTwo(a2, a1, b1, b2) Else CompareResult = compareTwo(a2, a1, b2, b1) End If End If End If If CompareResult = True Then ' If compare result returns true, Flip rows For k = FirstCol To LastCol lTemp = ThisArray(k, j) ThisArray(k, j) = ThisArray(k, i) ThisArray(k, i) = lTemp Next k End If Next j Next i End Sub Function compareOne(FirstCompare1 As Variant, FirstCompare2 As Variant) As Boolean If FirstCompare1 > FirstCompare2 Then compareOne = True Else compareOne = False End If End Function Function compareTwo(FirstCompare1 As Variant, FirstCompare2 As Variant, SecondCompare1 As Variant, SecondCompare2 As Variant) As Boolean If FirstCompare1 > FirstCompare2 Then compareTwo = True ElseIf FirstCompare1 = FirstCompare2 And SecondCompare1 > SecondCompare2 Then compareTwo = True Else compareTwo = False End If End Function
多谢您的任何帮助或建议!!
编辑:我决定改用QuickSort。如果有兴趣,请参见下面的代码。
首先:不要在5000行上使用冒泡排序!这将需要5000 ^ 2/2次迭代,即12.5B次迭代!最好使用像样的QuickSort算法。在本文的底部,您将找到一个可以用作起点的文章。它仅比较第1列。在我的系统上,花费了0.01秒的排序(而不是优化冒泡排序后的4秒)。
现在,面对挑战,请查看下面的代码。它以原始运行时间的〜30%运行-同时显着减少了代码行。
主要杠杆是:
通过具有两个单独的回路可以进一步优化速度-一个回路用于一列,一个回路用于两列。这样可以将运行时间减少约10%,但会使代码过大,因此省略了代码。
Option Explicit
Sub sortA()
Dim start_time As Double Dim varArray As Variant, dblArray() As Double Dim a, b As Long Const rows As Long = 5000 Const cols As Long = 3 start_time = Timer 'Copy everything to array of type variant varArray = ArraySheet.Range("A1").Resize(rows, cols).Cells 'Cast variant to double ReDim dblArray(1 To rows, 1 To cols) For a = 1 To rows For b = 1 To cols dblArray(a, b) = varArray(a, b) Next b Next a BubbleSort dblArray, 1, False, 2, True MsgBox Format(Timer - start_time, "0.00")
End Sub
‘Array Must Be: Array(Column,Row) Sub BubbleSort(ThisArray() As Double, SortColumn1 As Long, Asc1 As Boolean, Optional SortColumn2 As Long = -1, Optional Asc2 As Boolean)
Dim LastRow As Long Dim FirstCol As Long Dim LastCol As Long Dim lTemp As Double Dim i, j, k As Long Dim CompareResult As Boolean LastRow = UBound(ThisArray, 1) FirstCol = LBound(ThisArray, 2) LastCol = UBound(ThisArray, 2) For i = LBound(ThisArray, 1) To LastRow For j = i + 1 To LastRow If SortColumn2 = -1 Then 'If there is only one column to sort by CompareResult = ThisArray(i, SortColumn1) <= ThisArray(j, SortColumn1) If Asc1 Then CompareResult = Not CompareResult Else 'If there are two columns to sort by Select Case ThisArray(i, SortColumn1) Case Is < ThisArray(j, SortColumn1): CompareResult = Not Asc1 Case Is > ThisArray(j, SortColumn1): CompareResult = Asc1 Case Else CompareResult = ThisArray(i, SortColumn2) <= ThisArray(j, SortColumn2) If Asc2 Then CompareResult = Not CompareResult End Select End If If CompareResult Then ' If compare result returns true, Flip rows For k = FirstCol To LastCol lTemp = ThisArray(j, k) ThisArray(j, k) = ThisArray(i, k) ThisArray(i, k) = lTemp Next k End If Next j Next i
这是一个QuickSort实现:
Public Sub subQuickSort(var1 As Variant, _ Optional ByVal lngLowStart As Long = -1, _ Optional ByVal lngHighStart As Long = -1) Dim varPivot As Variant Dim lngLow As Long Dim lngHigh As Long lngLowStart = IIf(lngLowStart = -1, LBound(var1), lngLowStart) lngHighStart = IIf(lngHighStart = -1, UBound(var1), lngHighStart) lngLow = lngLowStart lngHigh = lngHighStart varPivot = var1((lngLowStart + lngHighStart) \ 2, 1) While (lngLow <= lngHigh) While (var1(lngLow, 1) < varPivot And lngLow < lngHighStart) lngLow = lngLow + 1 Wend While (varPivot < var1(lngHigh, 1) And lngHigh > lngLowStart) lngHigh = lngHigh - 1 Wend If (lngLow <= lngHigh) Then subSwap var1, lngLow, lngHigh lngLow = lngLow + 1 lngHigh = lngHigh - 1 End If Wend If (lngLowStart < lngHigh) Then subQuickSort var1, lngLowStart, lngHigh End If If (lngLow < lngHighStart) Then subQuickSort var1, lngLow, lngHighStart End If End Sub Private Sub subSwap(var As Variant, lngItem1 As Long, lngItem2 As Long) Dim varTemp As Variant varTemp = var(lngItem1, 1) var(lngItem1, 1) = var(lngItem2, 1) var(lngItem2, 1) = varTemp End Sub