c# - 如何在 C# 中计算 "median of five"？

Question

5 的中位数有时用作算法设计中的练习，并且众所周知仅使用 6 次比较 即可计算。

在 C# 中实现此“使用 6 次比较的 5 的中位数” 的最佳方法是什么？我所有的尝试似乎都导致了笨拙的代码 :( 我需要漂亮且可读的代码，同时仍然只使用 6 次比较。

public double medianOfFive(double a, double b, double c, double d, double e){
    //
    // return median
    //
    return c;
}

注意:我想我也应该在这里提供“算法”:

我发现自己无法像 Azereal 在他的论坛帖子中那样清楚地解释算法。所以我会在这里引用他的帖子。来自 http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

Well I was posed this problem in one of my assignments and I turned to this forum for help but no help was here. I eventually found out how to do it.

1. Start a mergesort with the first 4 elements and order each pair (2 comparisons)

2. Compare the two lower ones of each pair and eliminate the lowest one from the possibilities (3 comparisons)

3. Add in the 5th number set aside to the number without a pair and compare the two (4 comparisons)

4. Compare the two lowest of the two new pairs and eliminate the lower one (5 comparisons)

5. Compare the one by itself and the lower of the last pair and the lower number is the median

   The possible median is within the parentesis

(54321)

5:4 3:2 2 comparisons

(4<5 2<3 1)

4:2 3 comparisons

2(4<5 3 1)

1:3 4 comparisons

2(4<5 1<3)

4:1 5 comparisons

1,2(4<5 3)

4:3 6 comparisons

1,2(3)4,5

Three is the median

这是我编写的用于查找 5 的中位数的 C++ 代码。不要介意它的尴尬:

double StageGenerator::MedianOfFive(double n1, double n2, double n3, double n4, double n5){
    double *a = &n1, *b = &n2, *c = &n3, *d = &n4, *e = &n5;
    double *tmp;

    // makes a < b and b < d
    if(*b < *a){
        tmp = a; a = b; b = tmp;
    }

    if(*d < *c){
        tmp = c; c = d; d = tmp;
    }

    // eleminate the lowest
    if(*c < *a){
        tmp = b; b = d; d = tmp; 
        c = a;
    }

    // gets e in
    a = e;

    // makes a < b and b < d
    if(*b < *a){
        tmp = a; a = b; b = tmp;
    }

    // eliminate another lowest
    // remaing: a,b,d
    if(*a < *c){
        tmp = b; b = d; d = tmp; 
        a = c;
    }

    if(*d < *a)
        return *d;
    else
        return *a;

} 

它应该更紧凑，不是吗？

---

正如@pablito 在他的回答中指出的那样，内置的 List.Sort() 无法满足此要求，因为它最多使用 13 次比较:]

Answer 1

我发现这篇文章很有趣，作为练习，我创建了这个，它只进行 6 次比较，其他什么都不做:

static double MedianOfFive(double a, double b, double c, double d, double e)
{
    return b < a ? d < c ? b < d ? a < e ? a < d ? e < d ? e : d
                                                 : c < a ? c : a
                                         : e < d ? a < d ? a : d
                                                 : c < e ? c : e
                                 : c < e ? b < c ? a < c ? a : c
                                                 : e < b ? e : b
                                         : b < e ? a < e ? a : e
                                                 : c < b ? c : b
                         : b < c ? a < e ? a < c ? e < c ? e : c
                                                 : d < a ? d : a
                                         : e < c ? a < c ? a : c
                                                 : d < e ? d : e
                                 : d < e ? b < d ? a < d ? a : d
                                                 : e < b ? e : b
                                         : b < e ? a < e ? a : e
                                                 : d < b ? d : b
                 : d < c ? a < d ? b < e ? b < d ? e < d ? e : d
                                                 : c < b ? c : b
                                         : e < d ? b < d ? b : d
                                                 : c < e ? c : e
                                 : c < e ? a < c ? b < c ? b : c
                                                 : e < a ? e : a
                                         : a < e ? b < e ? b : e
                                                 : c < a ? c : a
                         : a < c ? b < e ? b < c ? e < c ? e : c
                                                 : d < b ? d : b
                                         : e < c ? b < c ? b : c
                                                 : d < e ? d : e
                                 : d < e ? a < d ? b < d ? b : d
                                                 : e < a ? e : a
                                         : a < e ? b < e ? b : e
                                                 : d < a ? d : a;
}