堆排序是一种基于二叉堆数据结构的排序算法，其核心思想是通过构建最大堆或最小堆，逐步将最大（或最小）元素移动到数组末尾，最终实现排序。以下是堆排序的详细过程图解及步骤说明：

一、构建最大堆

1. 初始化堆

   从数组的最后一个非叶子节点开始，向前遍历每个节点，对每个节点执行“向下调整”操作，确保子树满足最大堆性质（父节点≥子节点）。

2. 向下调整

   对于每个节点，比较其与左右子节点的值，若子节点较大则交换，并递归调整交换后的子节点，直到满足最大堆性质。

二、排序过程

1. 交换堆顶与末尾元素

   将最大堆的根节点（最大值）与数组末尾元素交换，此时末尾元素为最大值。

2. 重新调整堆

   将剩余元素（排除已排序的末尾元素）重新调整为最大堆，重复“向下调整”操作。

3. 重复步骤1-2

   每次交换后，堆的大小减一，继续上述过程，直到堆的大小为1，此时数组即为有序序列。

三、示例图解（以数组 [5, 2, 9, 3, 7, 1, 8, 6, 4] 为例）

1. 构建初始堆

   通过向下调整，将数组调整为大顶堆：[5, 9, 7, 3, 1, 8, 6, 4, 2]。

2. 交换与调整

   • 交换堆顶5与末尾2，得到 [2, 9, 7, 3, 1, 8, 6, 4, 5]

   • 调整剩余元素为最大堆：[2, 9, 8, 3, 1, 6, 4, 5, 7]

   • 重复上述步骤，最终得到有序数组：[1, 2, 3, 4, 5, 6, 7, 8, 9]。

四、关键要点

• 时间复杂度 ：

  • 构建堆：O（n）

  • 排序过程：O（n log n）

  • 总体时间复杂度：O（n log n）

• 空间复杂度 ：O（1）（原地排序）

• 稳定性 ：堆排序是不稳定的排序算法。

通过上述步骤，堆排序能够高效地对大规模数据进行排序，尤其适用于需要稳定时间复杂度的场景。