Python第五周 学习笔记（2）
def heap_sort(lst:list): '''堆排序
:type lst: list
:rtype: list
'''
length = len(lst)
lst.insert(0,0) # 前插0为了索引和结点号能够对应上，索引不必加一，便于理解，输出时切片即可
def heap_adjust(start, end):
'''
调整当前节点
调整结点的起点在n//2,保证所有调整结点都有孩子结点
:param end: 待比较个数
:param start: 当前节点下标
:rtype: None
'''
while 2 * start <= end: # 如果该结点下还有孩子则进入循环，否则跳出
lchild_index = 2 * start #该结点号*2 为左孩子结点
max_child_index = lchild_index #
if lchild_index < end and lst > lst: # 如果有右孩子并且右孩子比左孩子的数大，则更新最大值索引
max_child_index = lchild_index + 1
if lst > lst: #孩子结点比较完后与父结点比较，最大值放到父结点，并且下一次迭代的父结点是本次最大孩子索引
lst, lst = lst, lst
start = max_child_index
else: # 如果父结点最大则直接跳出，因为排顶堆从编号最大的子树开始调整，即保证了本次最大孩子结点与其孩子结点已经形成了顶堆
break
for st in range(length//2, 0, -1): # 调整为大顶堆
heap_adjust(st, length)
for end in range(length, 1, -1): #sort排序 根结点与最后结点交换，每次迭代刨除最后结点，直至只剩根结点
lst, lst = lst, lst
heap_adjust(1, end - 1)
return lst
页:
[1]