快速方式部分排序对象

Question

我有一个例程，在这个例程中，我定义了一组对象(大约20)，称为Jet，其中有一个已定义的<，用于对它们进行排序。在它们被分类之后，我取最低的两个。做这件事的快速方法是什么？到目前为止，我想到的选择是：

1. boost::ptr_vector<Jet>使用内置的.sort()，取前两个，
2. boost::ptr_list<Jet>，使用.sort()，取前两个
3. 使用上面的列表，但不是排序，而是使用max_element，删除元素，然后再次运行。

我认为使用std::vector<Jet>是最糟糕的选择，因为:我不需要随机访问；排序将在内存中移动对象；调用push_back(Jet)时将复制对象。由于所需的复制，我还假设std::list<Jet>会比boost::ptr_list<Jet>更糟糕。我进一步假设，使用两次max_element比对整个列表进行排序要快。

我的逻辑听起来像吗？表现上的差异会很大吗？还有别的选择我没想过吗？

Answer 1

有一个标准库算法可以这样做：

std::vector<Jet> v;
// populate v
std::partial_sort(v.begin(), v.begin() + 2, v.end());

v[0]现在是最小的元素，v[1]现在是第二小的元素；剩下的元素是一个未指定的顺序。std::vector<>可以用std::deque<>代替，因为后者也有随机访问迭代器.

(请注意，我链接到的页面上提到的复杂性是不正确的；C++11§25.4.1.3表示复杂性是(last - first) * log(middle - first)。)

Answer 2

您的一个假设是正确的，因为存储指针而不是对象会更快。

但是，如果您只需要两个最小的元素，则不需要对任何内容进行排序。只需获取前两个元素，然后遍历vector或list的元素，并保留较小的元素。

Answer 3

如果需要最低的两个对象，您可以创建自己的搜索函数，该函数将在O(N)时间内运行。使用排序是O(N log N)时间。