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

Question

我知道selection sort可以实现稳定或不稳定.但我想知道它是怎么回事.我认为排序算法只能稳定或只是不稳定.谁能解释一下？

Answer 1

基本上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交换"最少".

...等等,直到它被分类.

要使其稳定,而不是交换值,请插入"最小"值:

码:

2,3,1,1#扫描0到n并找到"最小"值

1,2,3,1#在'0'插入"最少",推回其他元素.

1,3,2,1#扫描1到n并找到"最小"值

1,1,2,3#在pos 1处插入'least',将其他元素推回.

...等等,直到它被分类.

修改不稳定的选择排序算法以保持稳定不应该太难.

Answer 2

通常情况下 - 你不正确.选择排序不稳定.这来自它的定义.所以,你显然对一个自定义案例感到困惑.

它可以是稳定的 - 通常只有链表.要做到这一点(经典的方式,O(1)内存) - 而不是交换,最小元素必须链接到未排序的部分,使整个算法稳定.这就是"实施"的不同之处 - 显然,由于数据结构的具体情况,这种情况只能在这种情况下产生稳定性.当选择排序不稳定时,它与常见情况无关

Answer 3

假设我有这个数组：

A = {3, 3, 1}

从位置0开始，选择排序将搜索最小值，并将当前元素替换为最小值。对于A，我们将第一个3与交换1，而在第二个步骤中不执行任何操作。

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