借鉴菜鸟教程和维基百科,懵逼来懵逼去,总算搞明白了。

def heap_sort(lst):
    def sift_down(start, end):
        """最大堆调整
        start 是调整的节点的在数组中的下标
        end   是结束的下标
        """
        root = start
        while True:
            l_child = 2 * root + 1  # 左孩子在数组中的下标
            if l_child > end:
                break
            # 节点的右孩子存在 且 右孩子大于左孩子
            if l_child + 1 <= end and lst[l_child] < lst[l_child + 1]:
                l_child += 1
            # 如果父节点 小于 其左孩子
            if lst[root] < lst[l_child]:
                lst[root], lst[l_child] = lst[l_child], lst[root]

                # 交换之后以交换子节点为根的堆可能不是大定堆
                root = l_child
            else:  # 如果父节点大于左右孩子节点
                break

# 创建最大堆
    # 计算最后一个有孩子的节点在原始数组中的下标
    last_have_child_item_index = len(lst) // 2 - 1
    for start in range(last_have_child_item_index, -1, -1): # 从最后一个有孩子的节点往上调整(每个节点都要调整)
        print(lst , f"start {start} end {len(lst)-1}")
        sift_down(start, len(lst) - 1)

    print("数据堆初始化后: ", lst)

# 堆排序
    # 最大堆中,最大值总是根节点
    for end in range(len(lst) - 1, 0, -1):
        lst[0], lst[end] = lst[end], lst[0]  # 交换根和尾
        sift_down(0, end - 1) # 堆调整,且堆长度减1
    return lst


if __name__ == "__main__":
    l = [9, 2, 1, 7, 6, 18, 5, 3, 4, 8]
    data = heap_sort(l)
    print(data)

results matching ""

    No results matching ""

    results matching ""

      No results matching ""