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

2022-01-24 00:00:00 algorithm containers c++ stl median

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

Let's say I need to retrieve the median from a sequence of 1000000 random numeric values.

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

If using anything but std::list, I have no (built-in) way to sort sequence for median calculation.

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

If using std::list, I can't randomly access values to retrieve middle (median) of sorted sequence.

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

Is it better to implement sorting myself and go with e.g. std::vector, or is it better to use std::list and use std::list::iterator to for-loop-walk to the median value? The latter seems less overheadish, but also feels more ugly..

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

Or are there more and better alternatives for me?

推荐答案

任何随机访问容器(如 std::vector)都可以使用标准 std::sort 算法，在 <algorithm> 标头中可用.

Any random-access container (like std::vector) can be sorted with the standard std::sort algorithm, available in the <algorithm> header.

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

For finding the median, it would be quicker to use std::nth_element; this does enough of a sort to put one chosen element in the correct position, but doesn't completely sort the container. So you could find the median like this:

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

相关文章