寻找5个元素的中位数

Question

以下问题是在最近的微软面试中提出的：

给定一个大小为5的未排序数组。 需要多少次最小比较才能找到中位数？然后他又将其扩展到了n的大小。

我认为对于5个元素的解决方案需要6次比较。

1) use 3 comparisons to arrange elements in array such that a[1]<a[2] , a[4]<a[5] and a[1]<a[4]
a) compare a[1] and a[2] and swap if necessary
b) compare a[4] and a[5] and swap if necessary 
c) compare a[1] and a[4].if a[4] is smaller than a[1] , then swap a[1] wid a[4] and a[2] wid a[5]
2)if a[3]>a[2].if a[2]<a[4] median value = min(a[3],a[4]) else median value=min(a[2],a[5]) 
3)if a[3]<a[2].if a[3]>a[4] median value = min(a[3],a[5]) else median value=min(a[2],a[4]) 

这个方法能否扩展到 n 个元素。如果不能，除了快速选择，我们如何在 O(n) 的时间内找到 n 个元素的中位数。

- akash

---

你可能想要稍微改进一下标记。有一个有序列表（1.）可以使用，它们也可以嵌套。 - Flexo

@akash：接受其他问题的答案（也就是说，如果一个答案回答了你的问题，请点击“绿色勾号”）。 - Claudiu

http://tysondw.blogspot.com/2009/09/minimum-number-of-comparisons-to-find.html - Colin D

http://en.wikipedia.org/wiki/Selection_algorithm - Colin D

@ColinD 感谢您提供的“中位数中位数”算法。 - akash

@akash，没问题，这个主题还有很多其他的谷歌搜索结果（其中一些链接回到 stack overflow），如果你使用你的谷歌功夫！ - Colin D

Answer 1

Select算法将列表分成五个元素一组的小组（剩余的元素暂时忽略）。然后，对于每个五元组，计算它们的中位数（如果这五个值可以被加载到寄存器中并进行比较，则此操作可能非常快 - 最少6次比较）。接着，在这些n/5个元素的子列表上递归调用Select函数以找到真正的中位数。

- akash

---

我不理解"load into registers"是什么意思，有人可以解释一下吗？ - Dimath

“装载到寄存器”意味着数据都存在于CPU的内存中。寄存器是CPU的算术逻辑单元可以与之交互的特殊内存。没有比寄存器更快的访问速度了。 - Thomas Legris