c++ - 以 3 函数的中位数进行的比较次数？

Question

截至目前，我的函数找到 3 个数字的中位数并对它们进行排序，但它总是进行 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

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

中位数 = max(min(a,b), min(max(a,b),c));

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