网站导航类型_个人博客网站总结_百度人工服务热线_百度推广步骤

堆排序（Heap Sort）

堆排序是一种基于二叉堆数据结构的排序算法。它的基本思想是：将待排序的数组构建成一个最大堆（或最小堆），然后依次将堆顶元素（最大值或最小值）与堆的最后一个元素交换，并调整堆，重复这个过程直到整个数组有序。

堆排序的步骤：

构建最大堆：将数组调整为一个最大堆。
交换堆顶元素：将堆顶元素（最大值）与堆的最后一个元素交换。
调整堆：将剩余元素重新调整为最大堆。
重复过程：重复步骤 2 和 3，直到整个数组有序。

时间复杂度：

最坏情况：O(n log n)
最好情况：O(n log n)
平均情况：O(n log n)

空间复杂度：

O(1) —— 堆排序是一种原地排序算法，不需要额外的存储空间。

Python 实现

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 arrdef 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)  # 递归调整子树# 示例使用
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
print("排序后的数组:", sorted_arr)

输出结果

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

堆排序的详细过程

以数组 [12, 11, 13, 5, 6, 7] 为例：

构建最大堆：
- 初始数组：[12, 11, 13, 5, 6, 7]
- 调整后最大堆：[13, 11, 12, 5, 6, 7]
交换堆顶元素：
- 将堆顶元素 13 与最后一个元素 7 交换。
- 数组变为：[7, 11, 12, 5, 6, 13]
调整堆：
- 调整剩余元素 [7, 11, 12, 5, 6] 为最大堆。
- 调整后最大堆：[12, 11, 7, 5, 6]
重复过程：
- 将堆顶元素 12 与最后一个元素 6 交换。
- 数组变为：[6, 11, 7, 5, 12, 13]
- 调整剩余元素 [6, 11, 7, 5] 为最大堆。
- 重复上述步骤，直到整个数组有序。
最终结果：
- 排序后的数组：[5, 6, 7, 11, 12, 13]

堆排序的优缺点

优点：

时间复杂度稳定为 O(n log n)，性能优异。
是原地排序算法，不需要额外的存储空间。

缺点：

不是稳定的排序算法（相同元素的相对位置可能改变）。
对于小规模数据，性能可能不如插入排序等简单算法。

堆排序的适用场景

需要原地排序的场景。
数据规模较大。
对稳定性没有要求的场景。

总结

堆排序是一种高效的排序算法，适用于大规模数据的排序。通过构建最大堆和逐步提取堆顶元素，可以实现数组的排序。尽管它不是稳定的排序算法，但其时间复杂度和空间复杂度使其在实际应用中具有较高的价值。