arrays - 为什么选择排序可以稳定或不稳定

Question

我知道选择排序可以实现为稳定的或不稳定的。但我想知道它怎么可能。我认为排序算法只能是稳定的或者只能是不稳定的。谁能解释一下？

Answer 1

基本上在选择排序中，在每个“轮”结束时发生的交换可以改变具有相同值的项目的相对顺序。

例如，假设您使用选择排序对4 2 3 4 1进行了排序。

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

现在 4 的相对顺序已经改变。原始列表中的“前”4 个已移至其他 4 个之后的位置。

记住稳定的定义是

the relative order of elements with the same value is maintained.

好吧，选择排序 的工作原理是在一组值中找到“最小”值，然后将其与第一个值交换:

Code:

2, 3, 1, 1 # scan 0 to n and find 'least' value

1, 3, 2, 1 # swap 'least' with element 0.

1, 3, 2, 1 # scan 1 to n and find 'least' value

1, 1, 2, 3 # swap 'least' with element 1.

...and so on until it is sorted.

为了使其稳定，而不是交换值，而是插入“最小”值:

Code:

2, 3, 1, 1 # scan 0 to n and find 'least' value

1, 2, 3, 1 # insert 'least' at pos 0, pushing other elements back.

1, 3, 2, 1 # scan 1 to n and find 'least' value

1, 1, 2, 3 # insert 'least' at pos 1, pushing other elements back.

...and so on until it is sorted.

将不稳定的选择排序算法修改为稳定应该不会太难。