`sort` 函数是 C++ STL（标准模板库）中 `algorithm` 头文件提供的**高效、泛型、不稳定排序算法**，底层通常采用混合排序策略（如 introsort：快速排序 + 堆排序 + 插入排序），平均时间复杂度为 $O(n \log n)$，最坏情况仍为 $O(n \log n)$ [ref_1][ref_2]。其核心设计遵循“**分离算法与数据结构**”原则，通过迭代器抽象操作任意支持随机访问的容器（如 `vector`、`array`、原生数组），并允许用户自定义比较逻辑。 --- ### 一、基本语法与参数解析 ```cpp #include <algorithm> #include <vector> #include <iostream> // 1. 默认升序（要求元素类型支持 operator<） std::sort(first, last); // 2. 自定义比较函数/对象（支持降序、多级排序等） std::sort(first, last, comp); ``` | 参数 | 类型 | 说明 | |------|------|------| | `first` | 随机访问迭代器（如 `vector<int>::iterator`） | 指向排序范围起始位置（含） | | `last` | 同上 | 指向排序范围结束位置（不含），即 `[first, last)` 左闭右开区间 | | `comp` | 可调用对象（函数指针、lambda、functor） | 二元谓词，返回 `true` 表示第一个参数应排在第二个之前；必须满足**严格弱序**（strict weak ordering）[ref_2] | > ✅ 正确 `comp(a,b)` 示例：`a < b`（升序）、`a > b`（降序）、`a.length() < b.length()`（按字符串长度） > ❌ 错误：`a <= b`（不满足反对称性）、`rand() % 2`（非确定性） --- ### 二、典型使用场景与代码示例 #### ▶ 基础类型升/降序 ```cpp #include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> nums = {5, 2, 8, 1, 9}; // 升序（默认） std::sort(nums.begin(), nums.end()); // → {1,2,5,8,9} // 降序：使用 std::greater<int>() 或 lambda std::sort(nums.begin(), nums.end(), std::greater<int>()); // → {9,8,5,2,1} // 等价 lambda： std::sort(nums.begin(), nums.end(), [](int a, int b) { return a > b; }); return 0; } ``` #### ▶ 字符串与字符数组排序 ```cpp #include <string> #include <algorithm> std::string s = "hello"; std::sort(s.begin(), s.end()); // → "ehllo" char arr[] = "world"; std::sort(arr, arr + 5); // → "dlorw" ``` #### ▶ 结构体排序（需自定义 `cmp`） ```cpp struct Student { std::string name; int score; int age; }; bool cmpByScore(const Student& a, const Student& b) { return a.score > b.score; // 按分数降序 } bool cmpByNameThenAge(const Student& a, const Student& b) { if (a.name != b.name) return a.name < b.name; return a.age < b.age; // 同名则按年龄升序 } int main() { std::vector<Student> students = { {"Alice", 95, 20}, {"Bob", 87, 19}, {"Alice", 92, 21} }; std::sort(students.begin(), students.end(), cmpByNameThenAge); // 结果：{"Alice",92,21}, {"Alice",95,20}, {"Bob",87,19} —— 注意：name 相同者按 age 升序 } ``` #### ▶ Lambda 实现动态排序（C++11+） ```cpp std::vector<std::pair<std::string, int>> data = {{"apple", 3}, {"banana", 1}, {"cherry", 2}}; // 按 second 升序，second 相同时按 first 字典序 std::sort(data.begin(), data.end(), [](const auto& a, const auto& b) { return a.second != b.second ? a.second < b.second : a.first < b.first; }); // → {{"banana",1}, {"cherry",2}, {"apple",3}} ``` --- ### 三、关键注意事项 | 项目 | 说明 | 来源依据 | |------|------|----------| | **头文件** | 必须 `#include <algorithm>`，否则编译失败 | [ref_2] | | **容器限制** | 仅支持**随机访问迭代器**容器（`vector`, `deque`, `array`, 原生数组），不支持 `list`（应使用 `list::sort()`） | [ref_1] | | **稳定性** | `std::sort` 是**不稳定排序**（相等元素相对位置可能改变）；如需稳定，用 `std::stable_sort` | [ref_3] | | **原地排序** | 直接修改原容器，**不返回新容器**（区别于 Python 的 `sorted()`） | [ref_4] | | **自定义类型前提** | 若未提供 `comp`，类型必须重载 `operator<`，否则编译报错 | [ref_2] | --- ### 四、C++ 与 Python 排序对比（关键差异） | 特性 | C++ `std::sort` | Python `list.sort()` / `sorted()` | |------|------------------|-----------------------------------| | **作用对象** | 迭代器范围（通用） | 仅限 `list`（前者）或任意可迭代对象（后者） | | **是否原地** | 是（修改原容器） | `list.sort()` 是，`sorted()` 否 | | **返回值** | `void` | `list.sort()` 返回 `None`，`sorted()` 返回新列表 | | **稳定性** | 不稳定 | `list.sort()` 和 `sorted()` 均为**稳定排序** | | **自定义键** | 通过 `comp` 谓词（需手动实现键提取逻辑） | 支持 `key=` 参数（如 `key=len`） | > 示例：Python 中 `sorted(words, key=len)` 在 C++ 中需写为： > `std::sort(words.begin(), words.end(), [](const auto& a, const auto& b) { return a.size() < b.size(); });` [ref_4] --- 综上，`std::sort` 是 C++ 中性能与灵活性兼顾的核心排序工具，其设计哲学强调**零开销抽象**与**策略可插拔性**，熟练掌握 `comp` 谓词编写是解锁高级排序能力的关键 [ref_1][ref_3]。