我正在尝试在 Python 中实现堆排序，但我似乎无法做到这一点。我试图实现这个伪代码，但我的代码没有排序！它只是筛选到荒谬的效果。我倾向于认为问题出在这一行：
将堆的根（最大值）与堆的最后一个元素交换
如何获得最大值？
这就是我所拥有的：
def my_heap_sort(sqc):
def heapify(count):
start = (count-2)/2
while start >= 0:
sift_down(start, count-1)
start -= 1
def swap(i, j):
sqc[i], sqc[j] = sqc[j], sqc[i]
def sift_down(start, end):
root = start
while (root * 2 + 1) <= end:
child = root * 2 + 1
temp = root
if sqc[temp] < sqc[child]:
temp = child+1
if temp != root:
swap(root, temp)
root = temp
else:
return
count = len(sqc)
heapify(count)
end = count-1
while end > 0:
swap(end, 0)
end -= 1
sift_down(0, end)
我发现了一个几乎相同问题的例子：
def heap_sort_example(a):
def heapify(a):
start = (len(a) - 2) / 2
start -= 1
def sift_down(a, start, end):
root = start
while root * 2 + 1 <= end:
child = root * 2 + 1
if child + 1 <= end and a[child] < a[child+1]:
child += 1
if child <= end and a[root] < a[child]:
a[root], a[child] = a[child], a[root]
root = child
else:
return
heapify(a)
end = len(a) - 1
while end > 0:
a[end], a[0] = a[0], a[end]
sift_down(a, 0, end-1)
end -= 1
结果不同，但两者都很荒谬：
>>> my_heap_sort(sqc)
[2, 7, 1, -2, 56, 5, 3]
>>> heap_sort_example(sqc)
[-2, 1, 7, 2, 56, 5, 3]