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

Question

就个人而言，我认为中位数的中位数不是真正的中位数。正确的？
那么如果上面的说法是正确的，为什么使用中位数的中位数作为支点来划分数组以找到第 Kth min elem 的时间复杂度最坏情况是 O(n) 呢？“n”是元素的数量。

Answer 1

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

它用作优化，在快速排序或快速选择等算法中计算数组分区的枢轴，从而O(n^2)避免最坏情况的复杂性。

维基百科关于它的文章，说：

尽管这种方法优化得很好，但在实践中通常优于选择随机枢轴，随机枢轴具有平均线性时间进行选择和平均线性时间进行排序，并且避免了计算枢轴的开销。