Python 堆排序

　　原理

　　堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。

　　步骤

　　创建最大堆:将堆所有数据重新排序，使其成为最大堆

　　最大堆调整:作用是保持最大堆的性质，是创建最大堆的核心子程序

　　堆排序:移除位在第一个数据的根节点，并做最大堆调整的递归运算

　　代码

　　def heap_sort(list):

　　# 创建最大堆

　　for start in range((len(list) - 2) // 2, -1, -1):

　　sift_down(list, start, len(list) - 1)

　　# 堆排序

　　for end in range(len(list) - 1, 0, -1):

　　list[0], list[end] = list[end], list[0]

　　sift_down(list, 0, end - 1)

　　return list

　　# 最大堆调整

　　def sift_down(lst, start, end):

　　root = start

　　while True:

　　child = 2 * root + 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

　　以上内容为大家介绍了Python 堆排序，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注多测师。https://www.e70w.com/xwzx/