如何在 Java 中利用数组实现简单的堆排序（Heap Sort）并分析其不稳定性特征-java教程-PHP中文网

堆排序是不稳定的排序算法，因建堆和交换过程中相等元素可能被跨层交换或堆顶替换而改变相对顺序，虽时间复杂度稳定为o(n log n)、空间复杂度为o(1)，但无法保证相同元素的原始先后位置。

如何在 java 中利用数组实现简单的堆排序（heap sort）并分析其不稳定性特征

堆排序在 Java 中可通过数组原地构建最大堆实现，它本质上是不稳定的排序算法，因为相同元素在堆调整过程中可能被交换位置。

用数组构建最大堆并完成堆排序

堆排序分两步：先将数组构造成最大堆（父节点 ≥ 子节点），再逐个将堆顶最大元素与末尾交换，并缩小堆范围重新调整。Java 中无需额外数据结构，直接操作数组即可：

从最后一个非叶子节点（索引为 arr.length / 2 - 1）开始，自底向上调用 siftDown（下沉）操作，确保每个子树满足最大堆性质
建堆完成后，循环执行：交换 arr[0] 与 arr[i]（i 从末尾递减），再对剩余前 i 个元素调用 siftDown(0, i) 恢复堆结构
siftDown 的核心逻辑是：比较当前节点与其左右孩子，找出三者中最大值的索引；若最大值不是当前节点，则交换并继续下沉该孩子位置

关键代码片段（简化版）

以下为可运行的核心逻辑（省略 main 方法和输入输出）：

JavaStoryDevelop

你接手一个需求时，是不是经常这样："改一个小字段 → 结果把不相关的代码也改了"、"需求说得很模糊 → 做着做着发现跑偏了"、"数据库加个字段 → 上线才发现漏了数据兼容"、"做了个新功能 → 一个月后自己都忘了当时怎么设计的"、"写到一半被中断 → 再回来不知道从哪继续"；这个 Skill 就是专门解决这些问题的。它会自动探测你的项目环境（JDK、Spring Boot、ORM、数据库、前端框架），记在

下载

<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  arr[largest]) largest = left;
    if (right  arr[largest]) largest = right;

    if (largest == idx) break;
    swap(arr, idx, largest);
    idx = largest;
}

}

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 后落位，顺序已变
这种交换不依赖元素原始索引，仅由值大小和堆结构决定，无法保证相等键的先后关系