问为什么选择排序可以是稳定的或不稳定的

EN

在selection sort中，在每个“循环”结束时发生的交换可以更改具有相同值的项的相对顺序。

例如，假设您将4 2 3 4 1与selection sort排序。

第一个“循环”将遍历每个元素，寻找最小元素。它会发现1是最小元素。然后，它将把1交换到第一个位置。这将导致第一个点中的4个进入最后一个点：1 2 3 4 4

现在，4的相对顺序发生了变化。原始列表中的“第一个”4已移至其他4个之后的一个位置。

记住，稳定的定义是

保持具有相同值的元素的相对顺序。

selection sort的工作方式是在一组值中找到“最小”值，然后用第一个值交换它。

代码： 2，3，1，1#扫描0到n并找到“最小”值 1，3，2，1#用元素0交换“最少”。 1，3，2，1#扫描1到n并找到“最小”值 1，1，2，3#用元素1交换“最少”。 ...and等，直到排序。

若要使此值稳定，请插入“最少”值，而不是交换值。

代码： 2，3，1，1#扫描0到n并找到“最小”值 1，2，3，1#在pos 0处插入“至少”，将其他元素推回。 1，3，2，1#扫描1到n并找到“最小”值 1，1，2，3#在pos 1处插入“至少”，将其他元素推回。 ...and等，直到排序。

修改不稳定的选择排序算法使其变得稳定应该不会太难。

一般情况下-你说的不对。选择排序是unstable。这来自于它的定义。很明显，你和一个定制的案子混在一起了。

它可以是稳定的-通常，只有在linked lists。要做到这一点(经典的方式，O(1)内存)-而不是交换，最小元素必须链接到未排序的部分，使整个算法稳定。这就是“实现”的区别--显然，只有在这种情况下，由于数据结构的特殊性，才会产生稳定性。当选择排序为不稳定时，这与常见情况无关。

假设我有一个数组：

A = {3, 3, 1}

从位置0开始，选择排序将搜索最小值，并用最小值交换当前元素。对于A，我们用1交换第一个3，第二步什么也不做。

这是不稳定的，因为第一个3应该在第二个之前出现。如果使用链接列表而不是数组，并将元素插入正确的位置而不是交换，则选择排序是稳定的。