std::partial_sort仅适用于取前K小（或大）元素且要求有序、其余元素顺序无关的场景；误用于子区间排序或Top-K无序需求时，应分别改用std::sort或std::nth_element。
std::partial_sort 什么时候该用，什么时候不该用
它只适合「取前 K 小（或大）元素，且要求这 K 个元素有序，其余元素顺序无所谓」的场景。不是「对某段子数组排序」，也不是「Top-K 但不要求有序」——后者用 std::nth_element 更快；前者直接用 std::sort 更直白。
常见误用：想把数组中间一段排好序，却写了 std::partial_sort，结果前 K 个被重排，后面乱了——这是设计使然，不是 bug。
- 要「局部子区间排序」→ 用
std::sort(begin + i, begin + j) - 要「快速拿到第 K 小值，不关心前 K 是否有序」→ 用
std::nth_element - 要「前 K 小且升序排列，不在乎剩下部分」→ 才轮到
std::partial_sort
怎么调用 std::partial_sort 才不越界
它的签名是 std::partial_sort(first, middle, last)，其中 [first, last) 是整个范围，[first, middle) 是你要排好序的前 K 个位置。关键约束：必须满足 first ≤ middle ≤ last，否则行为未定义（多数实现会崩溃或静默出错）。
比如你有一个含 10 个元素的 std::vector<int> v</int>，想取最小的 3 个并排序：
立即学习“C++免费学习笔记（深入）”；
std::partial_sort(v.begin(), v.begin() + 3, v.end());
如果写成 v.begin() + 5 而 v.size() 只有 4，运行时大概率触发断言失败或内存越界。
- 务必检查
middle - first ≤ last - first，也就是 K ≤ 总长度 - 迭代器类型要匹配：不能混用
int*和std::vector::iterator - 自定义比较器传参位置在最后，别漏掉：
std::partial_sort(..., std::greater{})
性能差异：比 full sort 快多少？
时间复杂度是 O(N log K)，其中 N 是总长度，K 是要排序的前 K 个数。当 K ≪ N 时优势明显：比如 N=1e6、K=10，它只建一个 10 元素堆，而 std::sort 是 O(N log N) ≈ 2e7 次比较，std::partial_sort 约 1e6 × log₂10 ≈ 3e6 次。
但 K 接近 N 时（比如 K = N−1），它反而可能比 std::sort 慢，因为内部用了堆操作+插入排序混合策略，常数项更高。
- K std::partial_sort
- K > 30% × N：直接
std::sort更稳 - 不确定 K 大小？先用
std::nth_element定位 pivot，再对前 K 用std::sort
容易被忽略的稳定性与自定义类型问题
std::partial_sort 不稳定——相等元素的相对顺序可能改变。如果你依赖稳定排序（比如按优先级取任务，相同优先级要保持提交顺序），它不合适。
对自定义类型，必须提供可比较的 operatoroperator 的结构体直接用会编译失败，错误信息通常很长，关键线索是类似 invalid operands to binary expression 或 no match for 'operator。
- 确保比较器满足严格弱序（strict weak ordering），尤其注意
a 必须为 false - 移动语义影响：C++11 后默认使用移动构造（如果类型支持），若对象不可移动，会退回到拷贝，注意性能回退
- 容器需支持随机访问迭代器：
std::list不能用，std::vector、std::array、原生数组可以
实际用的时候，先问自己一句：我真的需要前 K 个“已排序”吗？还是只要“前 K 小”就够了？答案决定该敲哪一行代码。
