C++STL算法nth_element和partial_sort使用

nth_element用于快速定位第n小元素，保证其前后的元素相对有序，平均时间复杂度O(n)；partial_sort则将最小的n个元素排序置于前端，时间复杂度O(n log m)，适用于Top K场景。根据是否需要有序结果选择：仅需第k元素用nth_element，需前k有序用partial_sort，两者均优于全排序。

在C++标准库中，nth_element 和 partial_sort 是两个非常实用的算法，适用于只需要部分有序数据的场景。它们都定义在 <algorithm> 头文件中，能够在不需要完全排序的情况下高效完成任务。

nth_element：快速定位第n小的元素

nth_element 用于将范围中的第n个位置设置为排序后应出现的元素，并保证该位置之前的元素都不大于它，之后的元素都不小于它。它不保证左右两部分的内部有序。

这个算法平均时间复杂度为 O(n)，适合用于查找中位数、第k大元素等场景。

#include <algorithm>
#include <vector>
#include <iostream>

std::vector<int> v = {5, 1, 6, 3, 8, 2};
// 找出第3小的元素（索引2）
std::nth_element(v.begin(), v.begin() + 2, v.end());
std::cout << "第3小的元素是：" << v[2] << '\n'; // 输出可能是3
// 此时v[0..1] ≤ v[2]，v[3..end] ≥ v[2]

注意：调用后只有第n个位置的值是确定的，其余元素顺序不确定。如果想获取中位数，这是比全排序更高效的选择。

立即学习“C++免费学习笔记（深入）”；

partial_sort：部分排序前n个最小元素

partial_sort 会将区间中最小的n个元素提取出来，并按顺序放在开头。它保证前n个元素是有序的，其余元素则无序。

算家云

高效、便捷的人工智能算力服务平台

37

查看详情

时间复杂度约为 O(n log m)，其中n是整个区间的长度，m是要排序的元素个数。适合“取Top K”类问题。

std::vector<int> v = {5, 1, 6, 3, 8, 2, 9};
// 将最小的4个元素按序排在前面
std::partial_sort(v.begin(), v.begin() + 4, v.end());
// 结果类似：[1, 2, 3, 5, ...]（后面的6,8,9,2等无序）
for (int x : v) std::cout << x << ' ';

如果只关心前几名的成绩或最高频的词汇，用 partial_sort 比 sort 更高效。

如何选择：nth_element vs partial_sort

根据需求选择合适的算法：

• 只需要第k小/大的元素？用 nth_element
• 需要前k小/大的元素且要求有序？用 partial_sort
• 前k个元素不要求顺序？nth_element 更快
• 数据量大但k较小？partial_sort 表现良好

例如，在找中位数时，使用 nth_element 可避免 O(n log n) 的完整排序开销。而在实现“排行榜前10”功能时，partial_sort 更合适。

以上就是C++STL算法nth_element和partial_sort使用的详细内容，更多请关注php中文网其它相关文章！