CSP-S 2021 第一轮 第4题：以下排序方法中，（）是不稳定的。

题目

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

选项

• A. 插入排序
• B. 冒泡排序
• C. 堆排序
• D. 归并排序

答案

C

题解

答案是 C. 堆排序。

稳定性是指：排序前后，关键字相同的元素，其相对顺序是否保持不变。

例如，两个数值相同的元素记作 2₁、2₂，原序列为： [2₁, 2₂, 1]

堆排序中，交换堆顶与末尾元素后得到 [1, 2₂, 2₁]，再调整并完成排序，最终得到： [1, 2₂, 2₁]

两个 2 的相对顺序变了，所以堆排序不稳定。

按通常的实现，插入排序、冒泡排序、归并排序都是稳定的。