Java堆排序核心是原地构建大顶堆并逐次交换堆顶与末尾后堆化调整，空间复杂度O(1)，时间复杂度O(n log n)；建堆从最后一个非叶子节点（索引arr.length/2-1）倒序heapify，排序时交换堆顶与末尾、缩短堆长、再heapify。
Java 中对整型数组使用堆排序，核心是**原地构建大顶堆 + 逐次交换堆顶与末尾 + 堆化调整**。整个过程不需要额外数组，空间复杂度 O(1)，时间稳定在 O(n log n)。
关键步骤拆解
堆排序分两阶段：先建堆，再排序。
-
建大顶堆：从最后一个非叶子节点（索引为
arr.length / 2 - 1）开始，倒序调用heapify，确保每个子树满足“父 ≥ 左右子”； -
排序循环：将堆顶（当前最大值）与末尾元素交换，堆有效长度减 1，再对新堆顶执行
heapify，恢复大顶堆性质； -
索引关系固定：对任意节点索引
i，左子为2*i+1，右子为2*i+2，父节点为(i-1)/2（整除）；
完整可运行代码
以下是一个简洁、带注释的实现：
public class HeapSort {
public static void heapSort(int[] arr) {
if (arr == null || arr.length int n = arr.length;
// 步骤1：自底向上建大顶堆（从最后一个非叶子节点开始）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 步骤2：逐个取出最大值，放到末尾
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 堆顶最大值换到末尾
heapify(arr, i, 0); // 对剩余 i 个元素重新堆化
}
}
// 下沉操作：让以 rootIndex 为根的子树满足大顶堆
private static void heapify(int[] arr, int heapSize, int rootIndex) {
int largest = rootIndex;
int left = 2 * rootIndex + 1;
int right = 2 * rootIndex + 2;
if (left arr[largest]) {
largest = left;
}
if (right arr[largest]) {
largest = right;
}
if (largest != rootIndex) {
swap(arr, rootIndex, 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;
}
}
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
调用示例：
int[] nums = {9, 8, 2, 7, 3, 1, 4, 6, 5};
HeapSort.heapSort(nums);
// 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]
常见易错点提醒
实际写时容易忽略这些细节：
- 建堆起始索引必须是
n/2 - 1，不是n-1或0； -
heapify中比较的是arr[left]和arr[largest]，不是和arr[rootIndex]直接比两次； - 排序循环中传入的
heapSize是动态缩小的（如i），不是固定n； - 递归版
heapify更易理解，但也可改写为迭代避免栈溢出（尤其大数据量）；
升序 vs 降序怎么选
升序用大顶堆（堆顶最大，每次扔到末尾）；降序则改用小顶堆——只需把 heapify 中的大小判断符号全部翻转（> 改 ），其余逻辑不变。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
