深入理解堆排序（Python语言堆排序算法从入门到精通）

堆排序的基本思想

堆排序分为两个主要阶段：

1. 构建最大堆：将无序数组构造成一个最大堆。
2. 重复提取最大值：将堆顶（最大值）与末尾元素交换，然后重新调整堆，直到所有元素有序。

Python实现堆排序

下面我们用Python一步步实现堆排序算法。

1. 调整堆（heapify）函数

这个函数用于维护堆的性质。假设根节点的左右子树已经是堆，但根节点可能破坏了堆的性质，我们需要“下沉”根节点以恢复堆结构。

def heapify(arr, n, i):    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)  # 递归调整受影响的子树

2. 堆排序主函数

首先构建最大堆，然后逐个将堆顶元素移到末尾，并重新调整堆。

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)                # 对剩余元素重新调整堆    return arr

3. 测试代码

# 示例使用if __name__ == "__main__":    data = [12, 11, 13, 5, 6, 7]    print("原始数组:", data)    sorted_data = heap_sort(data)    print("排序后数组:", sorted_data)

运行结果：

原始数组: [12, 11, 13, 5, 6, 7]排序后数组: [5, 6, 7, 11, 12, 13]

堆排序的时间与空间复杂度

• 时间复杂度：无论最好、最坏还是平均情况，都是 O(n log n)。
• 空间复杂度：O(1)，因为它是原地排序算法（不考虑递归栈空间）。

总结

通过本教程，你已经掌握了Python堆排序的核心原理和实现方法。堆排序虽然不如快速排序在实际应用中常见，但它具有稳定的时间复杂度，非常适合学习数据结构与算法的基础知识。希望这篇堆排序实现教程能帮助你更好地理解这一经典算法！

关键词回顾：Python堆排序、堆排序算法详解、Python排序算法、堆排序实现教程。