python编写堆排序

以下是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[i], arr[0] = arr[0], arr[i]
        # 维护最大堆
        heapify(arr, i, 0)

def heapify(arr, n, i):
    # 找到左右子节点
    left = 2 * i + 1
    right = 2 * i + 2
    
    # 假设当前节点是最大值
    largest = i
    
    # 如果左子节点比当前节点大，则更新最大值
    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)

使用`heap_sort()`函数对列表进行堆排序：

arr = [64, 34, 25, 12, 22, 11, 90]
heap_sort(arr)
print(arr)

输出结果：

[11, 12, 22, 25, 34, 64, 90]