c++ - 为什么 std::sort() 比 std::make_heap() 快？

Question

我有 13721057我的元素 std::vector<Sequence> .我需要对这个 vector 进行排序并获取前 25 个元素。我想，因为你可以在 O(N) 中构建一个堆弹出 25 个元素(每个元素都是 O(logN) )一定比在 O(NlogN) 中对整个 vector 排序更快.

但是，当我对代码计时时:

clock_t tStart = clock();
sort(mostFrequent.begin(), mostFrequent.end(), greater<Sequence>());
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

对比

clock_t tStart = clock();
make_heap(mostFrequent.begin(), mostFrequent.end());
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

对整个 vector 进行排序似乎要快得多。这是为什么？

Answer 1

这不是一个完整的答案，但要从 13721057 中获取前 25 个元素，您最好使用 partial_sort .

如果只需要第25个元素，那么nth_element .

作为旁注。为了按排序顺序获取第一个小于 X 的元素，我会使用 lambda 执行 auto mid = std::partition，然后执行 std::sort(begin,mid)。可能有更好的方法。