爲什麼選擇排序不穩定？

Question

這可能是微不足道的，但我不明白爲什麼Selection Sort的默認實現不穩定？

在每次迭代中，您會找到剩餘數組中的最小元素。當找到這個最小值時，您可以選擇您找到的第一個最小值，並且只在元素實際上小於它時才更新它。因此，在每次迭代中選擇的元素是第一個最小值 - 這意味着，它是第一個按照以前的排序順序。所以，就我的理解而言，當前的排序不會破壞以前排序在相同元素上生成的訂單。

我錯過了什麼？

Answer 1

一個小例子：

令b = B在

< B>，< b>中，<一>，< C>（具有< b < C）

後一個循環順序排序，但B和b的順序已更改：

< a>，< b>，< B >，< c>

但是，你可以實現選擇排序穩定，如果你，而不是切換，插入最小值。但爲了提高效率，您應該有一個支持低成本插入的數據結構，否則最終會出現二次複雜性。

Answer 2

問題是選擇排序將數組前面的元素交換到最小元素騰出的位置，這可能會擾亂排序的順序。例如，假設我排序

(4, 0), (4, 1), (1, 0) 

選擇排序第一交換的（1,0）到前：​​

(1, 0), (4, 1), (4, 0) 

而現在的（4,0）和（4,1）從他們從那裏開始的地方沒有秩序。按此順序執行此操作將按此順序保留元素，並且4個元素不按順序排列。

希望這會有所幫助！

Answer 3

如果元素已經排序，穩定的方法不會進一步計算，但它計算到結束，因此它不穩定。