重複選擇排序行爲

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