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

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

直接摘自维基百科:

Selection sort can be implemented as a stable sort. If, rather than swapping in step 2, the minimum value is inserted into the first position (that is, all intervening items moved down), the algorithm is stable. However, this modification either requires a data structure that supports efficient insertions or deletions, such as a linked list, or it leads to performing Θ(n2) writes.

所以基本上你确实有一个稳定的排序，因为你总是交换一个小于最小值的值(而不是小于或等于该值)。