CSP-J 2022 第一轮 第 12 题：排序算法稳定性说法错误的是

题目

以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

选项

• A. 冒泡排序算法是稳定的
• B. 简单选择排序是稳定的
• C. 简单插入排序是稳定的
• D. 归并排序算法是稳定的

答案

B

题解

答案是 B：简单选择排序是稳定的，这个说法错误。

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

简单选择排序每一轮找到最小元素，再与当前待排序区间的第一个元素交换。这个交换可能改变相同元素的相对顺序。例如：

``text 原序列：3ₐ 3ᵦ 1 第一轮：1 3ᵦ 3ₐ ``

这里 3ₐ 和 3ᵦ 的数值都是 3，下标只是用来区分它们。第一轮将 1 与 3ₐ 交换后，两个 3 的先后顺序颠倒了，所以简单选择排序不稳定。

其余算法的常见实现都是稳定的：

• 冒泡排序：只有前一个元素大于后一个时才交换，相等时不交换。
• 简单插入排序：只向后移动比待插入元素大的元素，不越过相等元素。
• 归并排序：合并时遇到相等元素，优先取左侧的元素，保持原有顺序。