在StackOverflow和其他地方有很多索赔,nth_element是O(n),它通常用Introselect实现：
http://en.cppreference.com/w/cpp/algorithm/nth_element
我想知道如何实现这一点.我看着Wikipedia’s explanation of Introselect,只是让我更困惑. QSort和Median-Med的算法如何切换？
我在这里发现了Introsort的文章：@L_502_2@但是说：
In this paper,we concentrate on the sorting problem and return to the selection problem only briefly in a later section.
我试图阅读STL本身来了解如何实现nth_element,但是这样做真的很快.
解决方法
你问了两个问题,一个是题目
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?
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_partition_pivot,我们可以清楚地看到,nth_element给出了introselect 2 * log2(大小)细分步骤(在最佳情况下是quickselect所需的两倍),直到heap_select启动并解决了好.
