小编点评

**博客地址：**https://www.cnblogs.com/zylyehuo/# _*_coding:utf-8_*_import randomdef sift(li, low, high): # 堆的向下调整（大根堆） \"\"\" :param li: 列表 :param low: 堆的根节点位置 :param high: 堆的最后一个元素的位置 :return: \"\"\" i = low # i最开始指向根节点 j = 2 * i + 1 # j开始是左孩子 tmp = li[low] # 把堆顶存起来 while j <= high: # 只要j位置有数 if j + 1 <= high and li[j + 1] > li[j]: # 如果右孩子有并且比较大 j = j + 1 # j指向右孩子 if li[j] > tmp: li[i] = li[j] i = j # 往下看一层 j = 2 * i + 1 else: # tmp更大，把tmp放到i的位置上 li[i] = tmp # 把tmp放到某一级领导位置上 break else: li[i] = tmp # 把tmp放到叶子节点上 **摘要：** 博客文章介绍了堆排序的算法，其中包括堆的向下调整（大根堆）的实现。 * **堆的向下调整**是一种排序算法，它通过不断地从堆顶元素中提取最大（或最小）元素来构建一个排序好的列表。 * **堆**是一种双向链表，其中每个节点表示一个元素。 * **堆的向下调整**的算法在每次迭代中，从堆顶元素开始，直到找到最大（或最小）元素。 * 在每次迭代中，如果右孩子存在且其元素大于左孩子，则将右孩子的元素替换于左孩子的元素。 * 如果右孩子的元素大于左孩子的元素，则将右孩子的元素放到左孩子的所在位置。 * 最后，排序后的列表将从堆顶元素开始，依次向下直到叶子节点。

正文

博客地址：https://www.cnblogs.com/zylyehuo/

# _*_coding:utf-8_*_

import random


def sift(li, low, high):  # 堆的向下调整（大根堆）
    """
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    """

    i = low  # i最开始指向根节点
    j = 2 * i + 1  # j开始是左孩子
    tmp = li[low]  # 把堆顶存起来
    while j <= high:  # 只要j位置有数
        if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子有并且比较大
            j = j + 1  # j指向右孩子
        if li[j] > tmp:
            li[i] = li[j]
            i = j  # 往下看一层
            j = 2 * i + 1
        else:  # tmp更大，把tmp放到i的位置上
            li[i] = tmp  # 把tmp放到某一级领导位置上
            break
    else:
        li[i] = tmp  # 把tmp放到叶子节点上


def heap_sort(li):
    n = len(li)
    for i in range((n - 2) // 2, -1, -1):
        # i表示建堆的时候调整的部分的根的下标
        sift(li, i, n - 1)
    # 建堆完成了
    for i in range(n - 1, -1, -1):
        # i 指向当前堆的最后一个元素
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)  # i-1是新的high


ls = [i for i in range(10)]

random.shuffle(ls)
print(ls)

heap_sort(ls)
print(ls)

复制