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