2

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

我知道这可以通过从左到右查看数组来解决，如果不满足条件，交换这两个元素会给出正确的答案。有人能解释一下为什么这个算法有效吗？

4

2 回答 2

8

给定数组中的任意三个连续数字，有四种可能的关系：

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
于 2013-07-21T23:19:06.490 回答
1

这是java中建议解决方案的代码。 

public static int [] alternatingList(int [] list) {
    int first, second,third;
    for (int i = 0;i < list.length-2;i+=2) {
        first = list[i];
        second = list[i+1];
        third = list[i+2];
        if (first > second && first > third) {
            list[i+1] = first;
            list[i] = second;
        }
        else if (third> first && third > second) {
            list[i+1] = third;
            list[i+2] = second;
        }
    }
    return list;
}

在此代码中，由于所有数字都是不同的，因此总会有一个更大的数字放入“峰值”中。交换数字不会改变您所做的最后一部分的一致性，因为您换出的数字将始终小于您放入新峰值的数字。

请记住，这段代码不能处理一些边缘情况，例如长度均匀的列表和小于 3 的列表，我写得很快 :)，我只写代码来说明解决方案的概念

此外，此解决方案比建议的欺骗中的解决方案更好，因为它通过了一次。欺骗中的解决方案使用了 hoare 的选择算法，该算法为 n，但需要在列表上多次减小大小传递，并且在使用 Hoare（或中位数的中位数）后还需要在列表上再进行 n 次传递。

更多数学证明：
对于每三个连续的数字a,b,c，有三个选项

a > b && a > c
b > c && b > a
c > a && c > b

在第一种情况下，您切换a到中间，因为它是最大的，第二种情况什么都不做（最大的已经在中间），第三种情况“c”进入中间。

现在你有a < b > c d e现在 d 和 e 未知的地方。现在新a,b,c的是c,d,e和你做同样的操作，这保证不会弄乱顺序，因为c只有当它大于时才会改变d，e因此移动到c's 位置的数字将小于b并且不会破坏排序，这可以以永不中断的顺序无限清晰地继续。

于 2013-07-21T23:20:26.623 回答