为什么选择排序不稳定？

Question

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

在每次迭代中,您都会在剩余的数组中找到最小元素.找到此最小值时,您可以选择找到的第一个最小值,并仅在元素实际小于它时更新它.因此,每次迭代时选择的元素是第一个最小值 - 意思是,它是先前排序顺序的第一个.因此,根据我的理解,当前排序不会破坏先前排序对相等元素生成的顺序.

我错过了什么？

Answer 1

一个小例子:

设b = B in

<B>,<b>,<a>,<C>(a <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)从它们开始排序的位置出现故障.运行此完成将按此顺序保留元素,并且4s无序.

希望这可以帮助!