堆排序 描述 堆排序是一种基于 二叉堆 （通常是大顶堆或小顶堆）的排序算法。它的核心思想是将待排序的序列构造成一个堆，然后反复将堆顶元素（最大值或最小值）与堆末尾元素交换，并重新调整堆，直到整个序列有序。堆排序的时间复杂度为 O(n log n) ，且是 原地排序 （不需要额外空间）。 知识点分解与步骤 堆的基本概念 堆是一棵 完全二叉树 ，即除最后一层外，其他层节点数达到最大值，最后一层节点从左到右排列。 大顶堆 ：每个节点的值都大于或等于其左右子节点的值（根节点最大）。 小顶堆 ：每个节点的值都小于或等于其左右子节点的值（根节点最小）。 堆的存储方式 堆通常用 数组 存储。对于数组中下标为 i 的节点： 父节点下标： (i-1)/2 （向下取整） 左子节点下标： 2*i + 1 右子节点下标： 2*i + 2 堆排序的步骤 步骤 1：构建初始大顶堆 从最后一个 非叶子节点 （下标为 n/2 - 1 ）开始，从右到左、从下到上依次对每个节点进行 下沉操作（heapify） ，使以该节点为根的子树满足大顶堆性质。 下沉操作 ：比较当前节点与其左右子节点，若子节点值更大，则将最大的子节点与当前节点交换，并继续向下调整直到满足堆性质。 示例 （数组 [3, 5, 2, 7, 1] ）： 非叶子节点依次为下标 1（值 5）、下标 0（值 3）。 调整下标 1：子节点为值 1，无需交换。 调整下标 0：左子节点值 5 < 右子节点值 7，与右子节点交换，得到 [7, 5, 2, 3, 1] 。 步骤 2：排序 将堆顶元素（最大值）与末尾元素交换，此时末尾元素为最大值。 排除末尾元素，对剩余堆（大小减 1）重新调整为大顶堆。 重复上述过程，直到堆大小为 1。 接上例 ： 初始堆 [7, 5, 2, 3, 1] ，交换堆顶 7 和末尾 1，得到 [1, 5, 2, 3, 7] ，调整前 4 个元素为新堆 [5, 3, 2, 1] 。 交换堆顶 5 和末尾 1，得到 [1, 3, 2, 5, 7] ，调整前 3 个元素为 [3, 1, 2] 。 依此类推，最终得到有序数组 [1, 2, 3, 5, 7] 。 时间复杂度分析 建堆过程：O(n) 每次下沉调整：O(log n) 总共 n-1 次调整：O(n log n) 总时间复杂度：O(n log n) 关键点总结 堆排序通过 下沉操作 维护堆性质，逐步将最大值移到末尾。 适合对大规模数据排序，且不需要额外空间（优于归并排序）。 不稳定排序（相同值可能交换顺序）。