快速排序中位数选择

Question

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

Answer 1

您应该查看Medians of Medians算法.这是一个线性时间算法,具有以下重现...

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

......这是O(n).算法细节......

1. 将列表分成每个5个元素的n/5个子序列
2. 通过蛮力找到每个列表的中位数.将有n/5个
3. 让m_1,...,m_n/5成为这些中位数.
4. 递归地找到这些中位数的中位数.这将是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

参考

• 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

我希望这有帮助.
斯托伊奇