我正在实施快速排序，我希望将枢轴设置为中位数或三个数字。这三个数字是第一个元素、中间元素和最后一个元素。
我能不能在 less no 中找到中位数。比较？
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];
}
如果关注点只是比较，那么应该使用它。
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;
}
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;
}
您不能一次完成，而且您只使用两个或三个，所以我会说您已经获得了最少的比较次数。
与其只计算中位数，不如将它们放在适当的位置。然后，您可以一直只进行 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];
}
我知道这是一个旧线程，但我必须在一个 RAM 很少且没有 ah/w 乘法单元 (:) 的微控制器上解决这个问题。最后，我发现以下效果很好：
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])]];
}
如果您不害怕使用编译器内在函数让您的手有点脏，那么您可以使用正好 0 个分支来做到这一点。
之前讨论过同样的问题：
找到三元组中间值的最快方法？
不过，我必须补充一点，在快速排序的天真实现的上下文中，有很多元素，在找到中位数时减少分支的数量并不是那么重要，因为当你开始折腾元素时，分支预测器会以任何一种方式阻塞围绕枢轴。更复杂的实现（不在分区操作上分支，并避免 WAW 危险）将从中受益匪浅。
从总和中删除最大值和最小值
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
}
你可以写出所有的排列：
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 次比较。
实际上，有一种巧妙的方法可以通过仔细分析 6 种可能的排列（低、中、高）来将中值元素从三个中分离出来。在蟒蛇中：
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快速排序在以下位置使用：
使用按位异或运算符，可以找到三个数字的中位数。
def median(a,b,c):
m = max(a,b,c)
n = min(a,b,c)
ans = m^n^a^b^c
return ans