按特定顺序排列整数

Question

给定一组不同的未排序整数s1,s2,..,sn如何排列整数,使得s1 <s2> s3 <s4 ...

我知道这可以通过从左到右查看数组来解决,如果不满足条件则交换这两个元素会得到正确的答案.有人可以解释为什么这个算法有效.

Answer 1

给定阵列中任意三个连续数字,有四种可能的关系:

a < b < c
a < b > c
a > b < c
a > b > c

在第一种情况下,我们知道a <c.由于满足第一个条件,我们可以交换b和c以满足第二个条件,并且仍然满足第一个条件.

在第二种情况下,两个条件都已满足.

在第三种情况下,我们必须交换a和b来给b <a？C.但是我们已经知道b <c,所以如果<c然后交换以满足第二个条件并不会使第一个条件无效.

在最后一种情况下,我们知道a> c,因此交换a和b以满足第一个条件保持第二个条件的有效性.

现在,您向序列添加第四个数字.你有:

a < b > c ? d

如果c <d那么就没有必要改变任何东西了.但是如果我们必须交换c和d,则仍然满足先前条件.因为如果b> c且c> d,那么我们知道b> d.所以交换c和d给我们b> d <c.

添加第五个数字时,可以使用类似的推理.你有a < b > c < d ? e.如果d> e,那么就没有必要改变任何东西了.如果d <e,那么根据定义c <e,所以交换保持先前条件.

实现算法的伪代码:

for i = 0 to n-2
    if i is even
        if (a[i] > a[i+1])
            swap(a[i], a[i+1])
        end if
    else
        if (a[i] < a[i+1])
            swap(a[i], a[i+1])
    end