Python第五周 学习笔记（2）

loyalxuan

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[lchild_index + 1] > lst[lchild_index]: # 如果有右孩子并且右孩子比左孩子的数大，则更新最大值索引
　　max_child_index = lchild_index + 1
　　if lst[max_child_index] > lst[start]: #孩子结点比较完后与父结点比较，最大值放到父结点，并且下一次迭代的父结点是本次最大孩子索引
　　lst[start], lst[max_child_index] = lst[max_child_index], lst[start]
　　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[1], lst[end] = lst[end], lst[1]
　　heap_adjust(1, end - 1)
　　return lst[1:]