快速排序中值选择

Question

我们可以选择3个元素分区的中位数来实现快速排序。同样，我们可以选择5、7或11个元素的中位数来实现快速排序吗?如果是，那又是怎么回事?

Answer 1

你应该看看中位数的中位数算法。它是一个线性时间算法，具有以下递归式…

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

…也就是O(n)算法细节…

1. 将列表划分为n/5个子序列，每个子序列有5个元素
2. 查找每个列表的中位数，通过暴力破解。将会有n/5的
3. 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/卢卡/w4231 fall99/幻灯片/l3.pdf
• http://www.soe.ucsc.edu/classes/cmps102/Spring05/selectAnalysis.pdf
• http://webee.technion.ac.il/courses/044268/w0809_website/recitations/Median.pdf

我希望这对你有帮助。斯托伊

Answer 2

• 中位数算法是一种确定性线性时间算法选择算法。
• 使用此算法，可以改进快速排序算法!
• 平均情况时间复杂度为0 (nlogn)，
• 最坏情况下的时间复杂度为O(n2) n方。

然而，我们可以使用中位数的中位数来改进它。

kthSmallest (arr [0 . .n - 1), k)

1. 将arr[]分成≤n/5≤5的组
   除了最后一组元素可能少于5个

2. 对以上创建的≤n/5≤组进行排序，求所有组的中位数组。创建一个辅助数组'median[]'并存储中位数
   

   中位数数组中所有的组

3. //递归调用此方法查找中位数[0..≤≤n/5≤≤1]的中位数medOfMed = kthSmallest(median[0..]⌈n/5⌉1],⌈n/10⌉)

4. 在medOfMed周围划分arr[]并获取其位置。pos = partition(arr, n, medOfMed)

5. 如果pos == k return medOfMed

6. If pos>k返回kthSmallest(arr[1 ..]pos-1), k)

7. If pos <k返回kthSmallest(arr[pos+1..])r],>

现在时间复杂度为:O(n)