在 C++ 中，std::sort 是一个非常强大且常用的函数，用于对容器或数组中的元素进行排序。它定义在 <algorithm> 头文件中。
std::sort 的基本语法
std::sort 的基本语法有以下几种形式：
-
默认升序排序：
std::sort(first, last);first: 指向要排序范围的起始元素的迭代器（包含）。last: 指向要排序范围的结束元素之后一个位置的迭代器（不包含）。- 这种形式会使用元素的默认
<运算符进行比较，实现升序排序。
-
自定义比较规则排序：
std::sort(first, last, comp);first,last: 同上。comp: 一个可调用对象（函数指针、函数对象或 Lambda 表达式），用于定义比较规则。它接受两个参数，并返回一个bool值。如果第一个参数“小于”第二个参数（即应该排在第二个参数之前），则返回true。
std::sort 的特点
- 头文件： 必须包含
<algorithm>。 - 迭代器类型： 需要随机访问迭代器（RandomAccessIterator）。
std::vector、std::deque、std::string和 C 风格数组都提供随机访问迭代器，因此它们可以直接使用std::sort。std::list和std::forward_list不提供随机访问迭代器，它们有自己的sort()成员函数。 - 排序算法：
std::sort通常使用 IntroSort（内省式排序），这是一种混合排序算法，结合了快速排序、堆排序和插入排序的优点，以确保在各种情况下的平均和最坏时间复杂度都为 O(N log N)。 - 原地排序：
std::sort是原地排序算法，它直接修改原始容器中的元素，不创建副本。
使用示例
1. 对 std::vector<int> 进行升序排序
#include <iostream>
#include <vector>
#include <algorithm> // 包含 std::sortint main() {std::vector<int> numbers = {5, 2, 8, 1, 9, 4};// 对向量进行升序排序std::sort(numbers.begin(), numbers.end());std::cout << "升序排序后的数字: ";for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl; // 输出: 1 2 4 5 8 9return 0;
}
2. 对 std::vector<int> 进行降序排序
方法一：使用 std::greater<T> 函数对象
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // 包含 std::greaterint main() {std::vector<int> numbers = {5, 2, 8, 1, 9, 4};// 对向量进行降序排序std::sort(numbers.begin(), numbers.end(), std::greater<int>());std::cout << "降序排序后的数字: ";for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl; // 输出: 9 8 5 4 2 1return 0;
}
方法二：使用 Lambda 表达式
#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> numbers = {5, 2, 8, 1, 9, 4};// 使用 Lambda 表达式进行降序排序std::sort(numbers.begin(), numbers.end(), [](int a, int b) {return a > b; // 如果 a 大于 b，则 a 排在 b 之前});std::cout << "降序排序后的数字 (Lambda): ";for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl; // 输出: 9 8 5 4 2 1return 0;
}
3. 对 std::string 中的字符进行排序
#include <iostream>
#include <string>
#include <algorithm>int main() {std::string s = "programming";// 对字符串中的字符进行升序排序std::sort(s.begin(), s.end());std::cout << "排序后的字符串: " << s << std::endl; // 输出: aggimnoprrreturn 0;
}
4. 对自定义结构体或类进行排序 (按特定成员)
假设有一个 Student 结构体，我们想按分数对其进行排序。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>struct Student {std::string name;int score;
};// 自定义比较函数（可作为 Lambda 表达式或独立函数）
bool compareStudents(const Student& s1, const Student& s2) {return s1.score < s2.score; // 按分数升序排序
}int main() {std::vector<Student> students = {{"Alice", 85},{"Bob", 92},{"Charlie", 78},{"David", 92} // Bob 和 David 分数相同};// 使用自定义比较函数对学生进行排序std::sort(students.begin(), students.end(), compareStudents);std::cout << "按分数排序后的学生: " << std::endl;for (const Student& s : students) {std::cout << s.name << ": " << s.score << std::endl;}/* 输出:Charlie: 78Alice: 85Bob: 92David: 92*/// 假设分数相同，按名字字母顺序排序std::sort(students.begin(), students.end(), [](const Student& s1, const Student& s2) {if (s1.score != s2.score) {return s1.score < s2.score; // 分数不同时按分数排序}return s1.name < s2.name; // 分数相同时按名字排序});std::cout << "\n按分数然后按名字排序后的学生: " << std::endl;for (const Student& s : students) {std::cout << s.name << ": " << s.score << std::endl;}/* 输出:Charlie: 78Alice: 85Bob: 92David: 92 (注意：这里Bob和David的相对顺序可能不变，因为它们在原始数据中是Bob在前。如果想确保 David 在 Bob 之后，比较器应返回 true 只有当 s1 严格小于 s2。当前输出是正确的，因为 Bob 92, David 92, Bob 的 'B' < David 的 'D'。实际输出取决于 `std::sort` 的稳定性，但 `std::sort` 通常是不稳定的，对于相等元素，相对顺序可能改变。如果需要稳定性，使用 `std::stable_sort`。但在这个例子中，因为Bob和David名字不同，所以会进一步排序。*/return 0;
}
总结
std::sort 是 C++ 中进行排序的首选工具，因为它高效、灵活，并且易于使用。通过提供自定义比较规则，你可以根据几乎任何条件对各种数据类型进行排序。
--链表01)
