为什么选择排序不稳定？

Question

问题: 我正在查看各种类型的列表,并找到了一个非常有趣的所有排序稳定性的图像.我不会问排序的稳定性意味着什么,因为它已经被回答.我的问题是如何选择排序,是不稳定的因为它被广泛使用.

以下是各种形象及其稳定性和复杂性: -

从图像中可以看出,最后一列为我们提供了这些种类的稳定性.

图片来源: -

https://medium.com/@_marcos_otero/the-real-10-algorithms-that-dominate-our-world-e95fa9f16c04

我没有快速和heapsort的经验,但我习惯于选择排序并在各种程序中使用它,从未发现任何不稳定的行为.我知道复杂明智的bubblesort远比选择排序好但是实际的工作是相同的是按照升序还是降序对一组值进行排序和排序？所以这种排序的稳定性有点令人困惑,主要是让我想到一种值比另一种更稳定.

任何人都可以向我解释不稳定的行为以及他们的稳定性在这些排序中的复杂程度如何不同？

Answer 1

选择排序不稳定的原因是交换一对元素的步骤可能会改变具有相同键的另一对元素的相对顺序.例如,在对数组进行排序时

2 2' 1

因为具有最小键的元素是1,所以你必须通过用2交换1将它推到数组的最低位置:

1 2' 2

用2交换1改变了两个相等元素(2'和2)的相对顺序.

也就是说,具有相同键的两个元素在排序输出中的出现顺序与它们在输入数组中出现的顺序不同.因此,选择排序不稳定.