選擇算法是否穩定？

Question

我有一個與選擇排序算法有關的問題。

我有這個列表，每個項目都有一個名字和一個年齡。

（（湯姆·20）（鮑勃10）（八30）（蘇10））

如果我們排序年齡列表（順序遞增）。我們可以得到下面的列表中的任一。

（（鮑勃10）（蘇10）（湯姆20）（專利30）） OR （（蘇10）（鮑勃10）（湯姆20）（專利30））

這裏是方法給出

public static void selectionSort(int [] arr) 
{ 
    final int n=arr.length; 
    int least,temp; 

    for(int i=0; i<n; i++) 
    { 
     least=i; 

     for(int j=i; j<n; j++)    
      if(arr[j]<=arr[least]) 
      least=j; 


     temp=arr[i]; 
     arr[i]=arr[least]; 
     arr[least]=temp; 
    } 
} 

問題是算法穩定與否？如果它是穩定的，如何使它不穩定？

如果不穩定，如何使其穩定？

我發現這個列表並不穩定。 我是否正確？ 如果我錯了，有人可以向我解釋嗎？ 謝謝

Answer 1

對不起方法頭是 公共靜態無效選擇排序（INT [] ARR） { INT至少，溫度; final int n = arr.length;

其餘的都在上面。

Answer 2

穩定的排序是保留輸入集合的原始順序的排序，其中比較算法不區分兩個或更多項目。

在你的例子中，這意味着Bob總是會在Sue之前出現，因爲這是輸入集的原始順序。

當兩個元素相等時，不穩定的算法表現出未定義的行爲，但有時可能保留順序是完全可能的。

由於行爲是未定義的，即您每次運行它都會得到不同的bob命令和起訴，所以確實會不穩定。

Answer 3

@mikefaheysd更快，所以我不會重複他所解釋的。我只是根據你的代碼添加一些解釋。

你需要弄清楚的是當對象相等時方法的行爲是什麼。目前，它是不穩定的，因爲你用這個：

if(arr[j]<=arr[least]) 
    least=j; 

假設在某個時刻鮑勃的指數是least（因爲他是先輸入數組中）。當蘇來時，她的指數現在將爲least，因爲您使用<=進行比較。 Sue將在Bob之前被移動，並且他們的相對順序將會改變。

現在，如果將比較結果更改爲<，則會有穩定的排序，因爲認爲兩個對象不會改變相對位置。