引言
排序是编程中最常见的数据处理操作之一。C++ STL（标准模板库）为我们提供了多种高效且灵活的排序相关算法。本文将详细介绍 STL 排序算法，包括 sort、stable_sort、partial_sort、partial_sort_copy、nth_element、is_sorted 及 is_sorted_until。
1 std::sort —— 高效的通用排序算法
原理
std::sort 是 STL 中最常用的排序算法，采用混合排序（IntroSort），结合了快速排序、堆排序和插入排序的优点。它在平均情况下表现优异，最坏情况下也能保证较好的性能。
用法
#include <algorithm>
#include <vector>
#include <iostream>
// 按 Google 风格注释
int main() {
// 初始化一个整数向量
std::vector<int> vec = {5, 2, 9, 1, 5, 6};
// 对整个向量进行升序排序
std::sort(vec.begin(), vec.end());
// 输出排序结果
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
// 使用自定义比较器实现降序排序
std::sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
场景
需要对整个容器进行排序
不关心元素间的原始顺序（非稳定排序）
追求最快速度
性能
时间复杂度：O(nlogn)
空间复杂度：O(logn)
2 std::stable_sort —— 保持相等元素顺序的排序
原理
std::stable_sort 保证相等元素的原始顺序不变，底层实现通常为归并排序，最坏情况下时间复杂度也为 O(nlogn)。
用法
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
struct Person {
std::string name;
int age;
};
// Google 风格注释
int main() {
// 初始化人员列表
std::vector<Person> people = {
{"Alice", 30}, {"Bob", 25}, {"Charlie", 25}, {"David", 35}
};
// 按年龄排序，保持原始顺序
std::stable_sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
return a.age < b.age;
});
for (const auto& person : people) {
std::cout << person.name << " " << person.age << std::endl;
}
return 0;
}
场景
需要保持相等元素原始顺序（如多字段排序）
稳定性优先于速度
性能
时间复杂度：O(nlogn)
空间复杂度：O(n)（可能需要额外空间）
3 std::partial_sort —— 局部排序，适合 Top-K 问题
原理
std::partial_sort 只对前 k 个元素进行排序，剩余元素无序。底层通常采用堆排序。
用法
#include <algorithm>
#include <vector>
#include <iostream>
// Google 风格注释
int main() {
// 初始化向量
std::vector<int> vec = {10, 3, 5, 8, 2, 7};
// 只排序前 3 个元素，剩下的无序
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
// 输出前 3 个最小值
for (int i = 0; i < 3; ++i) {
std::cout << vec[i] << " ";
}
std::cout << std::endl;
return 0;
}
场景
只关心前k个最小/最大元素（如 Top-K）
比完全排序更高效
性能
时间复杂度：O(n+klogk)
4 std::partial_sort_copy —— 局部排序并拷贝到新容器
原理
std::partial_sort_copy 将输入区间的前 k 个最小（或最大）元素排序后拷贝到目标区间，源容器不变。
用法
#include <algorithm>
#include <vector>
#include <iostream>
// Google 风格注释
int main() {
std::vector<int> src = {7, 2, 5, 9, 1, 4};
std::vector<int> dst(3);
// 拷贝并排序 src 的前 3 个最小值到 dst
std::partial_sort_copy(src.begin(), src.end(), dst.begin(), dst.end());
for (int num : dst) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
场景
只需要部分排序结果，且不希望修改原容器
Top-K 结果拷贝到新容器
性能
时间复杂度：O(n+klogk)
5 std::nth_element —— 找到第 n 小（大）元素
原理
std::nth_element 是快速选择算法的实现。它调整容器，使第 n 个位置上的元素正好是排序后该位置的元素，左侧元素都不大于它，右侧都不小于它，但左右两侧无序。
用法
#include <algorithm>
#include <vector>
#include <iostream>
// Google 风格注释
int main() {
std::vector<int> vec = {6, 2, 9, 1, 7, 5};
// 找到第 3 小元素（索引 2），并调整位置
std::nth_element(vec.begin(), vec.begin() + 2, vec.end());
std::cout << "第3小元素: " << vec[2] << std::endl;
// 输出前3个元素（不保证有序，但都 <= vec[2]）
for (int i = 0; i <= 2; ++i) {
std::cout << vec[i] << " ";
}
std::cout << std::endl;
return 0;
}
场景
只关心第n小/大元素
快速求中位数、分位数
Top-K 无序结果
性能
平均时间复杂度：O(n)
6 std::is_sorted 和 std::is_sorted_until —— 判断是否有序
原理
std::is_sorted检查整个区间是否有序。std::is_sorted_until返回第一个无序元素的迭代器。
用法
#include <algorithm>
#include <vector>
#include <iostream>
// Google 风格注释
int main() {
std::vector<int> vec = {1, 2, 3, 5, 4, 6};
// 判断是否完全有序
if (std::is_sorted(vec.begin(), vec.end())) {
std::cout << "向量已排序" << std::endl;
} else {
std::cout << "向量未排序" << std::endl;
}
// 找到第一个无序位置
auto it = std::is_sorted_until(vec.begin(), vec.end());
std::cout << "第一个无序元素: " << *it << std::endl;
return 0;
}
场景
判断容器是否已排序
快速定位无序区间
7 对比与扩展
传统排序方法
冒泡排序、选择排序、插入排序等：实现简单，但性能远不如 STL 算法。
STL 排序算法都经过高度优化，推荐优先使用。
STL 排序算法选择建议
评论区