堆排序 题目描述：给定一个整数数组，使用堆排序算法将其按升序排列。 解题过程： 理解堆结构 堆是一种特殊的完全二叉树，满足： 最大堆：每个节点的值都大于或等于其子节点的值 最小堆：每个节点的值都小于或等于其子节点的值 堆排序使用最大堆来实现升序排序 算法步骤 步骤1：构建最大堆 从最后一个非叶子节点开始（索引为n/2-1），向前遍历到根节点 对每个节点执行"堆化"操作，确保以该节点为根的子树满足最大堆性质 步骤2：排序过程 将堆顶元素（最大值）与最后一个元素交换 排除最后一个元素（已排序），对剩余部分重新堆化 重复上述过程直到所有元素有序 详细实现过程 以数组[ 4, 10, 3, 5, 1 ]为例： 构建最大堆： 最后一个非叶子节点索引：5/2-1=1（节点10） 从节点10开始堆化：比较10与其子节点5和1，10最大，无需调整 处理节点4：比较4与其子节点10和3，10最大，交换4和10 交换后数组变为[ 10, 4, 3, 5, 1 ] 检查节点4的新位置：比较4与其子节点5，5更大，交换4和5 最终最大堆：[ 10, 5, 3, 4, 1 ] 排序过程： 交换堆顶10与末尾1：[ 1, 5, 3, 4, 10 ]（10已排序） 对前4个元素堆化：从根节点1开始，比较1与子节点5和3，5最大，交换1和5 得到[ 5, 1, 3, 4, 10 ]，继续堆化节点1，比较1与子节点4，交换1和4 得到[ 5, 4, 3, 1, 10 ] 交换堆顶5与当前末尾1：[ 1, 4, 3, 5, 10 ]（5,10已排序） 重复上述过程直到完全有序 关键操作：堆化函数 堆化是维护堆性质的核心操作： 比较当前节点与其左右子节点 如果子节点更大，与最大的子节点交换 递归处理被交换的子节点位置 时间复杂度：O(log n) 复杂度分析 时间复杂度：O(n log n) 构建堆：O(n) 每次提取最大值并重新堆化：O(log n)，执行n-1次 空间复杂度：O(1)，原地排序 堆排序特别适合需要部分排序或实时排序的场景，是不稳定排序算法。