为什么选择排序不稳定？

Question

问题：I浏览了各种类型的列表，发现了一个非常有趣的所有类型稳定的图像。我不想问排序的稳定性意味着什么，因为它已经是answered.My问题了，selection 是如何不稳定的，因为它被广泛使用。

这里是排序的图像，它们的稳定性和复杂性：-

​

​

从图像中可以看到，最后一列为我们提供了每种类型的稳定性。

图片来源：-

otero/the-real-10-algorithms-that-dominate-our-world-e95fa9f16c04

我对快速排序和堆排序没有经验，但我习惯于选择排序，并在各种程序中使用它，从未发现过任何不稳定的行为。我知道，复杂明智的排序比选择排序要好得多，但实际工作是相同的，即按升序或降序排序和排列一组值，对吗?所以排序中的这种稳定性有点混乱，主要迫使我思考一种排序比另一种更稳定。

有人能解释我的不稳定行为和他们的稳定性如何不同的复杂性在这些分类？

Answer 1

使选择排序不稳定的是，交换一对元素的步骤可能会改变具有相同键的另一对元素的相对顺序。例如，在对数组排序时

2 2' 1

由于具有最小键的元素为1，因此必须将其推送到数组的最低位置，方法是用2交换1：

1 2' 2

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

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