algorithm - 为什么选择排序不稳定？

Question

这可能是微不足道的，但我不明白为什么 Selection Sort 的默认实现不稳定？

在每次迭代中，您都会找到剩余数组中的最小元素。当找到这个最小值时，你可以选择你找到的第一个最小值，只有当一个元素实际小于它时才更新它。因此，在每次迭代中选择的元素是第一个最小值——这意味着，它在前一个排序顺序中排在第一位。因此，据我所知，当前排序不会破坏先前排序对相等元素生成的顺序。

我错过了什么？

Answer 1

一个小例子:

令 b = B 在

< B > , < b > , < a > , < C >(带有 < b < c)

在一个循环之后序列被排序但是 B 和 b 的顺序发生了变化:

, , ,

但是，如果您插入最小值而不是切换，则可以实现稳定的选择排序。但是为了提高效率，您应该拥有一个支持低成本插入的数据结构，否则您最终会遇到二次复杂度。