为什么选择排序不稳定？

Question

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

在每次迭代中，您会找到剩余数组中的最小元素。当找到这个最小值时，您可以选择您找到的第一个最小值，并且只在元素实际上小于它时才更新它。因此，在每次迭代中选择的元素是第一个最小值 - 这意味着，它是第一个按照以前的排序顺序。所以，就我的理解而言，当前的排序不会破坏以前排序在相同元素上生成的订单。

我错过了什么？

Answer 1

一个小例子：

令b = B在

< B>，< b>中，<一>，< C>（具有< b < C）

后一个循环顺序排序，但B和b的顺序已更改：

< a>，< b>，< B >，< c>

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

Answer 2

问题是选择排序将数组前面的元素交换到最小元素腾出的位置，这可能会扰乱排序的顺序。例如，假设我排序

(4, 0), (4, 1), (1, 0) 

选择排序第一交换的（1,0）到前：​​

(1, 0), (4, 1), (4, 0) 

而现在的（4,0）和（4,1）从他们从那里开始的地方没有秩序。按此顺序执行此操作将按此顺序保留元素，并且4个元素不按顺序排列。

希望这会有所帮助！

Answer 3

如果元素已经排序，稳定的方法不会进一步计算，但它计算到结束，因此它不稳定。