1

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

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大的还是别的。

4

2 回答 2

0

代码必须来自这里。

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

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

于 2013-10-16T22:12:11.390 回答
0

普遍的看法是，对于小输入，快速排序比插入排序慢。因此，许多实现在某个阈值处切换到插入排序。

在 Quicksort 的 Wikipedia 页面中有对这种做法的参考。 这是一个商业合并排序代码的示例，它为小输入切换到插入排序。这里的阈值为 7。

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

然而，我在实践中发现，普遍的智慧并不普遍。当我运行基准测试时，切换的积极影响或消极影响很小。那是为了快速排序。在分区算法中，它更有可能不是负数，因为分区的一侧在每一步都被丢弃，因此花费在小输入上的时间更少。这在@Dennis 对这个 SO question的回复中得到了验证。

于 2013-10-16T22:13:34.397 回答