1、算法步骤

a. 创建一个堆 H[0……n-1]；

b. 把堆首（最大值）和堆尾互换；

c. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

d. 重复步骤 b，直到堆的尺寸为 1。

2、动图演示

3、代码

# 定义一个函数buildMaxHeap，用于构建最大堆
def buildMaxHeap(arr):
    # 导入math模块
    import math

    # 从最后一个非叶子节点开始，依次向上构建最大堆
    for i in range(math.floor(len(arr) / 2), -1, -1):
        heapify(arr, i)

# 定义一个函数heapify，用于维护最大堆的性质
def heapify(arr, i):
    # 计算左右子节点的索引
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
    # 判断左子节点是否大于当前节点
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    # 判断右子节点是否大于当前节点
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是当前节点，则交换节点，并继续向下调整
    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

# 定义一个函数swap，用于交换数组中两个元素的位置
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

# 定义一个全局变量，用于记录堆的大小
arrLen = 0

# 定义一个函数heapSort，用于堆排序
def heapSort(arr):
    # 全局变量arrLen记录数组的长度
    global arrLen
    arrLen = len(arr)
    # 构建最大堆
    buildMaxHeap(arr)
    # 将堆顶元素与堆尾元素交换，并调整堆结构，直到堆中只剩一个元素
    for i in range(len(arr) - 1, 0, -1):
        swap(arr, 0, i)
        arrLen -= 1
        heapify(arr, 0)
    # 返回排序后的数组
    return arr

打赏 支付宝打赏 微信打赏