Python堆排序对数组进行堆排序

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

Python堆排序的基本操作步骤如下：

1.构建大顶堆：

# 将列表a中的数据，构造成大顶堆
def heapify(a, n, i):
    largest = i  # 初始化最大值
    l = 2 * i + 1  # 左孩子结点的位置
    r = 2 * i + 2  # 右孩子结点的位置

    # 如果左孩子大于父节点，将最大指针指向左孩子
    if l < n and a[l] > a[largest]:
        largest = l

    # 如果右孩子大于父节点，将最大指针指向右孩子
    if r < n and a[r] > a[largest]:
        largest = r

    # 如果最大值不是父节点，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        heapify(a, n, largest)

2.将堆顶元素与末尾元素进行交换：

# 将堆顶元素与末尾元素进行交换
def swap(a, i, j):
    a[i], a[j] = a[j], a[i]

3.堆排序：

# 堆排序
def heap_sort(a):
    n = len(a)
    # 构建初始堆，从第一个非叶子结点开始
    for i in range(n // 2 - 1, -1, -1):
        heapify(a, n, i)

    # 将堆顶元素与末尾元素进行交换，并且重新调整堆
    for i in range(n - 1, 0, -1):
        swap(a, 0, i)
        heapify(a, i, 0)

4.使用示例：

# 示例
if __name__ == '__main__':
    a = [3, 5, 2, 1, 4]
    print('排序前:', a)
    heap_sort(a)
    print('排序后:', a)

5.输出结果：

# 输出结果
排序前: [3, 5, 2, 1, 4]
排序后: [1, 2, 3, 4, 5]