快速排序中位数选择

由于我们可以选择3元素分区的中位数来实现快速排序。同样，我们可以选择5,7或11个元素的中位数来实现快速排序吗？如果是这样，那么怎么样？快速排序中位数选择

2011-04-09 james

嗯..基本上你只是选择所述阵列的5,7，或11个元件被划分并使用他们的位数作为枢轴。这与3的中位数并没有太大的区别。主要区别可能在于，对于小于5,7或11个元素的数组，您应该进行插入排序。再次，它会加快你的快速排序，几乎不管你有多少元素用于查找你的数据透视表，对小于10-15个元素的数组进行插入排序。 – 2011-04-09 18:08:05

你应该看看Median of Medians algorithm。这是一种线性时间算法，具有以下重复...

T(n) ≤ T(n/5) + T(7n/10) + O(n)

...这是O（n）。该算法的细节...

将列表分为5种元素各
的N/5个子找到每个列表的中位数，蛮力。将有n/5这些
让m_1，...，m_n/5是这些中位数。
递归地找到这些中位数。这将是1个元素，这个关键点！

...和一些伪代码...

MedianOfMedians (A[1],...,A[n]) 
begin 
    for i=1 to n/5 do { 
     let m_i be the median of A[5i − 4], A[5i − 3],..., A[5i]; 
    } 
    pivot = Select(m1,...,m_n/5, n/10); // the pivot 
    return pivot 
end

参考

我希望这有助于。
赫里斯托斯

来源

2011-04-09 16:01:59 Hristo

根据你的代码，我们可以找到最接近整个数组中值的数据点，然后将整个数组分成2部分？如果下半部分的数字少于上半部分，那么做什么？ – Alcott 2011-10-11 02:59:20

快速排序中位数选择

回答

相关问题