为什么选择排序可能是稳定或不稳定 [英] Why Selection sort can be stable or unstable

问题描述

我知道选择排序可以实现为稳定或不稳定。但我不知道怎么会这样。我认为，排序算法只能稳定或仅不稳定。有人能解释一下吗？

I know that selection sort can be implemented as stable or unstable. But I wonder how it can be. I think sort algorithm can be only stable or only unstable. Can someone explain?

推荐答案

基本上在选择排序，交换发生在年底每一个圆可以改变相对为了具有相同价值的物品。

Basically in selection sort, swap that occurs at the end of each "round" can change the relative order of items having the same value.

例如，假设你排序 4 2 3 4 1 与选择排序。

第一个圆将逐一寻找最小元素的元素。它会发现1是最小元素。然后将交换1到第一点。这将导致4在第一点进入最后一个景点： 1 2 3 4 4

the first "round" will go through each element looking for the minimum element. it will find that 1 is the minimum element. then it will swap the 1 into the first spot. this will cause the 4 in the first spot to go into the last spot: 1 2 3 4 4

现在的4的相对顺序发生了变化。 第一4在原始列表已被移动到一个点的其它4后

now the relative order of the 4's has changed. the "first" 4 in the original list has been moved to a spot after the other 4.

记住稳定的定义是，

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

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

嗯，选择排序的工作原理的找到至少值在一组值，然后交换它与第一个值的

code：

2，3，1，1＃扫描0到n，找到至少值

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

1，3，2，1＃交换'至少'与元素0。

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

1，3，2，1＃扫描1到n，找到至少值

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

1，1，2，3＃掉'至少'与元素1。

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

...等等，直到它被排序。

...and so on until it is sorted.

为了使这个稳定的，而不是swaping值，将至少值，而不是的：

code：

2，3，1，1＃扫描0到n，找到至少值

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

1，2，3，1＃插入件至少在POS 0，推其他元素回

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

1，3，2，1＃扫描1到n，找到至少值

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

1，1，2，3＃插入至少在POS 1，推其他元素了。

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

...等等，直到它被排序。

...and so on until it is sorted.

这应该不是太难修改不稳定的选择排序算法趋于稳定。的

这篇关于为什么选择排序可能是稳定或不稳定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！