选择排序.如何进行选择作为稳定算法

Question

我具有选择排序算法的这种影响。如何将此实现作为稳定？我认为不可能/

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;
}

Answer 1

直接从Wikipedia拿走：

选择排序可以作为稳定的排序实现。如果将最小值插入第一个位置（即，所有中间项目向下移动）而不是交换步骤2，则该算法是稳定的。但是，此修改需要支持有效插入或删除（例如链接列表）的数据结构，或者导致执行θ（n2）写入。

因此，基本上您确实有稳定的排序，因为您总是换成最小值较小的值（而不是较少或等于值）。

Answer 2

您的实现不是稳定的。在每次迭代中，您将元素处于数组中的位置i，并将其放在其余数组中的任意位置，因此您弄乱了原始订单。

如果您想要稳定的排序，则必须：

• 按照您已经完成的剩余列表，选择最小元素
• 插入它在i的位置而无需交换。这意味着将剩余元素移至您要放置的i元素的空间的权利。

这可以确保具有相同值的元素在相同顺序中放置在排序的数组和原始数组中。

（感谢Groo在评论中指出错误）