GESP 八级 · GESP202609 C++ 八级 第 20 题

堆排序是一种稳定的排序算法。

堆排序通过构建大顶堆/小顶堆实现排序，过程中涉及大量元素交换。稳定性要求相等元素相对位置不变，但堆调整时父节点与子节点交换会打乱同值元素顺序，故堆排序不稳定。

易误判为稳定，因堆排序整体有序，忽略局部交换对同值元素的影响；或混淆稳定排序（如归并、冒泡）与不稳定排序（如快速、堆）。

1. 考纲定位

本题考查《GESP 考试大纲》八级"排序算法"模块中关于排序稳定性的判定。命题人专门设置此题，卡住的是考生对"稳定性"概念的理解深度——多数考生能记住堆排序是 O(n log n) 且原地排序，却忽略了稳定性这一关键属性，导致在需要稳定排序的场景下误用堆排序。

2. 解题思维

稳定性定义：相等元素的相对位置在排序后保持不变。堆排序的核心步骤是构建堆后反复将堆顶与末尾元素交换，再重新调整堆。这个"交换"操作是破坏稳定性的根源——当存在多个相等值时，它们在堆调整过程中可能被任意交换。

以数组 [5, 3, 5, 2] 为例：初始堆顶为第一个 5，与末尾的 2 交换后，两个 5 的相对位置已改变。后续调整中它们还可能再次被交换。因此，无论堆排序如何优化，都无法保证同值元素顺序不变。