堆排序是不稳定的排序算法，因建堆和交换过程中相等元素可能被跨层交换或堆顶替换而改变相对顺序，虽时间复杂度稳定为O(n log n)、空间复杂度为O(1)，但无法保证相同元素的原始先后位置。
堆排序在 Java 中可通过数组原地构建最大堆实现，它本质上是不稳定的排序算法，因为相同元素在堆调整过程中可能被交换位置。
用数组构建最大堆并完成堆排序
堆排序分两步：先将数组构造成最大堆（父节点 ≥ 子节点），再逐个将堆顶最大元素与末尾交换，并缩小堆范围重新调整。Java 中无需额外数据结构，直接操作数组即可：
- 从最后一个非叶子节点（索引为 arr.length / 2 - 1）开始，自底向上调用 siftDown（下沉）操作，确保每个子树满足最大堆性质
- 建堆完成后，循环执行：交换 arr[0] 与 arr[i]（i 从末尾递减），再对剩余前 i 个元素调用 siftDown(0, i) 恢复堆结构
- siftDown 的核心逻辑是：比较当前节点与其左右孩子，找出三者中最大值的索引；若最大值不是当前节点，则交换并继续下沉该孩子位置
关键代码片段（简化版）
以下为可运行的核心逻辑（省略 main 方法和输入输出）：
<font size="2"><pre class="brush:php;toolbar:false;">public static void heapSort(int[] arr) {
int n = arr.length;
// 步骤1：自底向上建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(arr, i, n);
}
// 步骤2：逐个取出最大值
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 堆顶与末尾交换
siftDown(arr, 0, i); // 对剩余 i 个元素重新堆化
}
}
<p>private static void siftDown(int[] arr, int idx, int heapSize) {
while (true) {
int largest = idx;
int left = 2 <em> idx + 1;
int right = 2 </em> idx + 2;</p><pre class='brush:java;toolbar:false;'> if (left < heapSize && arr[left] > arr[largest]) largest = left;
if (right < heapSize && arr[right] > arr[largest]) largest = right;
if (largest == idx) break;
swap(arr, idx, largest);
idx = largest;
}}
立即学习“Java免费学习笔记（深入）”；
private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
为什么堆排序是不稳定的？
稳定性指相等元素的相对顺序在排序前后保持不变。堆排序的不稳定性源于两个关键环节：
-
建堆过程中的跨层交换：例如数组
[5a, 2, 5b, 1]（a/b 仅作标识），建堆时 1 上浮、5b 下沉，可能导致 5b 移动到 5a 前方 -
排序阶段的堆顶交换：每次把最大值（可能是后出现的相同元素）换到末尾，打乱原始次序。如
[3a, 1, 3b, 2]建成最大堆后可能变为[3b, 2, 3a, 1]，再交换后 3b 先落位，3a 后落位，顺序已变 - 这种交换不依赖元素原始索引，仅由值大小和堆结构决定，无法保证相等键的先后关系
对比稳定排序的典型差异
与归并排序（稳定）不同，堆排序没有“有序子序列合并”机制；也不像插入排序那样逐个挪动、保留局部顺序。它的全局重构特性天然牺牲了稳定性，但换来了 O(1) 空间复杂度 和 O(n log n) 时间下界保障 —— 即使最坏情况也不会退化。
