堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法，其核心步骤包括构建堆和反复调整堆结构。以下是Java实现的详细说明：
1. 算法步骤构建大顶堆
从最后一个非叶子节点（索引为length/2 - 1）开始，自底向上调整每个子树，使其满足大顶堆性质（父节点 ≥ 子节点）。
关键操作：adjustHeap()方法负责调整以当前节点为根的子树。
交换堆顶与末尾元素
将堆顶元素（最大值）与当前无序区的末尾元素交换，此时末尾元素归入有序区。
调整剩余无序区，使其重新成为大顶堆。
重复调整
每次交换后，无序区长度减1，直到所有元素有序。
2. Java代码实现import java.util.Arrays;public class HeapSort { public static void main(String[] args) { int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; heapSort(array); System.out.println(Arrays.toString(array)); // 输出排序后的数组 } / * 堆排序主方法 */ public static void heapSort(int[] array) { if (array == null || array.length <= 1) { return; } int length = array.length; // 1. 构建大顶堆 for (int i = length / 2 - 1; i >= 0; i--) { adjustHeap(array, i, length); } // 2. 交换堆顶与末尾元素，并调整堆 for (int j = length - 1; j > 0; j--) { swap(array, 0, j); // 交换 adjustHeap(array, 0, j); // 调整剩余无序区 } } / * 调整大顶堆（从节点i开始，调整长度为length的子树） */ private static void adjustHeap(int[] array, int i, int length) { int temp = array[i]; // 保存当前节点值 for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { // 从左子节点开始 // 选择较大的子节点 if (k + 1 < length && array[k] < array[k + 1]) { k++; } // 若子节点大于父节点，上移子节点 if (array[k] > temp) { array[i] = array[k]; i = k; // 继续向下调整 } else { break; } } array[i] = temp; // 放置temp到正确位置 } / * 交换数组中两个元素的位置 */ private static void swap(int[] array, int a, int b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; }}3. 关键点解析- 大顶堆性质：父节点值 ≥ 子节点值，确保堆顶为最大值。
- 调整堆的逻辑：
从节点i的左子节点（2i+1）开始比较，若右子节点（2i+2）更大则选择右子节点。
若子节点值大于当前节点值，则上移子节点，并继续向下调整。
- 时间复杂度：
构建堆：O(n)
每次调整堆：O(log n)，共需调整n-1次 → 总复杂度：O(n log n)
- 空间复杂度：O(1)（原地排序）。
4. 动图演示（动图展示了堆排序的构建堆、交换和调整过程）5. 常见问题- 为什么从length/2 - 1开始构建堆？因为叶子节点无需调整，最后一个非叶子节点的索引为n/2 - 1（完全二叉树性质）。
- 与快速排序对比：堆排序最坏情况下仍为O(n log n)，但常数因子较大，实际性能略逊于快速排序。
通过以上步骤和代码，你可以清晰理解堆排序的实现原理。建议手动模拟小规模数据（如[4, 10, 3, 5, 1]）的排序过程以加深理解。
