中位数的选择算法

Question

我试图理解寻找中位数的选择算法。我已经粘贴了下面的伪代码。

SELECT(A[1 .. n], k):
if n<=25
use brute force
else
m = ceiling(n/5)
for i=1 to m
B[i]=SELECT(A[5i-4 .. 5i], 3)
mom=SELECT(B[1 ..m], floor(m/2))
r = PARTITION(A[1 .. n],mom)
if k < r
return SELECT(A[1 .. r-1], k)
else if k > r
return SELECT(A[r +1 .. n], k-r)
else
return mom

我有一个非常微不足道的疑问。我想知道作者上面写的 i<=25 的蛮力是什么意思。是不是他会一个接一个地将元素与其他元素进行比较，看看它是第 k 个最大的还是其他什么。

Answer 1

代码必须来自这里。

蛮力算法可以是任何简单而愚蠢的算法。在您的示例中，您可以对 25 个元素进行排序并找到中间的元素。与选择算法相比，这是简单而愚蠢的，因为排序需要O(nlgn)而选择只需要线性时间。

当n很小时，蛮力算法通常就足够了。此外，它更容易实现。在此处阅读有关蛮力的更多信息。

Answer 2

常识是，对于小输入，快速排序比插入排序慢。 因此，许多实现在某个阈值切换到插入排序。

在

快速排序的维基百科页面中提到了这种做法。下面是商业合并排序代码的示例，该代码切换到小输入的插入排序。 这里的阈值是 7。

"蛮力"几乎可以肯定是指这里的代码使用相同的做法：插入排序，然后选择中间元素作为中位数。

然而，在实践中我发现，常识并非普遍正确。 当我运行基准测试时，开关几乎没有积极或消极的影响。 那是给快速排序的。 在Parition算法中，它更有可能是负数，因为分区的一侧在每一步都被丢弃，因此在小输入上花费的时间更少。 这在@Dennis对这个SO问题的回答中得到了验证。