time-complexity - 中位数快速排序的最坏情况时间复杂度是多少？

Question

中位数快速排序的最坏情况时间复杂度是多少（枢轴由需要 O(n) 时间才能找到的中位数的中位数确定）？

Answer 1

根据维基，

近似中值选择算法也可以用作快速排序中的枢轴策略，产生最优算法，最坏情况复杂度为 O(n log n)。

这是因为中位数算法的中位数可以防止在已经排序的数组上的简单快速排序中发生的错误分区。