堆排序的python实现

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾 元素就变成了最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复进行交换、重建堆的操作，直到 排序完成。

堆排序流程

1. 将无序序列构造成一个大顶堆。
2. 交换堆顶元素和末尾元素。
3. 重新调整结构，使其满足大顶堆定义。
4. 重复步骤2、3，直到排序完成。

堆排序实现

# 最大堆实现
def heapify(arr: List, n: int, i: int) -> None:
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    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)

def heap_sort(arr: List) -> List:
    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)  # 在减少的堆上重新调整堆

    return arr

堆排序时间复杂度

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