大根堆排序算法

大根堆排序是一种基于堆数据结构的排序算法，它的时间复杂度为 O(nlogn)。

具体过程如下：

1. 将待排序数组构建成一个大根堆。

2. 将堆顶元素（即最大值）与堆底元素交换，并将堆大小减1。

3. 对新的堆顶元素进行堆调整，使其满足堆的性质。

4. 重复步骤2-3，直到堆大小为1。

代码实现如下：

def heap_sort(arr):
    def heapify(start, end):
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child += 1
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                break

    # 构建堆
    for start in range((len(arr) - 2) // 2, -1, -1):
        heapify(start, len(arr) - 1)

    # 堆排序
    for end in range(len(arr) - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        heapify(0, end - 1)
        
    return arr

其中，heapify函数用于对指定范围内的子树进行堆调整，构建堆的过程则是从最后一个非叶子节点开始进行的。排序过程中，每次将堆顶元素与堆底元素交换后再进行堆调整，直到整个数组有序。