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

Question

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

如果使用 除 std::list 的任何东西，我没有（内置）方法来对序列进行排序以进行中位数计算。

如果使用 std::list ，我不能随机访问值来检索排序序列的中间（中位数）。

自己实现排序并使用例如 std::vector 是否更好，或者使用 std::list 并使用 std::list::iterator 到中位数更好价值？后者似乎不那么开销，但也感觉更难看..

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

原文由 sharkin 发布，翻译遵循 CC BY-SA 4.0 许可协议

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];
}

原文由 Mike Seymour 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

犰狳 有一个看起来像答案 https://stackoverflow.com/a/34077478 by https://stackoverflow.com/users/2608582/matthew-fioravante 中的实现

它使用一个调用 nth_element 和一个调用 max_element 它在这里： https ://gitlab.com/conradsnicta/armadillo-code/-/blob/9.900.x/ 包括/armadillo_bits/op_median_meat.hpp#L380

 //! find the median value of a std::vector (contents is modified)
template<typename eT>
inline
eT
op_median::direct_median(std::vector<eT>& X)
  {
  arma_extra_debug_sigprint();

  const uword n_elem = uword(X.size());
  const uword half   = n_elem/2;

  typename std::vector<eT>::iterator first    = X.begin();
  typename std::vector<eT>::iterator nth      = first + half;
  typename std::vector<eT>::iterator pastlast = X.end();

  std::nth_element(first, nth, pastlast);

  if((n_elem % 2) == 0)  // even number of elements
    {
    typename std::vector<eT>::iterator start   = X.begin();
    typename std::vector<eT>::iterator pastend = start + half;

    const eT val1 = (*nth);
    const eT val2 = (*(std::max_element(start, pastend)));

    return op_mean::robust_mean(val1, val2);
    }
  else  // odd number of elements
    {
    return (*nth);
    }
  }

原文由 Alessandro Jacopson 发布，翻译遵循 CC BY-SA 4.0 许可协议