Python堆排序详解（从零开始掌握堆排序算法）

堆排序的基本思想

堆排序的核心步骤如下：

1. 将待排序数组构建成一个最大堆。
2. 将堆顶元素（最大值）与末尾元素交换，然后缩小堆的范围（排除已排序的末尾元素）。
3. 对新的堆顶元素进行堆化（heapify），使其重新满足最大堆性质。
4. 重复步骤2和3，直到堆中只剩一个元素。

Python堆排序算法实现

下面我们用Python一步步实现堆排序。整个过程分为两个主要函数：

• heapify(arr, n, i)：维护以i为根节点的子树为最大堆。
• heap_sort(arr)：主函数，负责构建初始堆并执行排序。

def heapify(arr, n, i):    """    维护最大堆性质    :param arr: 数组    :param n: 堆的大小    :param 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)  # 递归堆化受影响的子树def heap_sort(arr):    """    堆排序主函数    :param 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)               # 对剩余元素重新堆化# 测试示例if __name__ == "__main__":    data = [12, 11, 13, 5, 6, 7]    print("原始数组:", data)    heap_sort(data)    print("排序后数组:", data)  

代码解析

1. heapify 函数：

该函数确保以索引 i 为根的子树满足最大堆性质。它比较根节点与其左右子节点，找出最大值。如果最大值不是根节点，则交换，并递归处理被影响的子树。

2. 构建初始堆：

在 heap_sort 中，我们从最后一个非叶子节点（索引为 n//2 - 1）开始，自底向上调用 heapify，从而构建完整的最大堆。

3. 排序过程：

每次将堆顶（最大值）与当前堆的最后一个元素交换，然后缩小堆的范围（i 递减），并对新堆顶调用 heapify，重复此过程直至排序完成。

堆排序的性能分析

• 时间复杂度：无论最好、最坏还是平均情况，都是 O(n log n)。
• 空间复杂度：O(1)，属于原地排序算法。
• 稳定性：不稳定（相同元素的相对位置可能改变）。

总结

通过本教程，你已经掌握了如何用Python语言实现堆排序算法。堆排序虽然不如快速排序在平均情况下快，但它具有稳定的 O(n log n) 时间复杂度，适用于对性能要求较高的场景。希望这篇关于堆排序算法的详细讲解能帮助你深入理解这一经典排序方法！

如果你正在学习Python排序算法，不妨动手运行上面的代码，修改测试数据，加深理解。掌握堆排序实现不仅有助于面试，也能提升你的算法思维能力！