algorithm - 中位数的中位数不是真正的中位数。正确的？

Question

个人认为中位数的中位数并不是真正的中位数。对吗？
那么如果上面的说法是正确的，那为什么要用中位数的中位数作为枢轴来划分数组，求第K个最小元素的时间复杂度最坏情况是O(n)呢？ “n”是元素的数量。

Answer 1

中位数的中位数确实只是一个近似值，不一定是实际的中位数。

它被用作一种优化，在 Quicksort 或 Quickselect 等算法中计算数组分区的主元，从而避免 O(n^2) 的最坏情况复杂度。

Wikipedia article关于它，说:

Although this approach optimizes quite well, it is typically outperformed in practice by instead choosing random pivots, which has average linear time for selection and average linearithmic time for sorting, and avoids the overhead of computing the pivot.