部分排序算法的复杂度与nth_element算法的比较。

Question

根据cppreference.com，C++ STL排序算法的复杂度如下： sort: O(N log(N)) partial_sort: "大约" O(N log(M))，其中 M 是 distance(middle-first) nth_element: "平均" O(N)

然而，这似乎意味着，你可以使用 nth_element 然后对第一个范围进行排序，以给出总体复杂度为 O(N + M log(M))，这比 O(N log(M)) 稍好一些。这是否真实？我最好避免使用partial_sort吗？

- rlbond

---

当输入规模很大时，复杂度的顺序很重要。对于小输入，我认为这并不会有太大影响。 - taocp

非常有趣的问题。请参考本杰明·林德利在这个问题中对上一个答案的评论 - 他说，根据经验，在某些情况下这样做更快。 - Ami Tavory

Quickselect有一个很大的常数因子，所以我猜这只对相当大的M有意义。使用一些真实输入进行基准测试将会告诉您更多信息。 - Niklas B.

Answer 1

std::partial_sort 可以对你感兴趣的M个元素进行部分排序。另一方面，std::nth_element 只会给你一个数组，使得第n个元素被放置在左边的所有元素都比它小，右边的所有元素都比它大。

使用 std::partial_sort 的用例包括按排名顺序获取百万条记录中的前10个结果。使用 std::nth_element 来查找数组的中位数或查找考试结果中排名第10的人。

如果您只对性能特征感兴趣，对于较小的M值，std::partial_sort 比 std::nth_element 表现更佳（约为10,000）。有关此的详细分析，请参见：https://www.youtube.com/watch?v=-0tO3Eni2uo

视频摘要

std::nth_element 使用修改过的Quickselect算法，无论M是多少，都提供了O(N)的时间复杂度。

std::partial_sort 使用Heapselect算法，在M较小时比Quickselect表现更好。作为副作用，Heapselect的结束状态将给你一个堆，这意味着你可以免费获得Heapsort算法的前半部分。

std::partial_sort 优化了 M 相对于 N 很小的情况，例如从一个非常大的变长列表中获取前 10 个元素。但它并没有针对其他情况进行优化。

在 std::partial_sort 和 std::nth_element + std::sort 的竞赛中，std::partial_sort 在 M 很小时领先（M 较小），但一旦 M 不再很小时就被 std::nth_element + std::sort 超过了。

- Average Joe

---

Downvote 不是我给的，但你可以通过总结 YouTube 视频来改进你的答案。尽可能让答案自成一体。 - Rerito

Answer 2

经过广泛的测试，似乎对于我的用例来说，partial_sort 更快。我早有怀疑——但这似乎证实了它。

- rlbond