algorithm - 堆排序算法错误

Question

我正在尝试编写堆排序算法，这是我的代码。但是，它不起作用。当我尝试运行宏时，它说下标超出范围，它对应于 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