最少数量比较找出 3 个数字的中位数

Question

我正在实现快速排序，我希望将枢轴设置为中位数或三个数字。这三个数字分别是第一个元素、中间元素和最后一个元素。

我能找到更少的中位数吗？比较？

median(int a[], int p, int r)
{
    int m = (p+r)/2;
    if(a[p] < a[m])
    {
        if(a[p] >= a[r])
            return a[p];
        else if(a[m] < a[r])
            return a[m];
    }
    else
    {
        if(a[p] < a[r])
            return a[p];
        else if(a[m] >= a[r])
            return a[m];
    }
    return a[r];
}

Answer 1

如果只关心比较，那么应该使用这个。

int getMedian(int a, int b , int c) {
    int x = a-b;
    int y = b-c;
    int z = a-c;
    if(x*y > 0) return b;
    if(x*z > 0) return c;
    return a;
}

Answer 2

int32_t FindMedian(const int n1, const int n2, const int n3) {
    auto _min = min(n1, min(n2, n3));
    auto _max = max(n1, max(n2, n3));
    return (n1 + n2 + n3) - _min - _max;
}

Answer 3

你不能用一个来完成，而且你只使用了两到三个，所以我想说你已经得到了最少的比较次数。

Answer 4

与其只计算中位数，不如将它们放在适当的位置。 然后你就可以一直只进行 3 次比较，并且你的支点就更接近到位了。

T median(T a[], int low, int high)
{
    int middle = ( low + high ) / 2;
    if( a[ middle ].compareTo( a[ low ] ) < 0 )
        swap( a, low, middle );
    if( a[ high ].compareTo( a[ low ] ) < 0 )
        swap( a, low, high );
    if( a[ high ].compareTo( a[ middle ] ) < 0 )
        swap( a, middle, high );

    return a[middle];
}

Answer 5

我知道这是一个旧线程，但我必须在 RAM 很少且没有硬件乘法单元 (:)) 的微控制器上准确解决这个问题。最后我发现以下效果很好：

static char medianIndex[] = { 1, 1, 2, 0, 0, 2, 1, 1 };

signed short getMedian(const signed short num[])
{
    return num[medianIndex[(num[0] > num[1]) << 2 | (num[1] > num[2]) << 1 | (num[0] > num[2])]];
}

Answer 6

如果你不怕弄脏编译器内部函数，你可以用 0 个分支来完成。

同样的问题之前讨论过：
找到三元组中间值的最快方法？

不过，我必须补充一点，在快速排序的简单实现的背景下，有很多元素，在找到中位数时减少分支数量并不那么重要，因为当你开始折腾时，分支预测器会阻塞。围绕枢轴的元素。更复杂的实现（不会在分区操作上分支，并避免 WAW 危险）将从中受益匪浅。

Answer 7

从总和中删除最大值和最小值

int med3(int a, int b, int c)
{
    int tot_v = a + b + c ;
    int max_v = max(a, max(b, c));
    int min_v = min(a, min(b, c));
    return tot_v - max_v - min_v
}

Answer 8

实际上有一种巧妙的方法可以通过仔细分析 6 种可能的排列（低、中、高）来将中值元素从三个元素中分离出来。 在Python中：

def med(a, start, mid, last):
    # put the median of a[start], a[mid], a[last] in the a[start] position
    SM = a[start] < a[mid]
    SL = a[start] < a[last]
    if SM != SL:
        return
    ML = a[mid] < a[last]
    m = mid if SM == ML else last
    a[start], a[m] = a[m], a[start]

一半的时间你有两次比较，否则你有 3 个（平均 2.5）。 并且只需在需要时（2/3 的时间）交换中值元素一次。

完整的Python快速排序使用这个：

https://github.com/mckoss/labs/blob/master/qs.py

Answer 9

你可以写出所有的排列：

    1 0 2
    1 2 0
    0 1 2
    2 1 0
    0 2 1
    2 0 1

然后我们要找到

1

的位置。如果我们的第一次比较可以分割出一组相等的位置，例如前两行，我们可以通过两次比较来完成此操作。

问题似乎是前两行在我们现有的任何比较中都是不同的：

a<b

，

a<c

，

b<c

。因此我们必须完全识别排列，这在最坏的情况下需要 3 次比较。

Answer 10

使用按位异或运算符，可以找到三个数字的中位数。

def median(a,b,c):
    m = max(a,b,c)
    n = min(a,b,c)
    ans = m^n^a^b^c
    return ans

Answer 11

我建议以下内容作为对最佳答案的改进。

int getMedian(int a, int b , int c) {
    int x = a-b;
    int y = b-c;
    int z = a-c;
    if(x^y > 0) return b;
    if(x^z > 0) return c;
    return a;
}