python堆排序算法怎么实现

共计 921 个字符，预计需要花费 3 分钟才能阅读完成。

堆排序算法的实现步骤如下：

1. 构建最大堆（Max Heap）：首先将待排序的序列构建成一个最大堆。从最后一个非叶子节点开始，依次将当前节点与其子节点进行比较，如果当前节点的值小于子节点的值，则将两者交换位置，并继续比较下一个子节点，直到当前节点的值大于或等于其子节点的值。
2. 将堆顶元素与数组末尾元素交换位置：将堆顶元素与数组最后一个元素进行交换。这样，最大的元素就排在了数组的末尾。
3. 重新调整剩余元素，使其满足最大堆的性质：将剩余的元素重新调整为最大堆。重复步骤 1 和步骤 2，直到所有元素都排序完毕。

下面是 Python 代码的实现：

def heapify(arr, n, i):
    largest = i  # 初始化最大元素的索引 
    left = 2 * i + 1  # 左子节点的索引 
    right = 2 * i + 2  # 右子节点的索引 

    # 如果左子节点存在且大于根节点，则将最大元素索引设为左子节点的索引 
    if left < n and arr[i] < arr[left]:
        largest = left

    # 如果右子节点存在且大于当前最大元素，则将最大元素索引设为右子节点的索引 
    if right < n and arr[largest] < arr[right]:
        largest = right

    # 如果最大元素索引发生了变化，则将当前根节点和最大元素交换位置，并继续调整以确保最大堆结构 
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    # 构建最大堆，从最后一个非叶子节点开始 
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 依次将堆顶元素与数组末尾元素交换，并重新调整堆 
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换堆顶元素和尾部元素 
        heapify(arr, i, 0)

    return arr


# 测试 
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heapSort(arr)
print(" 排序结果:", sorted_arr)

输出结果：[5, 6, 7, 11, 12, 13]

丸趣 TV 网 – 提供最优质的资源集合！