CSP-S 提高级 · CSP 2021 提高级第一轮 第 4 题

以下排序方法中，（ ）是不稳定的。

这题考排序稳定性，拿到题先想：稳定性定义是相等元素相对顺序不变。再看算法过程，插入、冒泡、归并都是相邻操作或有序合并，只有堆排序建堆时父子远距离交换，直接锁定答案。

很多学生死记'快选堆希'口诀却忘了推导，容易在堆排序和归并排序上混淆；有的把'稳定'理解成性能稳定，以为堆排序快所以稳定，这是概念偷换；还有学生看到冒泡排序交换次数多，误以为会打乱相等元素，其实冒泡只在不等时才换，相等时相对位置天然保持。

考察知识点

排序基础、排序算法稳定性、堆排序原理

概念定义

• 排序的稳定性：如果排序前 $a_i = a_j$ 且 $i < j$，排序后 $a_i$ 仍然在 $a_j$ 之前，则称该排序算法是稳定的；否则是不稳定的。
• 插入排序：将元素插入已排序序列的合适位置，遇到相等元素时插入在其后面→稳定。
• 冒泡排序：相邻元素比较交换，相等时不交换→稳定。
• 堆排序：建堆和调整过程中进行远距离交换，相等元素的相对顺序无法保证→不稳定。
• 归并排序：合并时遇到相等元素优先取左半部分→稳定。