算法实现堆排序

堆排序（Heap Sort）是一种效率较高的排序算法，它是利用堆这种数据结构而设计的。堆（Heap）是一个完全二叉树，它分为两种类型：最大堆和最小堆。最大堆的每个节点的值都大于或等于其左右子节点的值，最小堆的每个节点的值都小于或等于其左右子节点的值。堆排序是利用堆这种数据结构而设计的一种排序算法，它的平均时间复杂度为 O(nlogn)。

下面是使用 Python 语言实现的堆排序算法：

def heap_sort(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[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    # 找到最大元素
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    # 如果不是根节点，则交换并继续堆化
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

该算法首先构造一个最大堆，然后进行排序。在构造最大堆时，从最后一个非叶子节点开始向上堆化，直到堆化根节点。在排序时，每次将堆顶元素与最后一个元素交换，并将堆的大小减 1，再从堆顶开始向下堆化，直到堆化大小为 1