c++ - 使用 STL 容器进行中位数计算时，正确的方法是什么？

Question

假设我需要从 1000000 个随机数值序列中检索中位数。

如果使用任何但 std::list，我没有(内置)方法来对中值计算的序列进行排序。

如果使用 std::list，我无法随机访问值来检索排序序列的中间(中位数)。

自己实现排序并使用例如是否更好？ std::vector，还是使用std::list和使用std::list::iterator来for-loop-走到中间值？后者似乎不那么开销，但也感觉更难看..

或者我有更多更好的选择吗？

Answer 1

任何随机访问容器(如 std::vector )都可以使用标准 std::sort 进行排序算法，在 <algorithm> 中可用标题。

要找到中位数，使用 std::nth_element 会更快。 ;这足以将一个选定的元素放在正确的位置，但不能完全对容器进行排序。所以你可以找到这样的中位数:

int median(vector<int> &v)
{
    size_t n = v.size() / 2;
    nth_element(v.begin(), v.begin()+n, v.end());
    return v[n];
}