前言
堆排序（Heap Sort）是一种高效的排序算法，由 J. W. J. Williams 于 1964 年提出。它巧妙利用堆数据结构的特性，结合了插入排序和归并排序的优点，兼具原地排序和稳定时间复杂度的特性。本文将深入剖析堆排序的原理、实现及优化，助你彻底掌握这一经典算法。
🌟 核心思想
堆排序基于二叉堆的以下特性：
- 堆结构：完全二叉树，满足：
- 大顶堆：父节点值 ≥ 子节点值（用于升序排序）。
- 小顶堆：父节点值 ≤ 子节点值（用于降序排序）。
- 关键操作：
- 建堆（Heapify）：将无序数组转化为堆结构。
- 调整堆：移除堆顶后重新平衡堆。
- 排序流程：
⚙️ Java实现
public class HeapSort {
public void sort(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);
}
}
// 堆化操作（大顶堆）
private void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大值为根节点
int left = 2*i + 1; // 左子节点
int right = 2*i + 2; // 右子节点
// 检查左子节点是否大于根
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 检查右子节点是否大于当前最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 若最大值不是根节点，交换并递归调整
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest); // 递归调整子树
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
关键点解析：
- 建堆起点：从最后一个非叶子节点（n/2 - 1）开始自底向上堆化。
- 排序阶段：每次将堆顶（最大值）交换到末尾，缩小堆范围后重新调整。
- 递归堆化：确保子树始终满足堆性质。
🔍 时间复杂度分析
| 阶段 | 时间复杂度 | 说明 |
|---|---|---|
| 建堆 | O(n) | 非叶子节点的高度求和 |
| 排序 | O(n log n) | 执行 n-1 次堆调整 |
| 总计 | O(n log n) | 最优/最坏/平均均相同 |
📦 空间复杂度
| 类型 | 空间复杂度 | 说明 |
|---|---|---|
| 原地排序 | O(1) | 仅用常数级额外空间 |
| 递归栈 | O(log n) | 堆化递归深度（可优化为迭代） |
迭代优化堆化函数：
private void heapifyIterative(int[] arr, int n, int i) {
int current = i;
while (true) {
int left = 2*current + 1;
int right = 2*current + 2;
int largest = current;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest == current) break;
swap(arr, current, largest);
current = largest; // 向下继续调整
}
}
✅ 算法特性
| 特性 | 说明 |
|---|---|
| 稳定性 | ❌ 非稳定（交换可能改变相同值元素的顺序） |
| 原地性 | ✅ 不需要额外存储空间 |
| 适应性 | ❌ 输入数据分布不影响性能 |
| 比较排序 | ✅ 基于元素比较操作 |
⚡ 优化技巧
- 自底向上建堆比自顶向下效率更高（减少比较次数）。
- 用循环替代递归，避免栈溢出风险（代码见上一节）。
- 需降序排序时改用小顶堆，调整比较逻辑即可。
- 元素移动优化：
// 减少交换次数（类似插入排序）
void heapifyMove(int[] arr, int n, int i) {
int temp = arr[i];
int current = i;
while (2*current + 1 < n) {
int child = 2*current + 1;
if (child+1 < n && arr[child+1] > arr[child]) child++;
if (arr[child] <= temp) break;
arr[current] = arr[child]; // 子节点上移
current = child;
}
arr[current] = temp; // 最终位置
}
💡 实际应用场景
- 内存受限系统：嵌入式设备（原地排序特性节省内存）。
- 实时系统：工业控制系统（稳定 O(n log n) 时间保证响应）。
- 优先级队列实现：任务调度（高效插入/删除最大元素）。
- Top-K 问题：构建大小为 K 的堆找最大/最小 K 个元素。
🌐 总结
当内存敏感且需要避免快速排序最坏情况时，堆排序是理想选择。虽在日常开发中不如快速排序应用广泛，但其理论价值和在特定场景下的实用性不可替代。