python 实现堆排序算法代码

def heapify(arr, n, i):
    largest = i  # 初始化最大为根
    l = 2 * i + 1     # 左 = 2*i + 1
    r = 2 * i + 2     # 右 = 2*i + 2

    # 如果左子节点大于根
    if l < n and arr[l] > arr[largest]:
        largest = l

    # 如果右子节点大于目前的最大值
    if r < n and arr[r] > arr[largest]:
        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 // 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)

# 测试堆排序
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print("排序后的数组是")
for i in range(n):
    print("%d" % arr[i], end=" ")

这段代码实现了堆排序算法。堆排序是一种基于比较的排序技术，通过构建二叉堆（通常为最大堆）来对元素进行排序。首先，它将数组元素重新排列成一个最大堆。此时，整个数组的最大值就是堆顶的根节点。将它与堆数组的末尾元素进行交换，此时末尾就是最大值。然后将剩余的n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序数组了。