heapsort算法錯誤

Question

我正在嘗試編寫一個heapsort算法，這是我的代碼。但是，它不起作用。當我嘗試運行宏時，它表示下標超出範圍，它對應於if A(leftchild,1) > A(i,1) then位。它說i和leftchild都等於零，但情況並非如此，但我不知道要在哪裏更改它。

Sub MakeMaxHeap(i As Long, heapsize As Long) 
    Dim LeftChild As Long 
    Dim RightChild As Long 
    Dim largest As Long 

    LeftChild = 2 * i 
    RightChild = 2 * i + 1 

    If heapsize > LeftChild Then 
     If A(LeftChild, 1) > A(i, 1) Then 
      largest = LeftChild 
     ElseIf A(LeftChild, 1) = A(i, 1) Then 
      largest = i 
     End If 
    End If 

    If heapsize > RightChild Then 
     If A(RightChild, 1) > A(largest, 1) Then 
      largest = RightChild 
     ElseIf A(RightChild, 1) = A(largest, 1) Then 
      largest = i 
     End If 
    End If 

    If largest <> i Then 
     Call MakeMaxHeap(largest, heapsize) 
    End If 

End Sub 

Sub BuildMaxHeap() 
    Dim i As Long 
    Dim heapsize As Long 
    heapsize = n 

    For i = n/2 To 1 Step -1 
     Call MakeMaxHeap(i, heapsize) 
    Next i 

End Sub 


Sub HeapSort() 
    Dim i As Long 
    Dim temp As Double 
    Dim j As Long 
    Dim heapsize As Long 

    Call InitializeA 
    'This basically stores a 
    Call BuildMaxHeap 
    heapsize = n 
    For i = n To 2 Step -1 
     temp = A(i, 1) 
     A(i, 1) = A(1, 1) 
     A(1, 1) = temp 
     heapsize = heapsize - 1 
     Call MakeMaxHeap(1, heapsize) 
    Next i 

    For j = 1 To n 
     Cells(j, 7).Value = A(j, 1) 
    Next j 
End Sub 

Answer 1

的MakeMaxHeap過程有幾個問題：

• 在一些點，可變largest將永遠不會得到一個值，因爲這兩個If條件可能是False。如果發生這種情況，遞歸調用的第一個參數是0，導致運行時錯誤。

• 儘管進行了比較和遞歸調用，MakeMaxHeap實際上不會更改任何數組。值應該交換，使其成爲最大的堆。

這裏是MakeMaxHeap與評論更正後的代碼在那裏進行了更改：

Sub MakeMaxHeap(i As Long, heapsize As Long) 
    Dim LeftChild As Long 
    Dim RightChild As Long 
    Dim largest As Long 
    Dim temp As Long ' *** Added 

    LeftChild = 2 * i 
    RightChild = 2 * i + 1 

    ' *** Give the variable an initial value, as both If conditions might be false 
    largest = i 
    ' *** Use >= instead of > 
    If heapsize >= LeftChild Then 
     If A(LeftChild, 1) > A(i, 1) Then 
      largest = LeftChild 
     ' *** ElseIf is not needed 
     End If 
    End If 

    ' *** Use >= instead of > 
    If heapsize >= RightChild Then 
     If A(RightChild, 1) > A(largest, 1) Then 
      largest = RightChild 
     ' *** ElseIf is not needed 
     End If 
    End If 

    If largest <> i Then 
     ' *** You need to actually swap the values 
     temp = A(i, 1) 
     A(i, 1) = A(largest, 1) 
     A(largest, 1) = temp 
     Call MakeMaxHeap(largest, heapsize) 
    End If  
End Sub