重复选择排序行为

Question

选择排序如何处理数组中的重复值？我很难在网上找到答案。

如果我有一个像[8，4，7，3，9，3]这样的数组，那么哪个索引将选择排序选择与数组的第一遍交换？

第三个索引还是第五个索引？

Answer 1

尽管您在3中交换的具体问题很容易回答，但更通用的版本并不容易，因为选择类别不是稳定。

经典实施将挑3第三索引处，因为下一个元件拾取到交换条件是

if (a[i] < a[iMin]) 

一旦第一3被交换到位置0，第二个3在索引5不会被选中。

该条件意味着最早的重复将根据算法当前通过之前的排列来选择。不过，这种安排可能与元素的初始安排不一样。

只要进一步向下复制选择过程，就不能保证，因为较小的数字可以在它们之前交换。

例如，在此初始排列

[3, 3, 1] 

的3索引零将被最后拾取，因为在第一次迭代将其移动一路到数组的末尾。

Answer 2

它取决于实施。 但是，通常情况下，循环将开始从左到右扫描并将获得第一个3。

但我怎么说thare不是一个标准。

这是根据本Wikipedia一个可能的实现：

procedure SelectionSort(a: list to sorts); 
    for i = 1 to n - 1 
    posmin ← i 
    for j = (i + 1) to n 
     if a[j] < a[posmin] 
     posmin ← j 
    tmp ← a[i] 
    a[i] ← a[posmin] 
    a[posmin] ← tmp