排序算法的稳定性

首先，回顾一下稳定排序的定义：

• 如果一个排序算法在排序后能保持相等元素的原始相对顺序，则该算法是稳定的。

• 反之，如果相等元素的相对顺序可能被改变，则该算法是不稳定的。

稳定排序如:插入排序，基数排序，归并排序，冒泡排序，计数排序。

不稳定排序不稳定的排序算法有: 快速排序 (相同会交换)，希尔排序，简单选择排序，堆排序。

分析各排序算法的稳定性

1. 冒泡排序（Bubble Sort）

• 工作原理：重复遍历数组，比较相邻元素，如果顺序错误就交换。

• 稳定性：

• 只有在前一个元素严格大于后一个元素时才交换，相等时不交换。

• 因此，相等元素的相对顺序不会改变。

• 结论：稳定。

2. 选择排序（Selection Sort）

• 工作原理：每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。

• 稳定性问题：

• 假设数组中有多个相等的元素，比如 [5, 5', 2]（5 和 5' 是相等的，但带标记以区分顺序）。

• 第一轮选择最小的 2，并与第一个 5 交换，得到 [2, 5', 5]。

• 此时 5' 和 5 的相对顺序改变了（原本 5' 在 5 前面，现在在后面）。

• 结论：不稳定。

3. 插入排序（Insertion Sort）

• 工作原理：将未排序部分的元素逐个插入到已排序部分的正确位置。

• 稳定性：

• 插入时，如果遇到相等的元素，会插入到它们的后面（因为通常实现是 while (arr[j] > key) 时才移动，相等时不移动）。

• 因此，相等元素的相对顺序不会改变。

• 结论：稳定。

4. 归并排序（Merge Sort）

• 工作原理：分治法，递归地将数组分成两半分别排序，然后合并两个有序数组。

• 稳定性：

• 合并时，如果两个子数组的元素相等，通常会先取左子数组的元素（因为实现通常是 if (left[i] <= right[j])）。

• 因此，相等元素的相对顺序不会改变。

• 结论：稳定。

验证不稳定性的例子

以选择排序为例：

• 初始数组：[5, 5', 2]（5 和 5' 值相等，但带标记以区分顺序）。

• 第一轮：选择最小的 2，与第一个 5 交换 → [2, 5', 5]。

• 此时 5' 和 5 的顺序颠倒，说明不稳定。

其他排序算法的稳定性补充

• 快速排序（虽然本题未问）：通常是不稳定的，因为分区时可能改变相等元素的顺序。

• 堆排序：不稳定，因为堆的调整可能改变相等元素的顺序。

总结

在题目给出的四种排序算法中：

• 不稳定的排序算法：选择排序。

• 其他（冒泡、插入、归并）都是稳定的。

最终答案

选择排序是不稳定的排序算法。