什么是堆排序

堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法。它的主要思想是将待排序的序列构建成一个大顶堆（或小顶堆），然后反复从堆顶取出最大（或最小）元素，将剩余的元素重新调整为一个新的堆，再重复取出堆顶元素的过程，直到排序完成。

算法思想

构建堆：将待排序序列构建成一个大顶堆（或小顶堆）。从最后一个非叶子节点开始，对每个非叶子节点进行以下操作：
比较该节点与其左右子节点的大小，找出最大（或最小）的元素。
如果最大（或最小）元素不是该节点本身，则交换它们的位置。
然后，以交换后的子节点为根节点，继续向下调整，直到堆的末尾。
排序：此时堆顶元素是最大（或最小）的元素，将其与堆的末尾元素交换位置，然后将剩余的元素重新调整为一个新的堆。重复这个过程，直到堆中只有一个元素。

堆排序的关键在于构建堆和调整堆的过程。构建堆的时间复杂度为O(n)，其中n是待排序序列的长度。排序过程中，需要进行n-1次交换操作，每次交换后需要调整堆的结构，时间复杂度为O(logn)。因此，堆排序的总时间复杂度为O(nlogn)。

代码示例

# sift函数用来调整堆
def sift(li, low, high):
    '''
    low: 二叉数的根节点
    high: 二叉树的最后一个节点
    '''
    i = low  # i最开始指向根节点
    j = 2 * i + 1  # 左孩子
    temp = li[low]
    while j <= high:  # 只要j位置有数
        if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子有且比较大
            j = j + 1  # j指向这个较大的右孩子
        if li[j] > temp:  # 如果当前根节点比最大的孩子大
            li[i] = li[j]  # 把这个孩子放入根节点
            i = j  # 往下看一层
            j = 2 * i + 1
        else:
            break
    li[i] = temp  # 最后把temp放入到叶子节点上


def heap_sort(li):
    n = len(li)
    # 先建堆
    for i in range((n - 2) // 2, -1, -1):
        # i表示舰堆时跟节点的下标，从第一个非叶子节点，也就是最后一个元素n-1的根节点(n-1-1)/2
        sift(li, i, n - 1)
    # 建堆完成，开始排序
    for i in range(n - 1, -1, -1):
        # i指向当前堆的最后一个元素
        li[i], li[0] = li[0], li[i]  # 为了节省空间，依次把根节点最大元素和最后一个元素交换
        sift(li, 0, i - 1)  # 前第i个元素已为有序