相关疑难解决方法(0)

给定是一个包含三个数值的数组,我想知道这三个数值的中间值.

问题是,找到三者中间的最快方法是什么？

我的方法是这种模式 - 因为有三个数字有六种排列:

if (array[randomIndexA] >= array[randomIndexB] &&
    array[randomIndexB] >= array[randomIndexC])

如果有人可以帮助我找到更优雅,更快捷的方法,那将是非常好的.

我正在寻找一个5元素排序的排序网络实现,但由于我在SO上找不到一个好的参考,我想要求为所有小的n值排序网络,至少n = 3通过n = 6但更高的值也会很好.一个好的答案至少应该将它们列为"交换"(对2个元素进行排序)操作的序列,但是在低阶排序网络方面看到递归分解也可能会很好.

对于我的应用程序,我实际上只关心5个元素的中位数,而不是实际按顺序排列.也就是说,只要中位数在正确的位置结束,结果中可能未指定其他4个元素的顺序.可以使用与排序网络相关的方法来计算交换数量少于执行完整排序的中位数吗？如果是这样,我的问题(对于n = 5)和其他情况的这种解决方案也会得到一个很好的答案.

(注意:我已经标记了这个问题C,因为C是我使用的语言,我怀疑跟随C标签的人有很好的答案,但我真的不在乎答案实际上是用C编写而不是伪代码只要符合上述标准,它就可以很容易地转换成C语言.)

到目前为止,我的函数找到3个数字的中位数并对它们进行排序,但它总是进行三次比较.我想我可以在某处使用嵌套的if语句,这样有时我的函数只会进行两次比较.

int median_of_3(int list[], int p, int r)
{
    int median = (p + r) / 2;

    if(list[p] > list[r])
        exchange(list, p, r);
    if(list[p] > list[median])
        exchange(list, p, median);
    if(list[r] > list[median])
        exchange(list, r, median);

    comparisons+=3;                // 3 comparisons for each call to median_of_3

    return list[r];
}

我不确定我在哪里可以看到嵌套的if语句.

你如何设置一般的最小比较数？

所以,在回答其他一些问题时,我偶然发现计算中位数为5的必要性.现在,在另一种语言中有一个类似的问题,但是我想要一个Scala算法,我不确定我是否满意我的.