c - 选择排序——稳定

Question

我读到，我们可以插入以将选择排序更改为稳定排序，而不是交换。我在网上得到了以下相同的实现。

void selection ( int a[], int n ) {
    while ( --n > 0 ) {
        int i, max = n;

        for ( i = 0; i < n; i++ ) {
            if ( a[i] >= a[max] )
                max = i;
        }

        if ( max != n ) {
            int save = a[max];

            for ( i = max; i < n; i++ )
                a[i] = a[i + 1];

            a[n] = save;
        }
    }
}

我不明白这如何成为以下内容的稳定排序: (1,0), (2,0), (5,0), (4,0), (5,1)

我认为上面提到的实现会给出 (1,0), (2,0), (4,0), (5,1), (5,0)

据我所知，我不认为这是一种稳定的行为。我对么。如果是这样，我怎样才能实现稳定的选择排序。

更改后的以下代码将为我们提供稳定的选择排序。如果我错了，请纠正我。

    for ( i = 0; i < n; i++ ) {
        if ( a[i] >= a[max] )
        max = i;
    }

我认为那条线不会给我们想要的结果，在这种情况下，它不会为我提供的用于排序的数据提供稳定的结果。我认为下面的代码会很好。

    for ( i = 0; i <= n; i++ ) {
        if ( a[i] >= a[max] )
        max = i;
    }

如果我错了，请纠正我？

谢谢

Answer 1

您发布的代码似乎是一种稳定的排序。

在选择循环中，将始终选择最大值的最后 次出现。这是因为条件说的是 a[i] >= a[max] 而不是 a[i] > a[max]。

for ( i = 0; i < n; i++ ) {
    if ( a[i] >= a[max] )
    max = i;
}

然后将选中的元素放在末尾(稳定排序应该放的地方)。其余元素的顺序没有改变，因为它们都是移动的而不是交换的。这保证了具有相同值的元素将保持相同的顺序，即稳定排序。