Ежедневный бит (е) C ++ # 40, Алгоритм разделения линейной сложности: std:: nth_element
std::nth_element — это алгоритм разделения с линейной сложностью, который переупорядочивает элементы заданного диапазона, так что этот элемент под средним итератором является элементом, который был бы там, если бы диапазон был отсортирован.
Это может быть полезно для выбора различных процентилей вне диапазона (например, медианы) без явной сортировки.
Линейная сложность алгоритма приводит к нетривиальной постоянной стоимости, а это означает, что если вы ищете небольшое количество элементов, алгоритм std::partial_sort может быть быстрее.
#include <algorithm>
#include <vector>
std::vector<int> data{8, 6, 2, 4, 3, 5, 9, 1};
std::nth_element(data.begin(), data.begin()+3, data.end());
// *(data.begin()+3) == 4
// because the sorted range would be {1, 2, 3, 4...}
