选择排序稳定

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

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