我发现自己经常遇到这个问题：给定一个序列，找到k最小的元素。这个问题并不难，但我想要的是一种既安全（很少出错）又能很好地传达意图的"惯用"方法。所以最后要做的是对序列进行排序，然后取第一个k元素：
std::sort(container.begin(),container.end());
std::vector<T> k_smallest(container.begin(),container.begin() + k);
在我看来，这既安全又容易理解，但这里的复杂性是nlogn+k，而不仅仅是n。你们是如何做到这一点的，有没有一种idomatic的方法（使用一些模糊的函数）可以在不需要重新实现轮子的情况下提供最佳的复杂性
std:：nth_element（）-平均线性复杂度。
nth_element是一种部分排序算法，它在[第一，最后）使得：
- 由第n个指向的元素被更改为如果对[第一个，最后一个）进行排序，则该位置将出现的任何元素
- 该新的第n个元素之前的所有元素都小于或等于新的第N个元素之后的元素
您可能想看看partial_sort（）
它理解起来很简单，不需要额外的工作，并且如果只关心第k个元素，那么它会比sort()更好[或者至少不会更差]。
为了获得最佳性能，您可能想要使用选择算法，但这需要更多的工作。
第一个算法：
步骤：
- 使用"选择"算法查找第k_th个元素
- 选择它作为枢轴并执行分区（来自快速排序算法），从而使枢轴剩下最小的k个元素
复杂性：O（n）最坏情况
第二算法：
步骤：
- 使用make_heap从数组元素中创建堆
- 执行k次以下操作：
- 读取第一个元素
- 使用pop_heap弹出
您可以使用priority队列的方法（c'tor、top、pop）来实现相同的结果，而不需要知道后面的算法。
复杂性：O（n+k*log（n））最坏情况