STL排序算法如何选择最佳方案 sort stable_sort partial

STL排序算法如何选择最佳方案 sort stable_sort partial_sort区别

P粉602998670

发布： 2025-07-09 09:10:02

原创

1068人浏览过

普通排序首选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区别

在使用 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<>()，默认是升序。