我们可以选择的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??

推荐答案

您应该考虑的的中位数算法的中位数。它是具有以下复发的线性时间算法...

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...

将列表分为N / 5子序列的5元每 找到每个列表中位数，蛮力。会有N / 5的这些 让M_1，...，m_n / 5是这些中位数。 在递归发现这些中位数的中位数。这将是1元件，枢转 divide the list into n/5 subsequences of 5 elements each find the median of each list, by brute force. there will be n/5 of these Let m_1,..., m_n/5 be these medians. 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

引用

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