algorithm - 快速排序中值选择

Question

因为我们可以选择三元素划分的中位数来实现快速排序。同样可以选择5、7、11个元素的中位数来实现快速排序吗？如果是，那又如何？？

Answer 1

你应该查看 Median of Medians algorithm .它是一个线性时间算法，具有以下递推...

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

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

1. 将列表分成 n/5 个子序列，每个子序列有 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
• 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

希望对您有所帮助。
赫里斯托