選擇排序 - 穩定

Question

我讀到，而不是交換，我們可以插入更改選擇排序到穩定的排序。我在網上獲得了以下實現。

 void selection (int a[], int n) 

    { 
while (--n > 0) { 
    int i, max = n; 

    for (i = 0; i < n; i++) { 
     if (a[i] >= a[max]) 
     max = i; 
    } 

    if (max != n) { 
     int save = a[max]; 

     for (i = max; i < n; i++) 
     a[i] = a[i + 1]; 

     a[n] = save; 
    } 
} 
} 

我不明白這是如何將是下一個穩定的排序： （1,0），（2,0），（5,0），（4,0），（5,1 ）

我認爲上述的實施將給 （1,0），（2,0），（4,0），（5,1），（5,0）

我沒有看到這是一個穩定的行爲，因爲我明白這一點。我對麼。如果是這樣，我怎麼能實現穩定的選擇排序。

下面的代碼在更改時會給我們一個穩定的選擇排序。糾正我，如果我錯了。

for (i = 0; i < n; i++) { 
    if (a[i] >= a[max]) 
    max = i; 
} 

該行不會給我們想要的結果，我認爲，在這種情況下，它不會給我的數據排序的穩定結果。我認爲下面的代碼會很好。

for (i = 0; i <= n; i++) { 
    if (a[i] >= a[max]) 
    max = i; 
} 

如果我錯了，糾正我？

謝謝

Answer 1

您發佈的代碼似乎是一個穩定的排序。

在選擇循環中，將始終選擇出現最大值的最後。這是因爲條件爲a[i] >= a[max]而不是a[i] > a[max]。

for (i = 0; i < n; i++) { 
    if (a[i] >= a[max]) 
    max = i; 
} 

然後將選定的元素放置在結尾處（穩定排序應該放在該處）。其餘元素的順序不變，因爲它們全部被移動而不是交換。這保證了具有相同值的元素將保持相同的順序，即穩定的排序。