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

Question

中

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

Answer 1

根据维基，

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

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