STL排序算法怎么选？sort、stable_sort、partial_sort区别详解

普通排序首选std::sort，适用于完整排序且不关心相等元素顺序的情况，平均时间复杂度O(n log n)，不稳定；2. 保持稳定顺序用std::stable_sort，适合需保留相同元素原始顺序的场景，如多字段排序，时间复杂度接近O(n log n)；3. 只取前K个值时使用std::partial_sort，用于高效获取最大或最小的k个元素，时间复杂度约为O(n log k)，不需全量排序。

在使用 STL 进行排序时，sort、stable_sort 和 partial_sort 是三个常用的排序算法。它们各有适用场景，选错可能影响性能或结果正确性。

1. 普通排序首选：std::sort

如果你只是想对一个序列进行完整排序，并且不关心相同元素的相对顺序，那首选就是 std::sort。

• 它是最快的通用排序算法之一，平均时间复杂度为 O(n log n)
• 不保证相等元素的顺序不变（不稳定）
• 适合大多数需要完全排序的情况，比如排序整数数组、结构体列表等

举个例子：

std::vector<int> nums = {5, 2, 8, 1, 3};
std::sort(nums.begin(), nums.end());

执行后，nums 就会被排成升序 {1, 2, 3, 5, 8}。

2. 保持稳定顺序：std::stable_sort

当你希望相同元素之间的原始顺序保留下来，就要用 std::stable_sort。

• 时间复杂度略高一些，但多数实现仍然接近 O(n log n)
• 稳定排序适用于处理结构体中多个字段的排序，比如先按类别排序，再按时间排序，不能打乱第一次排序的结果

比如你有一个学生列表，先按成绩排序，再按名字排序，这时候如果不稳定，第二次排序可能会打乱第一次的成绩顺序。

std::vector<std::pair<int, std::string>> students = {
    {90, "Alice"}, {85, "Bob"}, {90, "Charlie"}
};
std::stable_sort(students.begin(), students.end(),
                 [](const auto& a, const auto& b) {
                     return a.first > b.first;
                 });

这样，两个得 90 分的学生会保持他们在原数组中的相对位置。

3. 只取前 K 个最大/最小值：std::partial_sort

当你要从一堆数据中找出“前几个最大的”或者“前几个最小的”，不需要整个数组都排序，就可以用 partial_sort。

• 比如你需要从 1000 个数字里取出前 10 个最大的，这时候全部排序效率不高
• 它的时间复杂度大约是 O(n log k)，k 是你要取的数量

使用方式稍微有点不同：

std::vector<int> nums = {5, 2, 8, 1, 3, 7, 4, 6};
std::partial_sort(nums.begin(), nums.begin() + 3, nums.end(), std::greater<>());

// 此时前3个是最大的三个：8,7,6（顺序不一定准确），后面则是未排序的

如果你想获取前 k 个小的，可以去掉 std::greater<>()，默认是升序。

总结一下怎么选：

• 要排序全部元素，不在乎稳定性？→ 用 sort
• 需要保持相等元素的顺序？→ 用 stable_sort
• 只需要一部分最大/最小元素？→ 用 partial_sort

基本上就这些选择逻辑，不复杂但容易忽略应用场景差异。