堆排序 python

堆排序（Heap Sort）是一种树形选择排序的方法，是对直接选择排序的有效改进。

堆排序的基本思想是将待排序序列构造成一个大顶堆（或小顶堆），此时整个序列的最大值（或最小值）就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值（或最小值），然后将剩余的n-1个元素重新构造成一个堆，这样就会得到n个元素的次小值。如此反复执行，便能得到一个有序序列。

以下是 Python 代码实现堆排序：

def heapify(arr, n, i):
    largest = i  # 初始化最大元素的下标为父节点i
    l = 2 * i + 1  # 左子节点的下标
    r = 2 * i + 2  # 右子节点的下标

    # 如果左子节点存在且大于父节点，则更新最大元素下标
    if l < n and arr[i] < arr[l]:
        largest = l

    # 如果右子节点存在且大于父节点和左子节点，则更新最大元素下标
    if r < n and arr[largest] < arr[r]:
        largest = r

    # 如果最大元素不是父节点，则交换父节点和最大元素
    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, -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

调用 `heapSort(arr)` 即可对数组 `arr` 进行堆排序。