快速排序中位数的选择 [英] Quick sort median selection

问题描述

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

As we can choose median of 3 element partitioning to implement quick sort. Likewise can we choose median of 5, 7, or 11 element to implement quick sort? If so, then how??

推荐答案

您应该考虑的<一个href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm"相对=nofollow>的中位数算法的中位数。它是具有以下复发的线性时间算法...

You should look into the Median of Medians algorithm. It is a linear time algorithm with the following recurrence...

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

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

... which is O(n). The algorithm details...

1. 将列表分为N / 5子序列的5元每
2. 找到每个列表中位数，蛮力。会有N / 5的这些
3. 让M_1，...，m_n / 5是这些中位数。
4. 在递归发现这些中位数的中位数。这将是1元件，枢转<！/ LI>

1. divide the list into n/5 subsequences of 5 elements each
2. find the median of each list, by brute force. there will be n/5 of these
3. Let m_1,..., m_n/5 be these medians.
4. recursively find the median of these medians. this will be 1 element, the pivot!

......以及一些伪code ...

... and some pseudo-code...

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

引用

• <一个href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm
• 中位数在Java中
中位数
• http://www.cs.berkeley.edu /~luca/w4231/fall99/slides/l3.pdf
• http://www.soe.ucsc.edu/classes/ cmps102 / Spring05 / selectAnalysis.pdf
• 的http://webee.technion.ac.il/courses/044268/w0809_website/recitations/Median.pdf

• http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm
• Median of Medians in Java
• http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf
• http://www.soe.ucsc.edu/classes/cmps102/Spring05/selectAnalysis.pdf
• http://webee.technion.ac.il/courses/044268/w0809_website/recitations/Median.pdf

我希望这有助于。
斯托伊奇

I hope this helps.
Hristo

这篇关于快速排序中位数的选择的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！