如何计算 C# 中的“五的中位数”？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/480960/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do I calculate the "median of five" in C#?
提问by Gant
The median of five is sometimes used as an exercise in algorithm design and is known to be computable using only 6 comparisons.
中位数 5 有时用作算法设计的练习，并且已知仅使用 6 次比较即可计算。
What is the best way to implement this "median of five using 6 comparisons"in C# ? All of my attempts seem to result in awkward code :( I need nice and readable code while still using only 6 comparisons.
在 C#中实现这种“使用 6 个比较的 5 的中位数”的最佳方法是什么？我所有的尝试似乎都导致了笨拙的代码 :( 我需要漂亮且可读的代码，同时仍然只使用 6 个比较。
public double medianOfFive(double a, double b, double c, double d, double e){
//
// return median
//
return c;
}
Note:I think I should provide the "algorithm" here too:
注意：我想我也应该在这里提供“算法”：
I found myself not able to explain the algorithm clearly as Azerealdid in his forum post. So I will reference his post here. From http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085
我发现自己无法像Azereal在他的论坛帖子中那样清楚地解释算法。所以我会在这里参考他的帖子。来自http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085
Well I was posed this problem in one of my assignments and I turned to this forum for help but no help was here. I eventually found out how to do it.
Start a mergesort with the first 4 elements and order each pair (2 comparisons)
Compare the two lower ones of each pair and eliminate the lowest one from the possibilities (3 comparisons)
Add in the 5th number set aside to the number without a pair and compare the two (4 comparisons)
Compare the two lowest of the two new pairs and eliminate the lower one (5 comparisons)
Compare the one by itself and the lower of the last pair and the lower number is the median
The possible median is within the parentesis
(54321)
5:4 3:2 2 comparisons
(4<5 2<3 1)
4:2 3 comparisons
2(4<5 3 1)
1:3 4 comparisons
2(4<5 1<3)
4:1 5 comparisons
1,2(4<5 3)
4:3 6 comparisons
1,2(3)4,5
Three is the median
好吧，我在我的一项作业中遇到了这个问题，我转向这个论坛寻求帮助，但这里没有任何帮助。我最终找到了如何做到这一点。
使用前 4 个元素开始归并排序并对每一对进行排序（2 次比较）
比较每对中较低的两个，并从可能性中消除最低的一个（3 次比较）
将预留的第 5 个数字与没有配对的数字相加并比较两者（4 次比较）
比较两个新对中最低的两个并消除较低的一个（5 次比较）
单独比较一个和最后一对的较低者，较低的数字是中位数
可能的中位数在括号内
(54321)
5:4 3:2 2 比较
(4<5 2<3 1)
4:2 3 比较
2(4<5 3 1)
1:3 4 比较
2(4<5 1<3)
4:1 5 比较
1,2(4<5 3)
4:3 6 比较
1,2(3)4,5
三是中位数
Here is the C++ code I wrote to find median of five. Don't mind its awkwardness:
这是我编写的 C++ 代码，用于查找 5 的中位数。不要介意它的尴尬：
double StageGenerator::MedianOfFive(double n1, double n2, double n3, double n4, double n5){
double *a = &n1, *b = &n2, *c = &n3, *d = &n4, *e = &n5;
double *tmp;
// makes a < b and b < d
if(*b < *a){
tmp = a; a = b; b = tmp;
}
if(*d < *c){
tmp = c; c = d; d = tmp;
}
// eleminate the lowest
if(*c < *a){
tmp = b; b = d; d = tmp;
c = a;
}
// gets e in
a = e;
// makes a < b and b < d
if(*b < *a){
tmp = a; a = b; b = tmp;
}
// eliminate another lowest
// remaing: a,b,d
if(*a < *c){
tmp = b; b = d; d = tmp;
a = c;
}
if(*d < *a)
return *d;
else
return *a;
}
It should be more compact, isn't it ?
它应该更紧凑，不是吗？
As @pablito pointed out in his answer, the built-in List.Sort()cannot fulfill this requirement since it uses up to 13 comparisons :]
正如@pablito 在他的回答中指出的那样，内置List.Sort()函数无法满足此要求，因为它最多使用 13 个比较：]
采纳答案by Matthew Crumley
This is basically just factoring out the swapping and sorting code from your C++ example:
这基本上只是从您的 C++ 示例中提取交换和排序代码：
private static void Swap(ref double a, ref double b) {
double t = a;
a = b;
b = t;
}
private static void Sort(ref double a, ref double b) {
if (a > b) {
double t = a;
a = b;
b = t;
}
}
private static double MedianOfFive(double a, double b, double c, double d, double e){
// makes a < b and c < d
Sort(ref a, ref b);
Sort(ref c, ref d);
// eleminate the lowest
if (c < a) {
Swap(ref b, ref d);
c = a;
}
// gets e in
a = e;
// makes a < b
Sort(ref a, ref b);
// eliminate another lowest
// remaing: a,b,d
if (a < c) {
Swap(ref b, ref d);
a = c;
}
return Math.Min(d, a);
}
回答by user50612
An interesting thread here:
这里有一个有趣的线程：
Quote from thread:
从线程引用：
Put the numbers in an array.
Use three comparisons and shuffle around the numbers so that a[1] < a[2], a[4] < a[5], and a[1] < a[4].
If a[3] > a[2], then the problem is fairly easy. If a[2] < a[4], the median value is the smaller of a[3] and a[4]. If not, the median value is the smaller of a[2] and a[5].
So a[3] < a[2]. If a[3] > a[4], then the solution is the smaller of a[3] and a[5]. Otherwise, the solution is the smaller of a[2] and a[4].
将数字放入数组中。
使用三个比较并对数字进行混洗，使得 a[1] < a[2]、a[4] < a[5] 和 a[1] < a[4]。
如果 a[3] > a[2]，那么问题就很简单了。如果 a[2] < a[4]，则中值是 a[3] 和 a[4] 中的较小者。如果不是，则中值是 a[2] 和 a[5] 中的较小者。
所以 a[3] < a[2]。如果 a[3] > a[4]，则解是 a[3] 和 a[5] 中的较小者。否则，解是 a[2] 和 a[4] 中的较小者。
回答by Pablo Retyk
Just to check how many comparisons:
只是为了检查有多少比较：
class MyComparable : IComparable
{
public static int NumberOfComparisons = 0;
public int NumPart { get; set; }
#region IComparable Members
public int CompareTo(object obj)
{
NumberOfComparisons++; //I know, not thread safe but just for the sample
MyComparable mc = obj as MyComparable;
if (mc == null)
return -1;
else
return NumPart.CompareTo(mc.NumPart);
}
#endregion
}
class Program
{
static void Main(string[] args)
{
List<MyComparable> list = new List<MyComparable>();
list.Add(new MyComparable() { NumPart = 5 });
list.Add(new MyComparable() { NumPart = 4 });
list.Add(new MyComparable() { NumPart = 3 });
list.Add(new MyComparable() { NumPart = 2 });
list.Add(new MyComparable() { NumPart = 1 });
list.Sort();
Console.WriteLine(MyComparable.NumberOfComparisons);
}
}
the result is 13.
结果是 13。
回答by Kevin
This should do it
这应该做
private Double medianofFive(double[] input)
{
Double temp;
if (input[0] > input[1])//#1 - sort First and Second
{
temp = input[0];
input[0] = input[1];
input[1] = temp;
}
if (input[2] > input[3])//#2 sort Third and Fourth
{
temp = input[2];
input[2] = input[3];
input[3] = temp;
}
// replace the smaller of first and third with 5th, then sort
int smallerIndex = input[0] < input[2] ? 0 : 2;//#3
input[smallerIndex] = input[4];
//sort the new pair
if(input[smallerIndex]>input[smallerIndex+1])//#4
{
temp = input[smallerIndex];
input[smallerIndex] = input[smallerIndex+1];
input[smallerIndex+1] = temp;
}
//compare the two smaller numbers
// then compare the smaller of the two's partner with larger of the two
// the smaller of THOSE two is the median
if (input[2] > input[0])
//#5
{
temp = input[2] > input[1] ? input[1] : input[2];//#6
}
else
{
temp = input[0] > input[3] ? input[3] : input[0];//#6
}
return temp;
}
回答by Bill the Lizard
This is pretty ugly and could use some refactoring, but it explicitly walks through all the comparisons and swaps so you can see what's going on.
这非常丑陋，可以使用一些重构，但它明确地遍历所有比较和交换，以便您可以看到发生了什么。
public double medianOfFive(double a, double b, double c, double d, double e){
double median;
// sort a and b
if(a > b) // comparison # 1
{
double temp = a;
a = b;
b = temp;
}
// sort c and d
if(c > d) // comparison # 2
{
double temp = c;
c = d;
d = temp;
}
// replace the lower of a and c with e
// because the lowest of the first four cannot be the median
if(a < c) // comparison # 3
{
a = e;
// re-sort a and b
if(a > b) // comparison # 4
{
double temp = a;
a = b;
b = temp;
}
}
else
{
c = e;
// re-sort c and d
if(c > d) // comparison # 4
{
double temp = c;
c = d;
d = temp;
}
}
// eliminate a or c, because the lowest
// of the remaining four can't be the median either
if(a < c) // comparison #5
{
if(b < c) // comparison #6
{
median = c;
}
else
{
median = b;
}
}
else
{
if(d < a) // comparison #6
{
median = a;
}
else
{
median = d;
}
}
return median;
}
回答by Tamir
Interesting how many comparisons in MSDN sample...
有趣的是 MSDN 示例中有多少比较...
public static double Median(this IEnumerable<double> source) {
if (source.Count() == 0) throw new InvalidOperationException("Cannot compute median for an empty set.");
var sortedList = from number in source
orderby number
select number;
int itemIndex = (int)sortedList.Count() / 2;
if (sortedList.Count() % 2 == 0) {
// Even number of items.
return (sortedList.ElementAt(itemIndex) + sortedList.ElementAt(itemIndex - 1)) / 2; } else {
// Odd number of items.
return sortedList.ElementAt(itemIndex); }
}
回答by joel.neely
For completeness, the question is a specific case of a sorting network, which Knuth (Art of Computer Programming, vol 3)covers in great detail. The classic paper by K.E. Batcheron the subject is brief and worth reading.
为完整起见，问题是排序网络的一个特定案例，Knuth（计算机编程艺术，第 3 卷）对此进行了详细介绍。KE Batcher关于这个主题的经典论文很简短，值得一读。
回答by DRBlaise
I found this post interesting and as an exercise I created this which ONLY does 6 comparisons and NOTHING else:
我发现这篇文章很有趣，作为一个练习，我创建了它，它只进行了 6 次比较，其他什么都不做：
static double MedianOfFive(double a, double b, double c, double d, double e)
{
return b < a ? d < c ? b < d ? a < e ? a < d ? e < d ? e : d
: c < a ? c : a
: e < d ? a < d ? a : d
: c < e ? c : e
: c < e ? b < c ? a < c ? a : c
: e < b ? e : b
: b < e ? a < e ? a : e
: c < b ? c : b
: b < c ? a < e ? a < c ? e < c ? e : c
: d < a ? d : a
: e < c ? a < c ? a : c
: d < e ? d : e
: d < e ? b < d ? a < d ? a : d
: e < b ? e : b
: b < e ? a < e ? a : e
: d < b ? d : b
: d < c ? a < d ? b < e ? b < d ? e < d ? e : d
: c < b ? c : b
: e < d ? b < d ? b : d
: c < e ? c : e
: c < e ? a < c ? b < c ? b : c
: e < a ? e : a
: a < e ? b < e ? b : e
: c < a ? c : a
: a < c ? b < e ? b < c ? e < c ? e : c
: d < b ? d : b
: e < c ? b < c ? b : c
: d < e ? d : e
: d < e ? a < d ? b < d ? b : d
: e < a ? e : a
: a < e ? b < e ? b : e
: d < a ? d : a;
}
回答by Patrick
Thanks. I know your posts are quite old, but it was useful for my issue.
谢谢。我知道你的帖子很旧，但它对我的问题很有用。
I needed a way to compute the median of 5 SSE/AVX registers (4 floats / 8 floats at once, or 2 doubles/4 doubles at once):
我需要一种方法来计算 5 个 SSE/AVX 寄存器的中位数（一次 4 个浮点数/8 个浮点数，或一次 2 个双精度数/4 个双精度数）：
without any conditional jumps
only with min/max instructions
没有任何条件跳转
仅使用最小/最大指令
If the min/max functions are programmed for scalar registers with conditional jumps, my code is not optimal in term of comparisons. But if the min/max functions are coded with corresponding CPU instructions, my code is very effective because no conditional jump is done by the CPU when executing.
如果 min/max 函数是为带有条件跳转的标量寄存器编程的，我的代码在比较方面不是最佳的。但是如果 min/max 函数用对应的 CPU 指令编码，我的代码是非常有效的，因为 CPU 在执行时没有进行条件跳转。
template<class V>
inline V median(const V &a, const V &b, const V &c)
{
return max(min(a,b),min(c,max(a,b)));
}
template<class V>
inline V median(const V &a, const V &b, const V &c, const V &d, const V &e)
{
V f=max(min(a,b),min(c,d)); // discards lowest from first 4
V g=min(max(a,b),max(c,d)); // discards biggest from first 4
return median(e,f,g);
}
回答by John Tromp
-- In Haskell the solution could look like
import Data.Function
median5By pred [a,b,c,d,e] = fst $ merge2 c' d' where
merge2 = merge2By pred
merge2By pred x y = if x `pred` y then (x,y) else (y,x)
((_,b'), de ) = merge2By (pred `on` fst) (merge2 a b) (merge2 d e)
((_,c'),(d',_)) = merge2By (pred `on` fst) (merge2 b' c) de
main = print $ median5By (<) [2,5,4,1,3]
