1. 引言
如果一个排序算法在对多个具有相同键值的记录排序后，仍能保持它们在原始数组中的相对顺序，那么该排序算法就是稳定的。
稳定的排序算法在许多重要场景中非常关键，例如基数排序（Radix Sort）就依赖于排序的稳定性。
本文将通过一个反例说明：堆排序（Heapsort）虽然是一个高效算法（时间复杂度为 O(n log n)），但它并不稳定。
2. 理解排序稳定性
我们以一个包含多个元组的数组为例：
[(72, bob), (89, jim), (77, alice), (90, tom), (63, sam), (55, jill), (89, emma)]
每个元组可以理解为（成绩，姓名）。我们按“成绩”进行排序：
✅ 稳定排序结果应为：
[(55, jill), (63, sam), (72, bob), (77, alice), (89, jim), (89, emma), (90, tom)]
⚠️ 注意：虽然 (89, emma) 和 (89, jim) 按字母顺序可能更自然地排成 (89, emma) 在前，但排序仅依据“成绩”这个键，不考虑“姓名”。
因此，在稳定排序中，jim 应该排在 emma 前面，因为它们在原始数组中就是这个顺序。
3. 堆排序简介
堆排序是一种基于堆结构的比较排序算法，其核心步骤如下：
- 将输入数组构造成一个最大堆（Max-Heap）
- 重复以下操作 n 次：
- 将堆顶元素与堆的最后一个元素交换
- 对剩余堆进行 sift-down（下滤） 操作，恢复堆性质
最终数组将被排序为升序。
堆排序不需要额外的二叉树结构，所有操作都在原数组上完成。
4. 堆排序为何不稳定？
我们继续使用前面的元组数组作为例子，验证堆排序是否保持稳定性。
输入数组为：
A = [(72, bob), (89, jim), (77, alice), (90, tom), (63, sam), (55, jill), (89, emma)]
数组索引为 1~7（从 1 开始）。
4.1. 构建最大堆
我们构建最大堆后，堆顶元素为 (90, tom)：
将其与最后一个元素 (89, emma) 交换，此时 (90, tom) 被放到最终位置：
4.2. 使用 sift-down 修复堆
此时堆结构被破坏，(55, jill) 的键小于其子节点。我们使用 sift-down 操作将其修复：
修复后，堆顶为 (89, jim)。再次交换堆顶和最后一个元素：
4.3. 继续堆修复过程
继续对剩下的堆进行 sift-down 操作：
将堆顶 (89, emma) 与最后一个元素 (55, jill) 交换：
此时，我们已经可以观察到最终排序结果的一部分：
[(...), ..., (89, emma), (89, jim), (90, tom)]
⚠️ 问题出现了：在原始数组中，jim 出现在 emma 前面；但在排序结果中，emma 却排在了前面。
这说明堆排序破坏了原始的相对顺序，因此：
✅ 堆排序是不稳定的排序算法。
5. 总结
堆排序是一种高效的排序算法，具有 O(n log n) 的时间复杂度。然而，它并不保证相同键值元素在排序后的相对位置不变，因此不具备稳定性。
要判断排序算法是否稳定，不能仅看数值排序结果，而应从记录的角度出发，考虑多个字段中仅按一个字段排序时的行为。
在实际开发中，如果你需要保持记录顺序，应避免使用堆排序，而选择归并排序等稳定排序算法。