夜雨聆风
Java源码中的排序算法(三)- HeapSort
上一篇讲 DualPivotQuicksort（双轴快排）时提到它的智能算法切换，通过源码可以看到它的切换选择有多个，今天我们讲一个当检测到程序有 “恶化倾向(当时间复杂度可能变为O(n²) )” 时，作为保底策略启用的堆排序。
final class DualPivotQuicksort {/*** Threshold of mixed insertion sort is incremented by this value.* 混合插入排序的阈值通过此值进行递增。*/private static final int DELTA = 3 << 1; //常量 6/*** Max recursive partitioning depth before using heap sort.* 在使用堆排序之前的最大递归分区深度。*/private static final int MAX_RECURSION_DEPTH = 64 * DELTA;staticvoidsort(Sorter sorter, int[] a, int bits, int low, int high){// 省略部分代码.../** Switch to heap sort if execution* time is becoming quadratic.(时间复杂度正在变为O(n²)。)*/if ((bits += DELTA) > MAX_RECURSION_DEPTH) {heapSort(a, low, high);return;}// 省略部分代码...}}
这么做的好处
- 防止栈溢出：过深的递归可能导致 StackOverflowError
- 性能保护：当递归深度过大时，快排可能退化为 O(n²) 复杂度
- 保证稳定性：通过切换到堆排序等方法维持 O(n log n) 的时间复杂度
这正是“稳”的工程体现，今天就聚焦这个低调排序算法 ——— 堆排序，逐步拆解学习，让我们开始吧
一、堆排序工作过程：建堆 + 抽顶
先看一段JDK风格堆排序代码（简化自 java.util.DualPivotQuicksort内部实现）：
private static void heapSort(int[] a, int low, int high) {// STEP 1：自底向上建大顶堆（从最后一个非叶子节点开始）for (int k = (low + high) >>> 1; k > low; ) {pushDown(a, --k, a[k], low, high);}// STEP 2：反复“抽顶”：堆顶最大值 → 末尾，重建堆while (--high > low) {int max = a[low]; // 保存堆顶（当前最大值）pushDown(a, low, a[high], low, high); // 末尾元素上位，下沉调整a[high] = max; // 最大值归位到已排序区}}private static void pushDown(int[] a, int p, int value, int low, int high) {for (int k ;; a[p] = a[p = k]) {k = (p << 1) - low + 2; // 计算右孩子索引if (k > high) break; // 无孩子，停止if (k == high || a[k] < a[k - 1]) --k; // 选更大的孩子if (a[k] <= value) break; // 父节点不小于子节点，停止}a[p] = value;}
实例演示：排序数组 [4,10,3,5,1]
初始状态（二叉树表示）：
4/ \10 3/ \5 1
步骤1：建大顶堆
- 从索引
(0+4)/2=2向前遍历（索引2为叶子节点，跳过） - 调整索引1（值10）：已满足堆性质
- 调整索引0（值4）：
- 4 与子节点10交换 →
[10,4,3,5,1] - 4 与子节点5交换 →
[10,5,3,4,1]
4/ \10 3/ \5 1
步骤2：交换堆顶 + 重建堆
|
|
|
|
|
|---|---|---|---|
|
|
|
[1,5,3,4,10] |
|
|
|
[5,4,3,1,10] |
|
|
|
|
|
[1,4,3,5,10] |
|
|
|
[4,1,3,5,10] |
|
|
|
|
|
[1,3,4,5,10] |
|
源码关键点解析
- 索引计算：
k=(p<<1)-low+2精准计算右孩子索引，支持任意子数组区间（low非0场景） - 下沉优化：
value暂存待调整值，最后一次性赋值，减少内存写入次数 - 边界处理：
k==high判断巧妙处理“仅存在左孩子”的边界情况 - 高效建堆：从
(low+high)/2开始向前遍历，跳过叶子节点无效操作
二、性能优势：为什么说它“稳如泰山”？
|
|
|
|
|
|---|---|---|---|
| 最坏时间复杂度 |
|
|
|
| 空间复杂度 |
|
|
|
| 稳定性 |
|
|
|
| 缓存友好性 |
|
|
|
| 适用场景 |
|
|
|
核心优势
- 最坏情况有保障：实时系统、金融交易等绝不允许性能雪崩的场景
- 内存零负担：嵌入式设备、IoT环境（原地排序，无需额外数组）
- Top-K问题高效解：建大小为K的堆，时间复杂度O(n log K)，远优于全排序O(n log n)
示例：从1亿条日志中找访问量最高的10个IP使用最小堆维护Top 10，内存仅占10个元素，效率碾压全排序。
三、适用场景决策指南
推荐使用场景
- 内存极度受限环境：嵌入式系统、单片机（O(1)空间）
- 需要最坏性能保证：航天控制、高频交易系统（拒绝O(n²)风险）
- Top-K问题：实时榜单、推荐系统（用堆而非全排序）
- 外部排序辅助：数据库多路归并中维护K路最小值
避坑指南
- 数据量小（<50）：插入排序更快（常数因子小）
- 需要稳定排序：选择TimSort或归并排序（如按时间二次排序需保留原始顺序）
- 数据基本有序：快排或TimSort更优（堆排序无局部性优势）
💡 感谢你看完这篇内容，这是我自己在工作学习中遇到的case，做一些简单的 究，并总结经验，如有遗漏或不合理的地方，欢迎你提出问题，让我们一起探索。
