選擇排序。如何做選擇排序作爲穩定的算法？

我有這種選擇排序算法的障礙。如何做到穩定這個實現？我認爲它不可能/選擇排序。如何做選擇排序作爲穩定的算法？

int selection_sort1 (int ai_numbers[], const int ci_count) 
{ 
    int counter = 0; 
    int i, minIndex, j; 

    for (i = 0; i < ci_count; i++) 
    { 
     minIndex = i; 
     for (j = i + 1; j < ci_count; j++) 
     { 
      if (ai_numbers[j] < ai_numbers[minIndex]) 
      { 
       minIndex = j; 
      } 
     } 
     swap (&ai_numbers[i], &ai_numbers[minIndex]); 
     counter++; 
    } 


    return counter; 
}

來源

2012-10-28 user1779502

排序int []不需要穩定的排序。根本不可觀察到使用了不穩定的排序。 –

你實現並不穩定。在每次迭代中，您將數組中的位置爲i的元素放在剩餘數組中的任意位置，以便將原始順序搞亂。

如果你想有一個穩定的排序，你必須：

選擇來回其餘列表中的最小元素，你已經做
插入它在地方i沒有交換。這意味着將其餘元素向右移動以爲您要放置的元素留出空間。

這確保具有相同值的元件被放置在相同的順序所述排序後的數組中和原始數組英寸

（感謝Groo在徵求意見指出錯誤）

來源

2012-10-28 19:58:27 alestanis

它不會穩定，因爲與您發現的物品交換的物品將以任意位置結束。 – Groo

從維基百科直摘自：

選擇排序可以實現爲一個穩定的排序。如果不是在步驟2中交換，而是將最小值插入到第一個位置（即所有插入的項目向下移動），則該算法是穩定的。但是，此修改要麼需要支持有效插入或刪除的數據結構（例如鏈接列表），要麼導致執行Θ（n2）寫入。

所以基本上你有一個穩定的排序，因爲你總是換一個值，該值是小於最小值（相對於小於或等於該值）。

來源

2012-10-28 20:02:04 wardd

選擇排序。如何做選擇排序作爲穩定的算法？

回答

相關問題