1

我有选择排序算法的这种实现。如何使这个实现稳定？我觉得不可能/

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

2 回答 2

0

Taken straight from wikipedia:

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.

So basically you do have a stable sort, since you are always swapping a value that is less then the minimum value (as opposed to less then or EQUAL to the value).

于 2012-10-28T20:02:04.157 回答
0

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

如果你想要一个稳定的排序，你必须：

  • 像您已经做的那样从剩余列表中选择最小元素
  • 将其插入到位i而不交换。这意味着将剩余的元素向右移动，以便为i您放置的第 th 个元素腾出空间。

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

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

于 2012-10-28T19:58:27.533 回答