堆排序不是稳定排序。

✅ 什么是“稳定排序”？
一个排序算法是稳定的，当且仅当：
对于任意两个关键字相等的元素，排序后它们的相对顺序与排序前保持一致。

例如：
原始数组中有两个 5，记为 5ₐ（在前）和 5ᵦ（在后）。
如果排序后 5ₐ 仍然在 5ᵦ 前面 → 稳定；
如果变成了 5ᵦ 在 5ₐ 前面 → 不稳定。

❌ 为什么堆排序不稳定？

堆排序在以下两个操作中可能改变相等元素的相对位置：

1. 建堆过程中的交换

• 在自底向上调整堆时，父节点和子节点之间会交换。
• 如果有相等元素分布在不同子树中，交换可能导致它们的相对顺序颠倒。

2. 排序阶段的堆顶与末尾交换

• 每次将堆顶（最大值）与当前堆的最后一个元素交换。
• 这个“末尾元素”可能是一个与堆中其他相等元素原本靠前的元素，被直接扔到后面，破坏稳定性。

🔍 举个反例（经典例子）

原始数组（用下标区分相同值）：
[5, 4ₐ, 3, 2, 4ᵦ, 1]

其中 4ₐ 在 4ᵦ 前面。

步骤 1：建大顶堆
数组会被调整为（一种可能的大顶堆结构）：
[5, 4ₐ, 3, 2, 4ᵦ, 1] → 建堆后可能变成 → [5, 4ₐ, 3, 2, 4ᵦ, 1]

（此时还没问题）

步骤 2：第一次排序

• 交换堆顶 5 和末尾 1 → [1, 4ₐ, 3, 2, 4ᵦ, 5]
• 对前 5 个元素 sift_down：1 下沉，与 4ₐ 交换 → [4ₐ, 1, 3, 2, 4ᵦ, 5]

步骤 3：第二次排序

• 交换堆顶 4ₐ 和当前末尾 4ᵦ → [4ᵦ, 1, 3, 2, 4ₐ, 5]
• 现在 4ᵦ 跑到了 4ₐ 前面！

最终排序结果（升序）：
[1, 2, 3, 4ᵦ, 4ₐ, 5]

→ 4ₐ 和 4ᵦ 的相对顺序被颠倒了！

✅ 这就证明了堆排序不保证稳定性。

📌 补充说明
排序算法 是否稳定
冒泡排序 ✅ 是
插入排序 ✅ 是
归并排序 ✅ 是
基数排序 ✅ 是
堆排序 ❌ 否
快速排序 ❌ 否
希尔排序 ❌ 否
选择排序 ❌ 否

💡 口诀：“一堆希尔快选” —— 都不稳定
（堆、希尔、快排、选择）

✅ 如果你需要“稳定 + O(n log n)”
请使用 归并排序（稳定，O(n log n) 时间，O(n) 空间）
或对堆排序进行改造（如在比较时加入原始下标作为第二关键字），但这已不是标准堆排序。

✅ 总结

堆排序不是稳定排序，因为在建堆和交换堆顶的过程中，相等元素的相对位置可能被改变。
如果你的应用场景要求稳定性（如多关键字排序、保持输入顺序等），不要使用堆排序。

如有需要，我可以展示如何用“带索引的元组”让堆排序“模拟稳定”，但那属于工程技巧，而非算法本身的性质。