4

给定五个随机元素，只需进行六次比较就可以找到中位数。但我有一个额外的要求，即还满足以下条件：

a < c && b < c && c < d && c < e

a < b 或 d < e 不需要。

我已经能够使用七次比较来满足这个条件，但不是六次。这是我的代码，应该是不言自明的：

void medianSort(int[] arr)
{
    assert(arr.length == 5);

    void sortPair(ref int a, ref int b)
    {
        if(a > b) swap(a, b);
    }

    sortPair(arr[0], arr[1]);
    sortPair(arr[3], arr[4]);
    sortPair(arr[0], arr[3]);
    sortPair(arr[1], arr[4]);
    sortPair(arr[2], arr[3]);
    sortPair(arr[1], arr[2]);
    sortPair(arr[2], arr[3]);
}

我有一个快速排序，我希望通过使用 5 的中位数来选择枢轴来增强它。通过满足该条件，五个元素已经排序。

是否有可能在六次比较中完成这一点，还是我能做到最好的七次？

4

2 回答 2

2

我花了两个小时解决这个问题，但我找到了解决方案。重要的是要跟踪所做的比较，我在评论中做了非常详细的比较。该函数用 D 编写。

void medianSort(alias pred = "a < b", T)(ref T a, ref T b, ref T c, ref T d, ref T e)
{
    alias binaryFun!pred less;
    bool greater(T a, T b){ return !less(a, b); }

    if(greater(a, b)) swap(a, b); // #1
    // a<b
    if(greater(d, e)) swap(d, e); // #2
    // a<b d<e

    if(less(a, d)) // #3
    {
        // a<d<e a<b
        // eliminate a
        // d<e
        if(greater(b,c)) swap(b,c); // #4
        // b<c d<e
    }
    else // if(less(d, a))
    {
        // a<b d<a d<e
        // d<a<b   d<e
        swap(a, d);
        // a<d<b   a<e
        // eliminate a
        // d<b
        swap(d, b);
        // b<d
        if(greater(c, e)) swap(c, e); // #4
        // b<d c<e
        swap(c, d);
        // b<c d<e
    }

    // b<c d<e
    if(less(b, d)) // #5
    {
        // b<c b<d d<e
        // b<c b<d<e
        // eliminate b
        // d<e
    }
    else
    {
        // b<c d<e d<b
        // d<b<c d<e
        swap(b, d);
        // b<d<c b<e
        // eliminate b
        // d<c
        swap(c, e);
        // d<e
    }

    // d<e
    // median is smaller of c and d
    if(greater(c, d)) swap(c, d); // #6
}

Python： http: //pastebin.com/0kxjxFQX

于 2012-06-19T19:04:06.730 回答
1

好的，这是一个证明你至少需要 6 次比较的证据。

首先，请注意，我们获得的所有信息仅基于比较。我们可以根据比较步骤中发生的情况在最后进行交换。另请注意，我们的比较只能基于之前所做的比较。例如，算法的第一步将始终与之前未进行任何比较相同；第二个比较已经可以取决于第一个，等等。

让我们根据它们的大小“命名”元素 - 1,2,3,4,5。它们可以任何顺序出现在输入中。现在，我们至少需要四次比较才能正确排序元素。他们是：

3 > 2           [1]
3 > 1 OR 2 > 1  [2]
3 < 4           [3]
3 < 5 OR 4 < 5  [4]

任何其他比较都是额外的。此外，如果我们不能避免两个比较 in[2]或两个比较 in [4]- 这些也会变得extra。

由于初始排列可以是任何东西，我们立即得到一个额外的比较：（1 < 5理解这一点很重要：因为我们的算法总是根据它们在输入中的呈现方式采用相同的前两个元素，比如a和b，所以总是有a = 1和)的可能性b = 5。

现在，第二步需要考虑两种情况：

案例 1：我们比较1和以外的两个元素5。由于我们无法区分2, 3, 并且4在这个阶段我们立即得到第二个额外的比较：2 < 4。所以我们最多可以进行 6 次比较。

情况 2：我们将1or5与 、 或 中的一个2进行3比较4。不失一般性，让我们假设我们正在比较1。由于我们无法区分2, 3, ant4我们得到第二个额外比较：1 < 4. 量子点

于 2012-06-20T12:36:50.023 回答