1.堆排序介紹
構建大頂堆或者小頂堆（大頂堆用于升序龙助，小頂堆用于降序）
交換最后一個葉子結點和根結點
調整根結點戳气，使無序區(qū)重新變成大頂堆
2. 代碼實現
def big_endian(lst, start, end):
root = start
while True:
child = root * 2 + 1
if child > end:
break
if child + 1 <= end and lst[child] < lst[child + 1]:
child += 1
if lst[root] < lst[child]:
lst[root], lst[child] = lst[child], lst[root]
root = child
else:
break
def heap_sort(lst):
first = len(lst) // 2 - 1
for start in range(first, -1, -1):
big_endian(lst, start, len(lst) - 1)
for end in range(len(lst) - 1, 0, -1):
lst[0], lst[end] = lst[end], lst[0]
big_endian(lst, 0, end - 1)
if __name__ == "__main__":
l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
print(l)
heap_sort(l)
print(l)
# 運行結果
[3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
