从向量中提取最小，最大和中位数的最有效方法是什么

Question

vector<T> vec{...}假设T是一种数值类型，给定一种提取其最小值，最大值和中位数的最佳方法是什么？我知道的std::nth_element还有std::minmax_element，但他们似乎做多余的工作，如果叫了一个又一个。

到目前为止，我想到的最好的主意是一次叫std :: nth_element 3次。但这仍然需要3N比较，对吗？有什么方法可以重用先前迭代中完成的部分排序吗？

Answer 1

用于std::nth_element对产生中位数的分区，然后std::min_element在左半部分和右半部分进行划分std::max_element。

如果您需要更快的速度，请根据滚动您自己的版本std::nth_element。