最低编号 比较找到3个数字的中位数

Question

我正在实施quicksort,我希望将枢轴设置为中位数或三个数字.三个数字是第一个元素,中间元素和最后一个元素.

我可以找到中位数少于没有.比较？

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

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

Answer 3

与其只是计算中位数，不如将它们放在适当的位置。然后，您可以一直进行 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 4

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;
}