# 参考链接;https://blog.csdn.net/qq_34840129/article/details/80638225
# 参考链接;https://cuijiahua.com/blog/2018/01/alogrithm_9.html
# 参考链接:https://www.jianshu.com/p/d6ba8c43cbc1
def heap_sort(alist):
def siftdown(elems, e, begin, end): # 向下筛选
i, j = begin, begin * 2 + 1 # j为i的左子结点
while j < end:
if j + 1 < end and elems[j] > elems[j + 1]: # 如果左子结点大于右子结点
j += 1 # 则将j指向右子结点
if e < elems[j]: # j已经指向两个子结点中较小的位置，
break # 如果插入元素e小于j位置的值，则为3者中最小的
elems[i] = elems[j] # 能执行到这一步的话，说明j位置元素是三者中最小的，则将其上移到父结点位置
i, j = j, j * 2 + 1 # 更新i为被上移为父结点的原来的j的位置，更新j为更新后i位置的左子结点
elems[i] = e # 如果e已经是某个子树3者中最小的元素，则将其赋给这个子树的父结点
# 或者位置i已经更新到叶结点位置，则将e赋给这个叶结点。
end = len(alist)
for i in range(end // 2 - 1, -1, -1): # 构造堆序。
siftdown(alist, alist[i], i, end)
for i in range((end - 1), 0, -1): # 进行堆排序.i最后一个值为1，不需要到0
# print(elems)
e = alist[i] # 将末尾元素赋给e
alist[i] = alist[0] # 交换堆顶与最后一个元素
siftdown(alist, e, 0, i)
return alist
if __name__ == "__main__":
alist = [5, 6, 8, 1, 2, 4, 9, 9, 18]
print(alist)
heap_sort(alist)
print(alist)
待后续整理........
