本文是 Java排序算法面试手写精讲 的分章阅读版。
构建大顶堆 -> 堆顶最大元素与末尾交换 -> 缩小堆范围 -> 重新堆化(siftDown) -> 重复。
public static void heapSort(int[] arr) {
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); // 重新堆化(堆大小减1)
}
}
private static void heapify(int[] arr, int size, int root) {
int largest = root;
int left = 2 * root + 1;
int right = 2 * root + 2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest != root) {
swap(arr, root, largest);
heapify(arr, size, largest); // 递归堆化子树
}
}
public class HeapSort {
/**
* 堆排序入口
* 时间复杂度:建堆O(n) + n次siftDown O(nlogn) = O(nlogn)
* 空间复杂度:O(1) 原地排序
* 不稳定:siftDown可能改变相等元素的相对顺序
*/
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// Phase 1: 建堆(Floyd建堆法)
// 从最后一个非叶子节点开始,自底向上siftDown
// 为什么从n/2-1开始?因为索引n/2到n-1都是叶子节点,已经是合法的堆
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(arr, n, i);
}
// Phase 2: 逐个提取最大值
// 每次将堆顶最大元素交换到数组末尾,然后缩小堆的范围
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 堆顶(最大值)放到已排序区域
siftDown(arr, i, 0); // 对新的堆顶执行siftDown,堆大小=i
}
}
/**
* 下沉操作(迭代版,避免递归栈开销)
*
* @param arr 数组
* @param size 当前堆的有效大小(不是数组长度)
* @param i 需要下沉的节点索引
*
* 逻辑:将arr[i]与其较大的子节点比较,如果比子节点小则交换,直到满足堆性质
*/
private static void siftDown(int[] arr, int size, int i) {
int half = size >>> 1; // 只需要遍历到非叶子节点
while (i < half) {
int child = (i << 1) + 1; // 左子节点 = 2*i+1
int right = child + 1; // 右子节点 = 2*i+2
// 找出两个子节点中较大的
if (right < size && arr[right] > arr[child]) {
child = right;
}
// 如果父节点已经 >= 最大的子节点,堆性质已满足
if (arr[i] >= arr[child]) break;
// 否则交换,继续下沉
swap(arr, i, child);
i = child;
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
}
建堆为什么是O(n)而不是O(nlogn)? 直觉上n/2个节点每个siftDown最多logn,应该是O(nlogn)。但实际大部分节点在底层,siftDown深度很小:第k层有2^k个节点,每个下沉h-k层。总移动次数 = sum(2^k * (h-k)) = O(n)。数学证明比直觉更紧。
面试关联: 堆排序与Top-K问题直接相关——用小顶堆维护K个最大元素,时间复杂度O(nlogk)。Java的PriorityQueue底层就是堆结构,默认小顶堆。