C-标准库排序算法-stdsort-使用详解
目录
C++ 标准库排序算法 std::sort 使用详解
- C++ 中确实存在很多经典排序算法（快速排序、归并排序、堆排序、希尔排序等）。
- 每种排序算法都有其优势和适用场景（比如归并适合链表，桶排序适合范围已知的整数，堆排序适合实时取最大/最小值）。
- C++ 标准库中的
std::sort内部实现是一个 混合排序算法，主要基于 快速排序（QuickSort），在某些情况下会退化为堆排序或插入排序，所以它的时间复杂度一般为 O(N log N)。它不仅能对内置类型（如int、double）排序，还能自定义比较规则，甚至结合 C++20 的并行执行策略实现更高效的排序。
本文将从最基础的用法开始，逐步介绍 std::sort 的高级特性。
C++ std::sort 参数详解
在 C++ 中，std::sort 是最常用的排序函数之一。它定义在 <algorithm> 头文件中，能对容器（如 vector、array）或数组中的元素进行快速排序。
函数原型（常见用法）：
template <class RandomIt>
void sort(RandomIt first, RandomIt last);
template <class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);可以看到，std::sort 一共有两个版本：
两个参数：默认按升序排序。
- 排序的对象范围由两个迭代器决定：
first→ 排序起点last→ 排序终点的“下一个位置”- 注意是 左闭右开区间
[first, last)，包含first指向的元素，但不包含last指向的元素。
三个参数：用户可以指定排序规则。
- 默认情况下，
std::sort使用<作为比较规则（升序）。
但你可以传入一个比较函数（或函数对象、Lambda 表达式），来自定义排序规则。
- 默认情况下，
1. 基础用法：升序排序
如果不传入自定义比较函数，std::sort 默认会使用 小于运算符 < 进行比较，从而将元素按升序排列。
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> values = { 3, 5, 1, 4, 2 };
// 默认升序排序
std::sort(values.begin(), values.end());
for (int v : values)
std::cout << v << " ";
// 输出：1 2 3 4 5
}2. 降序排序
如果想要从大到小排列，可以传入标准库提供的 std::greater<> 比较器：
#include <functional> // std::greater
std::sort(values.begin(), values.end(), std::greater<int>());
// 输出：5 4 3 2 13. 自定义比较规则
有时候我们需要更复杂的排序逻辑，这时可以传入一个 自定义比较函数（函数指针、函数对象或 Lambda 表达式）。
例如，让数字 1 永远排在最后：
std::sort(values.begin(), values.end(), [](int a, int b) {
if (a == 1) return false; // a==1 时排在 b 之后
if (b == 1) return true; // b==1 时排在 a 之前
return a < b; // 其他情况正常升序
});
// 输出：2 3 4 5 1 注意：比较函数必须返回 bool，且要满足 严格弱序关系（Strict Weak Ordering），否则结果可能是未定义的。
4. std::sort 的函数签名
标准库中 std::sort 的定义大致如下：
// 默认比较：使用 operator<
template<class RandomIt>
void sort(RandomIt first, RandomIt last);
// 自定义比较器
template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);
// C++17 起：并行排序（可指定执行策略）
template<class ExecutionPolicy, class RandomIt>
void sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last);
template<class ExecutionPolicy, class RandomIt, class Compare>
void sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp);参数说明：
- first, last
迭代器范围[first, last)，要排序的区间。 - comp
自定义比较函数（bool comp(const T& a, const T& b)）。 - policy（C++17 起）
执行策略，例如std::execution::seq（顺序执行）、std::execution::par（并行执行）。
5. 使用要求
为了让 std::sort 工作正常，需要满足以下条件：
迭代器必须是 随机访问迭代器（Random Access Iterator），例如
std::vector、std::array、原生数组。
（std::list不行，因为它只支持双向迭代器。）元素类型必须：
- 可交换（Swappable）
- 可移动构造（MoveConstructible）
- 可移动赋值（MoveAssignable）
自定义比较器必须满足 Compare 要求（即符合严格弱序）。
6. 时间复杂度
- 默认比较或自定义比较：
O(N log N) 次比较（这里 N =last - first）。 - 实现一般基于 快速排序 + 堆排序 + 插入排序 的混合策略。
7. 示例：排序结构体
std::sort 常用于排序对象数组。我们可以自定义排序规则：
#include <string>
struct Person {
std::string name;
int age;
};
int main() {
std::vector<Person> people = {
{"Alice", 25},
{"Bob", 30},
{"Charlie", 20}
};
// 按年龄升序
std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
return a.age < b.age;
});
for (const auto& p : people)
std::cout << p.name << " " << p.age << "\n";
// 输出：
// Charlie 20
// Alice 25
// Bob 30
}8. 总结
std::sort是 C++ 排序的首选，效率高，接口灵活。- 默认是升序排序，可以用
std::greater<>或自定义比较器实现降序或更复杂的规则。 - 内部复杂度是 O(N log N)，但实现经过高度优化。
- 迭代器必须支持随机访问，类型必须可移动、可交换。
- C++17 之后可以使用执行策略（并行排序）。
建议：
- 简单场景直接用默认排序；
- 如果有特殊规则，写一个清晰的比较函数；
- 不要忘了比较函数要符合 严格弱序，否则可能出现奇怪的排序结果。