堆排序 图解

堆排序是一种基于堆数据结构的排序算法。堆是一个特殊的二叉树，它的父节点总是大于等于（大根堆）或小于等于（小根堆）它的子节点。堆排序包含两个阶段：建堆和排序。在建堆阶段，需要将无序数组构建成堆。排序阶段则是将堆顶元素（最大值或最小值，取决于堆的类型）与数组末尾元素交换，并将剩余元素重新构建成堆。

图解堆排序算法如下：

1.建堆阶段：

将无序数组构建成最大堆。

假设原始数组为：[2, 5, 3, 1, 6, 4]。首先将数组构建成二叉树，然后从最后一个非叶子节点开始，依次执行“下沉”操作。具体操作为：如果当前节点的值比子节点中的最大值小，则交换它们的值，继续向下调整，直至满足堆的性质。

构建最大堆的过程如下图所示。


2.排序阶段：

将堆顶元素与数组末尾元素交换，然后调整堆。

第一次交换后，数组变为：[4, 5, 3, 1, 6, 2]。此时堆顶元素4被放置于正确的位置，但是剩余元素不再符合最大堆的性质。因此需要将剩余元素重新构建成堆。再次执行从最后一个非叶子节点开始的“下沉”操作，将6下沉至正确的位置。

排序的完整过程如下图所示。


从时间复杂度和空间复杂度两个角度分析，堆排序的优缺点如下：

1.时间复杂度：

堆排序的最坏、平均和最好时间复杂度均为O(nlogn)，且具有稳定性。

2.空间复杂度：

堆排序是一种原地排序算法，不需要额外的辅助空间。排序过程中，只需要在堆排序阶段交换堆顶元素和数组末尾元素时开辟O(1)的交换空间。

因此，堆排序是一种非常高效的排序算法，尤其适用于大规模数据的排序场景。同时，堆排序还具有易于理解、编码简洁等优点。