1. 简介
在本文中，我们将探讨 [Selection Sort（选择排序）] 是否是一种 稳定排序算法。
2. 什么是稳定排序算法？
✅ 稳定排序算法 在排序过程中 保留相等元素的相对顺序。
举个例子，假设我们有一个数组 a，其中 a[1] == a[4]。如果排序后，a[1] 仍然在 a[4] 前面，则该算法是稳定的。
2.1. 示例
假设我们要对以下字符串数组进行排序：
[Dog（蓝色）, Mouse, Dog（红色）, Cat]
其中有两个相等的元素：蓝色 Dog 和红色 Dog。一个稳定排序算法应该保持它们在输入中的相对顺序，即蓝色在前。
排序后结果应为：
[Cat, Dog（蓝色）, Dog（红色）, Mouse]
那么问题来了：Selection Sort 是否能做到这一点？它是稳定还是不稳定的排序算法？
3. 标准 Selection Sort 是不稳定的
下面是标准 Selection Sort 的伪代码：
algorithm SelectionSort(a, n):
for i <- 1 to n:
j_min <- i
for j <- i to n:
if a[j] < a[j_min]:
j_min <- j
if i != j_min:
swap a[i] and a[j_min]
它通过不断将 a[i..n] 中的最小元素交换到 a[i] 的位置来实现排序。但 这种交换可能会破坏相等元素的相对顺序。
3.1. 示例
我们再次使用上面的动物数组进行演示：
初始数组：
[Dog（蓝色）, Mouse, Dog（红色）, Cat]
- 第一次迭代：找到最小元素
Cat，与第一个元素Dog（蓝色）交换，数组变为：
[Cat, Mouse, Dog（红色）, Dog（蓝色）]
- 第二次迭代：找到
Dog（红色），与Mouse交换：
[Cat, Dog（红色）, Mouse, Dog（蓝色）]
- 第三次迭代：发现
Dog（蓝色） < Mouse，再次交换：
[Cat, Dog（红色）, Dog（蓝色）, Mouse]
⚠️ 注意： 此时 Dog（红色） 被排在了 Dog（蓝色） 前面，破坏了它们在原始数组中的相对顺序。
✅ 结论：标准 Selection Sort 是不稳定的。
4. 能否构造一个稳定的 Selection Sort 变体？
可以。如果我们 不直接交换最小元素和当前位置，而是将其插入到正确位置，并将中间元素整体后移，就可以保持相等元素的相对顺序。
4.1. 示例
用新算法重新排序：
初始数组：
[Dog（蓝色）, Mouse, Dog（红色）, Cat]
- 第一次迭代：找到
Cat，插入到第一位，数组变为：
[Cat, Dog（蓝色）, Mouse, Dog（红色）]
第二次迭代：
Dog（蓝色）已经是当前最小，无需操作。第三次迭代：找到
Dog（红色），插入到Mouse前：
[Cat, Dog（蓝色）, Dog（红色）, Mouse]
✅ 结果：相等元素顺序未变，排序稳定。
4.2. 伪代码实现
algorithm StableSelectionSort(a, n):
for i <- 1 to n:
j_min <- i
for j <- i to n:
if a[j] < a[j_min]:
j_min <- j
if i != j_min:
temp <- a[j_min]
for j <- j_min downto i + 1:
a[j] <- a[j-1]
a[i] <- temp
4.3. 这算是 Selection Sort 吗？
这个问题存在争议：
- ❌ 否定观点：标准 Selection Sort 只有交换操作，没有插入和位移，因此这种变体不属于 Selection Sort。
- ✅ 肯定观点：其核心思想仍然是“逐步构建有序子数组”，只是实现方式不同，因此可以视为 Selection Sort 的稳定变体。
4.4. 数组 vs 链表
⚠️ 数组实现：插入操作需要频繁位移，时间复杂度为 O(n²)，效率较低。
✅ 链表实现：只需调整指针，无需移动元素，更适合稳定 Selection Sort 的实现。
例如，将 a[i-1] 指向 a[j_min]，再将 a[j_min] 指向 a[i]，即可完成插入。
5. 总结
| 要点 | 内容 |
|---|---|
| ✅ 标准 Selection Sort | 不稳定 |
| ✅ 稳定变体实现方式 | 插入 + 位移（数组）或指针调整（链表） |
| ⚠️ 时间复杂度 | 仍为 O(n²)，但实际效率受插入操作影响 |
| ✅ 是否属于 Selection Sort | 视核心思想而定，可视为变体 |
✅ 结论：标准 Selection Sort 不稳定，但可以通过插入方式实现稳定版本，尤其适合在链表上实现。