我是一名compsci学生，在Analysis&设计II级：
无序集合的中值是一个元素，使得小于中值的元素在元素数之一内假设没有平局，则会更大。
（a） 编写一个算法，找出3个不同值a，b、 c.
（b） 确定算法在平均情况和最坏情况。
从我搜索和了解到的一点来看，这似乎被称为寻找未排序数组的第k个元素，或者寻找中值？
然而，我们还没有学会快速排序，我所能找到的似乎比这里要求我的要复杂得多。也就是说，我不完全确定我是否理解这个问题中的定义。此外，找到3个不同值a、b、c的中值是否意味着找到一组大小为3的中值？
我不一定在寻找答案。只是简单的解释或澄清。谢谢
尝试#1
（a） 根据templatepedef的建议，我想出了一个天真的算法来解决这个问题：
medianOf(int a, int b, int c)
if a < b
if a > c
return a
else //a > b
if a < c
return a
if b < c
if b > a
return b
else //b > c
if b < a
return b
if c < a
if c > b
return c
else //c > a
if c < b
return c
我知道这非常天真和丑陋，但我无法想出更好的解决方案，而且已经花了我太多时间。
（b） 似乎最好的情况是当c<a<b进行2次比较，并且最坏的情况是当a<c<b有9个比较？那么，平均值是（2+9）/2，是5个还是6个比较？
还是我现在很天真？
尝试#2
（a） 好吧，所以，按照唐的建议，我真的很努力地把比较的次数减少到3。从数学上讲，我理解你的观点。检查a<b, b<c, a<c并从中扣除其余状态就足够了，但我找不到对其进行编码的方法……这是我最好的尝试：
medianOf(int a, int b, int c)
if a < b 1
if c < a 1
return a //c < a < b
else // a < b && a < c
if b < c 1
return b //a < b < c
else
return c //a < c < b
else //a > b
if c > a 1
return a //c > a > b
else //a > b && a > c
if b > c 1
return b //a > b > c
else
return c //a > c > b
我看不出我还能做得更好：
（b） 最佳情况：1个比较。平均情况：5/2=2到3次比较。最坏情况：5个比较。
有更好的吗？
最终解决方案
多亏了唐，经过我的努力，我终于得到了它。我的最后一个算法是正确的，但我的计数是错误的。
（b） 最佳情况：2个比较。平均病例：2例比较。最坏情况：3次比较。
幸运的是，我认为你想得太多了。：-）这样想——你能实现这个功能吗？
int medianOf(int a, int b, int c) {
...
}
你不必担心找到任意集的中值。只要找到三个输入的中间值。
一旦你做到了这一点，看看你所做的比较，并思考最佳情况、最坏情况和平均比较案例数。您可以直接计算进行了多少比较，因为您的代码应该很短。
你所想到的中值技术适用于更普遍的情况，即你有任意数量的元素，并想取所有元素的中值。这肯定比这更复杂，但这似乎不是你被要求做的
希望这能有所帮助！
提示：
如果<=b和b<=c、 则b是中值。
如果<=b且b>c且c>=a，则c为中值。
如果<b和b>c和c<a、 则a是中值。
如果a>=b且b>=c，则b为中值。
如果a>=b并且b<如果a>=c，则c为中值。
如果a>=b并且b<c和a<c、 则a是中值。
您可以在嵌套的if/else语句中对此进行编码，以便在返回答案之前执行2或3次比较。唯一的问题是比较次数的最坏情况、最佳情况和平均情况。对于平均情况，您可能必须假设所有3个数字都是不同的（但按随机顺序），否则"等于"的情况可能会根据比较的频率改变平均比较次数。