How is nth_element Implemented?

你已经回答过：

There are a lot of claims on StackOverflow 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,last,log2(last - first) * 2);
}

introselect(first,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_pa​​rtition_pivot,我们可以清楚地看到,nth_element给出了introselect 2 * log2(大小)细分步骤(在最佳情况下是quickselect所需的两倍),直到heap_select启动并解决了好.