14.排序算法(5)
2021-02-28 本文已影响0人
Stone_説
1.堆排序介绍
构建大顶堆或者小顶堆(大顶堆用于升序,小顶堆用于降序)
交换最后一个叶子结点和根结点
调整根结点,使无序区重新变成大顶堆
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]