当前位置：首页 > news >正文

C++ 排序指南

news 2025/8/15 15:20:16

在 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;
}