给定5个数字，查找中位数需要最少进行多少次比较？

Question

如何在一般情况下设置最小比较次数？

- Lazer

---

请参见http://cstheory.stackexchange.com/questions/12257/exact-number-of-comparisons-to-compute-the-median。 - Thomas Ahle

Answer 1

引用唐纳德·克努斯的话（通过维基百科，因为我现在没有我的《计算机程序设计艺术》副本），比较次数的下限是六：

http://en.wikipedia.org/wiki/Selection_algorithm （滚动到标题为“Lower Bounds”的部分）。

你的目标是有效地找到k个最小值，其中k是列表大小的一半，向上取整（因此，k = 3；n = 5），然后取这些值中的最大值。将其插入页面上的公式中，您将得到：

(5 - 3) + 1 + 1 + 2 = 6

在这种情况下，实际所需的最小比较次数也是六次。

如果你怀疑找到中位数的任务和找到k个最小值一样困难，可以参考Knuth的TAoCP第3卷5.3.3章节后的练习#2。

- James McNellis

---

然而，找到N/2个最小元素并不像找到一个中位数那么明显困难。 - P Shved

一旦您找到了前N/2个最小元素，其中最大的元素就是中位数，由于您已经进行了所有必要的比较，因此您知道哪一个N/2个最小元素是最大的。 - James McNellis

谢谢TAoCP的参考，Pavel。 - James McNellis

同意。6 是你能做到的最好的。 - DarthVader

你的或者我的计算有问题。我的答案是 (5 - 3) + 2 + 3。log_2(4) = 2，ceil(log_2(5)) = 3。需要帮助！ - user1091344

Answer 2

在Donald Knuth的《计算机程序设计艺术》第三卷中，第5.3.3节“最小比较选择”中有许多相关材料，考虑了选择n个值中第t大的最小比较数量的更一般问题（该值由Vt(n)表示）。

Knuth给出了Vt(n)的上界，即n-t+(t-1)⌈lg(n+2-t)⌉。首先通过锦标赛系统确定n-t+2的最大元素，将其去除（因为它不能是第t大的元素），然后用剩余的元素之一替换它，继续这个过程直到所有元素都参与到这个过程中，此时该阶段的最大元素就是原始集合的第t大元素。在这种情况下，n=5且t=3，因此这个公式给出的上界是6次比较。

Knuth提到当n≤6时，这个上界是精确的，因此这种情况适用。通常情况下，我理解找到选择（和排序）的最小比较算法没有通用程序，并且对于不断增加的n值，记录通常使用特殊技巧，这些技巧要么不适用于更大的值，要么在n增加时被其他技巧打败。

- JaakkoK

Answer 3

答案为6。 下面是计算方法。 （最初发表在如何在C＃中计算“五个数的中位数”？）

让我们用a，b，c，d和e表示这五个数字。

比较a和b，c和d。不失一般性，让a < b，c < d。（到目前为止有2次比较）

比较a和c。不失一般性，让a < c。（3）

比较b和e。 （4）请注意，使用b而不是d（它们无法互换），因为b是a和c中较小值的“对应项”。

案例1：让b < e。

____比较b和c - 较大的值是中位数。 (5)

案例2：让b > e。

____比较a和e。 (5)

____案例2.1：让a < e。

________比较c和e - 较大的值是中位数。 (6)

____案例2.2：让a > e。

________比较b和c - 较小的值是中位数。 (6) （格式很丑，我知道 >.<）

- Yongqing Yu