以3个函数的中位数进行比较的次数？

Question

到目前为止，我的函数找到3个数字的中位数并对它们进行排序，但它总是进行三次比较。我想我可以在某个地方使用嵌套的if语句，这样有时我的函数只会进行两次比较。

int median_of_3(int list[], int p, int r)
{
    int median = (p + r) / 2;

    if(list[p] > list[r])
        exchange(list, p, r);
    if(list[p] > list[median])
        exchange(list, p, median);
    if(list[r] > list[median])
        exchange(list, r, median);

    comparisons+=3;                // 3 comparisons for each call to median_of_3

    return list[r];
}

我不确定我在哪里可以使嵌套的if语句。

Answer 1

int m = (p + r) / 2;
if (list[p] < list[m])
    if (list[p] >= list[r])
        return list[p];
    else if (list[m] < list[r])
        return list[m];
else
    if (list[p] < list[r])
        return list[p];
return list[r];

Answer 2

如果我们允许额外的操作，我们最多可以使用2个比较来找到中位数。诀窍是使用排他性或找到三个数字之间的关系。

void median3(int A[], int p, int r)
{
    int m = (p+r)/2;
    /* let a, b, c be the numbers to be compared */
    int a = A[p], b = A[m], c = A[r];
    int e = a-b;
    int f = a-c;

    if ((e^f) < 0) {
        med_comparisons += 1;
        /* a is the median with 1 comparison */
        A[m] = a;
        /* b < a < c ? */
        if (b < c) /* b < a < c */ { A[p] = b, A[r] = c; }
        else       /* c < a < b */ { A[p] = c, A[r] = b; }
        comparisons += 2;
    } else {
        med_comparisons += 2;
        int g = b-c;
        if ((e^g) < 0) {
            /* c is the median with 2 comparisons */ 
            A[m] = c;
            /* a < c < b ? */
            if (a < b) /* a < c < b */ { A[p] = a, A[r] = b; }
            else       /* b < c < a */ { A[p] = b, A[r] = a; }
        } else {
            /* b is the median with 2 comparisons */
            A[m] = b;
            /* c < b < a ? */
            if (a > c) /* c < b < a */ { A[p] = c; A[r] = a; }
            else       /* a < b < c */ { /* do nothing */    }
        }
        comparisons += 3;
    }
}

第一个异或（e^f）是找出（a-b）和（a-c）之间符号位的差异
如果它们有不同的符号位，则a是中值。否则，a是最小值或最大值。在这种情况下，我们需要第二个异或。

同样，我们要找出（a-b）和（b-c）之间符号位的差异。如果它们有不同的符号位，一种情况是

如果（a-b）和（b-c）具有相同的符号位，则b是使用与上述相似的参数的中位数。实验表明，一个随机输入将需要1.667个比较来找出中值，并需要一个额外的比较来获得顺序。

Answer 3

如果您只需要中间值，这里有一个基于最小/最大运算符的无分支解决方案：

中值=最大值（最小值（a，b），最小值（最大值（a，b，c））

英特尔CPU具有SSE最小/最大矢量指令，因此根据您或编译器的矢量化能力，这可以运行得非常快。