python实现堆排序

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

def heap_sort(arr):
    # 构建大根堆
    def build_max_heap(arr):
        for i in range(len(arr)//2-1, -1, -1):
            heapify(arr, i, len(arr))
    # 调整堆，使其成为大根堆
    def heapify(arr, i, size):
        l = 2 * i + 1
        r = 2 * i + 2
        largest = i
        if l < size and arr[l] > arr[largest]:
            largest = l
        if r < size and arr[r] > arr[largest]:
            largest = r
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, largest, size)
    # 堆排序主函数
    build_max_heap(arr)
    for i in range(len(arr)-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i)
    return arr

堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。