给定 5 个数字，找出中位数所需的最少比较次数是多少？
一般情况下如何设置最小比较次数？
how do you setup minimum number of comparisons in general?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
一般情况下如何设置最小比较次数？
how do you setup minimum number of comparisons in general?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（3）
引用 Donald Knuth（通过维基百科，因为我目前没有 TAOCP 的副本），比较次数的下限是六：
http://en.wikipedia.org/wiki/Selection_algorithm（向下滚动到标题为“下限”的部分）。
您的目标实际上是找到 k 个最低值，其中 k 是列表大小的一半，向上舍入（因此，k = 3；n = 5），然后取其中的最大值。将其代入页面上的公式中，您将得到：
在本例中， 实际所需的最少比较次数也是六次。
如果您怀疑找到中位数的任务与找到 k 个最低值一样困难，您可以参考 Knuth 的 TAoCP，第 3 卷，第 5.3.3 章后的练习#2。
To cite Donald Knuth (by way of Wikipedia, since I don't have my copy of TAOCP at the moment), the lower bound for the number of comparisons is six:
http://en.wikipedia.org/wiki/Selection_algorithm (scroll down to the section entitled "Lower Bounds").
Your goal is, effectively, to find the k lowest values where k is half the size of the list, rounded up, (so, k = 3; n = 5) and then take the max of those. Plugging that into the formula there on the page, you get:
In this case, the actual minimum number of required comparisons is also six.
If you're in doubt that the task of finding the median is as hard as finding k lowest values, you may refer to Knuth's TAoCP, volume 3, excercise #2 after 5.3.3 chapter.
Donald Knuth 的《计算机编程艺术》第 3 卷第 5.3.3 节“最小比较选择”中有很多相关材料，其中更一般性的问题考虑选择 n 个值中第 t 个最大值所需的最少比较次数。 （该值用Vt(n)表示）。
Knuth 给出 Vt(n) 的上限 n - t + (t-1)⌈lg(n + 2 - t)⌉ em>，通过首先通过锦标赛系统确定n - t + 2的最大元素，删除它（因为它不可能是t最大）并替换它来实现剩下的元素之一，继续这个过程，直到所有元素都成为这个过程的一部分，然后这个阶段最大的元素是原始集合中第t最大的元素。在本例中，n = 5 且 t = 3，因此此公式给出的上限为 6 次比较。
Knuth 提到，当 n ≤ 6 时，这个上限是精确的，因此适用于这种情况。一般来说，我的理解是，没有找到用于选择（和排序）的最小比较算法的通用程序，并且 n 值增加的记录通常使用特殊技巧，这些技巧通常不适用于当n增加时，更大的值或简单地被其他技巧击败。
There is a lot of material on this in volume 3 of Donald Knuth's The Art of Computer Programming, in section 5.3.3, Minimum-Comparison Selection, where the more general question of the minimum number of comparisons required to select the tth largest of n values is considered. (This value is denoted by Vt(n)).
Knuth gives an upper bound of n - t + (t-1)⌈lg(n + 2 - t)⌉ for Vt(n), achieved by first determining the largest element of n - t + 2 by a tournament system, removing this (since it cannot be the tth largest) and replacing it with one of the remaining elements, continuing this procedure until all elements have been a part of this procedure, and then the largest element at this stage is the tth largest of the original set. In this case, n = 5 and t = 3, so the upper bound given by this formula is 6 comparisons.
Knuth mentions that this upper bound is exact when n ≤ 6, so that applies in this case. In general, my understanding is that there are no general procedures for finding minimum-comparison algorithms for selection (and sorting), and records for increasing values of n typically use special tricks that either are not generally applicable to larger values or are simply beaten by other tricks when n increases.
答案是 6。具体方法如下。
（最初发布于我如何计算C# 中的“五的中位数”？）
让我们用 a、b、c 表示这五个数字， d和e。
比较a和b、c和d。 WLOG 让a b，c d。 （到目前为止已进行 2 次比较）
比较 a 和 c。 WLOG 让a c。 (3)
比较b和e。 (4) 请注意，使用 b 代替 d（并且它们不能交换），因为 b 是以下较小者的“对应项” a 和 c。
情况 1：令 b b b b b e。
____比较b和c——较大的值是中位数。 (5)
情况2：令b> e。
____比较a和e。 (5)
____情况2.1：令a a a a a e。
____比较c和e——较大的值是中位数。 (6)
____情况2.2：令a> e。
____比较b和c——较小的值是中位数。 (6)
（格式很丑 ik >.<）
Answer is 6. Here's how.
(Originally posted on How do I calculate the "median of five" in C#?)
Let's denote these five numbers by a, b, c, d, and e.
Compare a and b, c and d. WLOG let a < b, c < d. (2 comparisons so far)
Compare a and c. WLOG let a < c. (3)
Compare b and e. (4) Note that b is used instead of d (and they cannot be swapped) because b is the "counterpart" of the smaller of a and c.
Case 1: let b < e.
____Compare b and c — the greater value is the median. (5)
Case 2: let b > e.
____Compare a and e. (5)
____Case 2.1: let a < e.
________Compare c and e — the greater value is the median. (6)
____Case 2.2: let a > e.
________Compare b and c — the smaller value is the median. (6)
(Formatting is ugly ik >.<)