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 是两个非常实用的算法，适用于只需要部分有序数据的场景。它们都定义在
nth_element：快速定位第n小的元素
nth_element 用于将范围中的第n个位置设置为排序后应出现的元素，并保证该位置之前的元素都不大于它，之后的元素都不小于它。它不保证左右两部分的内部有序。
这个算法平均时间复杂度为 O(n)，适合用于查找中位数、第k大元素等场景。
基本用法：
#include#include #include std::vector 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个元素是有序的，其余元素则无序。
时间复杂度约为 O(n log m)，其中n是整个区间的长度，m是要排序的元素个数。适合“取Top K”类问题。
基本用法：
std::vectorv = {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 更合适。
基本上就这些。两个算法都利用了分治和堆的思想，在实际开发中能显著提升性能。
