nth_element是如何实现的？

Question

Whosebug 和其他地方有很多声明 nth_element 是 O(n) 并且通常使用 Introselect 实现：http://en.cppreference.com/w/cpp/algorithm/nth_element

我想知道这是如何实现的。我查看了 Wikipedia's explanation of Introselect，这让我更加困惑。算法如何在 QSort 和 Median-of-Medians 之间切换？

我在这里找到了 Introsort 论文：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5196&rep=rep1&type=pdf 但是上面写着：

In this paper, we concentrate on the sorting problem and return to the selection problem only briefly in a later section.

我试图通读 STL 本身以了解 nth_element 是如何实现的，但这很快就会变得毛茸茸。

谁能告诉我如何实现 Introselect 的伪代码？或者更好的是，当然不是 STL 的实际 C++ 代码 :)

Answer 1

免责声明：我不知道 std::nth_element 在任何标准库中是如何实现的。

如果您知道 Quicksort 的工作原理，则可以轻松修改它以执行此算法所需的操作。 Quicksort 的基本思想是在每一步中，将数组分成两部分，使得所有小于主元的元素都在左子数组中，所有等于或大于主元的元素都在右子数组中. （称为三元快速排序的快速排序的一种修改创建了第三个子数组，其中所有元素都等于主元。然后右子数组仅包含严格大于主元的条目。）然后快速排序通过递归地对左右子数组进行排序-数组。

如果您只想移动第 n 个元素，而不是递归到 both 个子数组，您可以在每一步中告诉您是否需要下降到左侧或右侧子阵列。（你知道这一点是因为排序数组中的第 n 个元素有索引 n 所以它变成了比较索引的问题。）所以 - 除非你的 Quicksort 遭受最坏情况的退化——你在每一步中将剩余数组的大小大致减半。（你永远不会再看另一个子数组。）因此，平均而言，你在每一步中处理以下长度的数组：

Θ(N)
Θ(N / 2)
Θ(N / 4)
…

每一步都与它处理的数组的长度成线性关系。（你循环一次并决定每个元素应该进入哪个子数组，这取决于它与枢轴的比较。）

可以看到经过Θ(log(N))步，我们最终会到达一个单例数组，大功告成。如果你总结 N (1 + 1/2 + 1/4 + …)，你将得到 2 N。或者，在一般情况下，由于我们不能希望枢轴总是恰好是中位数，因此大约为 Θ(N).

Answer 2

STL（我认为是 3.3 版）的代码是这样的：

template <class _RandomAccessIter, class _Tp>
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
                   _RandomAccessIter __last, _Tp*) {
  while (__last - __first > 3) {
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1))));
    if (__cut <= __nth)
      __first = __cut;
    else 
      __last = __cut;
  }
  __insertion_sort(__first, __last);
}

让我们稍微简化一下：

template <class Iter, class T>
void nth_element(Iter first, Iter nth, Iter last) {
  while (last - first > 3) {
    Iter cut =
      unguarded_partition(first, last,
                          T(median(*first,
                                   *(first + (last - first)/2),
                                   *(last - 1))));
    if (cut <= nth)
      first = cut;
    else 
      last = cut;
  }
  insertion_sort(first, last);
}

我在这里所做的是删除双下划线和 _Uppercase 的东西，这只是为了保护代码免受用户可以合法定义为宏的东西的影响。我还删除了最后一个参数，它应该只有助于模板类型推导，并为简洁起见重命名了迭代器类型。

正如您现在应该看到的那样，它重复对范围进行分区，直到剩余范围中剩余的元素少于四个，然后对其进行简单排序。

现在，为什么是 O(n)？首先，最多三个元素的最终排序是 O(1)，因为三个元素的最大值。现在，剩下的就是重复的分区。分区本身就是 O(n)。不过在这里，每一步都会将下一步需要接触的元素数量减半，所以你有 O(n) + O(n/2) + O(n/4) + O(n/8) 如果你把它加起来，它小于 O(2n)。由于 O(2n) = O(n)，您平均具有线性复杂度。

Answer 3

你问了两个问题，一个是名义上的

How is nth_element Implemented?

您已经回答的问题：

There are a lot of claims on Whosebug and elsewhere that nth_element is O(n) and that it is typically implemented with Introselect.

我也可以通过查看我的 stdlib 实现来确认这一点。（稍后会详细介绍。）

还有你不明白的答案：

How can an algorithm switch between QSort and Median-of-Medians?

让我们看一下我从 stdlib 中提取的伪代码：

nth_element(first, nth, last)
{ 
  if (first == last || nth == last)
    return;

  introselect(first, nth, last, log2(last - first) * 2);
}

introselect(first, nth, last, depth_limit)
{
  while (last - first > 3)
  {
      if (depth_limit == 0)
      {
          // [NOTE by editor] This should be median-of-medians instead.
          // [NOTE by editor] See Azmisov's comment below
          heap_select(first, nth + 1, last);
          // Place the nth largest element in its final position.
          iter_swap(first, nth);
          return;
      }
      --depth_limit;
      cut = unguarded_partition_pivot(first, last);
      if (cut <= nth)
        first = cut;
      else
        last = cut;
  }
  insertion_sort(first, last);
}

无需详细了解引用函数 heap_select 和 unguarded_partition_pivot 我们可以清楚地看到，nth_element 给出了 introselect 2 * log2(size) 细分步骤（是需要的两倍通过 quickselect 在最好的情况下）直到 heap_select 开始并永久解决问题。

nth_element是如何实现的？

How is nth_element Implemented?

c++

algorithm

stl

selection

nth-element