算法nth_element [关闭]
-
25-09-2019 - |
题
我最近发现,存在一个称为 nth_element 在该方法中STL。引述的描述:
Nth_element类似于 partial_sort,因为它部分地 定购一个范围的元素:它 排列范围[第一,最后一个)这样 该元件由指向 迭代第n是一样的 元件,这将是在该位置 如果整个范围[第一,最后一个)有 被排序。此外,没有任何的 在范围的元素[第n个,最后一个)是 小于任何在所述元件的 范围[第一,第n个)。
它声称具有平均为O(n)的复杂性。如何算法的工作?我找不到任何解释它。
解决方案
这就是所谓的选择算法和维基百科有一个体面的网页上: HTTP://en.wikipedia。组织/维基/ Selection_algorithm
另外阅读有关顺序统计: http://en.wikipedia.org/wiki/Order_statistic
不隶属于 StackOverflow