algorithm - 按特定顺序排列整数

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，所以如果 a < 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