以下是 堆排序（Heap Sort） 的完整 Java 实现，包含详细注释和测试示例：

✅ 堆排序 Java 代码

import java.util.Arrays;

public class HeapSort {

/**
 * 堆排序主方法
 * @param arr 待排序的整型数组
 */
public static void heapSort(int[] arr) {
    if (arr == null || arr.length = 0; i--) {
        heapify(arr, n, i);
    }

    // 第二步：依次将堆顶（最大值）与末尾元素交换，并缩小堆范围
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);          // 将最大值移到末尾
        heapify(arr, i, 0);       // 对前 i 个元素重新堆化（堆大小为 i）
    }
}

/**
 * 调整以 index 为根的子树为最大堆（递归版）
 * 假设左右子树已经是最大堆
 * @param arr 数组
 * @param heapSize 当前堆的有效大小
 * @param index 根节点索引
 */
private static void heapify(int[] arr, int heapSize, int index) {
    int largest = index;           // 假设当前根最大
    int left = 2 * index + 1;      // 左孩子
    int right = 2 * index + 2;     // 右孩子

    // 找出三者（根、左、右）中的最大值索引
    if (left  arr[largest]) {
        largest = left;
    }
    if (right  arr[largest]) {
        largest = right;
    }

    // 如果最大值不是当前根，则交换并继续向下调整
    if (largest != index) {
        swap(arr, index, largest);
        heapify(arr, heapSize, largest); // 递归调整被影响的子树
    }
}

/**
 * 交换数组中两个位置的元素
 */
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 测试主方法
public static void main(String[] args) {
    int[] arr = {4, 10, 3, 5, 1, 12, 7};
    System.out.println("原始数组: " + Arrays.toString(arr));

    heapSort(arr);

    System.out.println("堆排序后: " + Arrays.toString(arr));
}

}

📌 输出示例：
原始数组: [4, 10, 3, 5, 1, 12, 7]
堆排序后: [1, 3, 4, 5, 7, 10, 12]

🔍 关键点说明：

1. 建堆：从 n/2 - 1 开始（完全二叉树中最后一个非叶子节点），自底向上调用 heapify。
2. 排序过程：
   • 每次将堆顶（最大值）与未排序部分的最后一个元素交换；
   • 缩小堆的范围（heapSize–）；
   • 对新堆顶调用 heapify 恢复堆性质。
3. 时间复杂度：O(n log n)（建堆 O(n)，n 次 heapify 各 O(log n)）
4. 空间复杂度：O(1)（原地排序，仅使用常数额外空间）
5. 稳定性：不稳定（交换操作可能改变相等元素的相对顺序）

💡 补充：非递归版 heapify（可选优化）

如果你担心递归深度（虽然堆高只有 log n），也可以写成循环形式：

private static void heapifyIterative(int[] arr, int heapSize, int index) {
int current = index;
while (true) {
int largest = current;
int left = 2 * current + 1;
int right = 2 * current + 2;

    if (left  arr[largest]) {
        largest = left;
    }
    if (right  arr[largest]) {
        largest = right;
    }

    if (largest == current) break; // 堆性质已满足

    swap(arr, current, largest);
    current = largest; // 继续向下调整
}

}

如需泛型版本（支持 Comparable）、最小堆实现或性能对比，也可以告诉我！