千问 堆排序（Heap Sort） 的完整 Java 实现

以下是 堆排序（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]

🔍 关键点说明：

💡 补充：非递归版 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）、最小堆实现或性能对比，也可以告诉我！