找到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个元素中找到中位数

Answer 1

选择算法将列表划分为五个元素的组。（剩余的元素暂时被忽略。然后，对于每组五个值，计算中位数（如果可以将五个值加载到寄存器中并进行比较-至少6个比较），则可以非常快速地进行此操作）。然后，在此 n/5 个元素的子列表中递归地调用 Select，以找到它们的真实中位数。