选择排序。如何做选择排序作为稳定的算法？

我有这种选择排序算法的障碍。如何做到稳定这个实现？我认为它不可能/选择排序。如何做选择排序作为稳定的算法？

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

选择排序。如何做选择排序作为稳定的算法？

回答

相关问题