跳到主要内容C++ 精通 std::sort 与自定义比较器 | 极客日志C++算法
C++ 精通 std::sort 与自定义比较器
C++ STL 中 std::sort 的使用，包括基础升序排序、迭代器范围、自定义比较器实现降序及结构体排序，对比了 std::sort 与 stable_sort 的差异，并通过调试步骤展示了比较函数的调用机制，最后提供实践挑战。
BigDataPan9 浏览 在 C++ 编程中，最常见的任务之一就是对数据进行排序。你可能有一个 vector（'魔法弹性数组'）装满了杂乱无章的数字、字符串、甚至是你自定义的'盒子'（struct 或 class）。
一个简单的比喻：'神奇的排序黑盒'
- '笨办法'：你自己编写一个排序算法，比如'冒泡排序'或'插入排序'。这就像你拿到一副打乱的扑克牌，必须自己一张一张地抽牌、比较、换位。这个过程既慢（
O(N^2) 效率）、又繁琐、还极易出错。
- C++ STL 的'聪明办法'：C++ 在
<algorithm>（算法）'工具包'里，为你提供了一个极其强大、高度优化的'神奇黑盒'—— std::sort。
- 你的工作：把'整堆牌'（
vector）'倒进'这个'黑盒' (std::sort)。
- 一瞬间（通常是
O(N log N) 效率，比'笨办法'快成千上万倍），'黑盒'会把完美排好序的牌（vector）'吐'出来。
- 你不需要知道'黑盒'内部是如何工作的（它通常是一种称为 'IntroSort' 的混合排序算法），你只需要知道如何使用它。
默认情况下，std::sort 会按照'从小到大'（升序）的规则排序。但它最强大的地方在于，你可以给它'递一张纸条'（一个自定义比较函数），告诉它按任何你想要的规则排序（比如'从大到小'、'按字符串长度'、'按学生年龄…'）。
在本教程中，你将学会：
std::sort 的基本用法：如何对 vector 进行'一键'升序排序。- 迭代器 (Iterators)：
begin() 和 end() 这两个'范围标记'的含义。
- 自定义比较器 (Comparator)：如何编写一个'规则函数'（'递纸条'）来实现降序排序。
- '终极应用'：如何对包含'自定义盒子' (
struct) 的 vector 进行排序（例如：按年龄）。
std::stable_sort：sort 的'稳定'兄弟，它们有何不同。- 'X 光透视'：用调试器'亲眼目睹'
sort 是如何'调用'你的'自定义规则'的。
前置知识说明 (100% 自洽)：
vector (向量)：C++ 标准库提供的一种'动态数组'（'魔法弹性盒子列表'）。你需要 #include <vector>。struct (结构体)：一种'蓝图'，用于创建'自定义盒子'，把相关数据（如 name 和 age）打包在一起。**#include <algorithm>**： 和 所在的'工具包'。
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
std::sort
std::stable_sort
**#include <iostream>**：用于 cout 打印。迭代器 (Iterator)：可以理解为指向容器（如 vector）中某个元素的'智能书签'。
myVec.begin()：返回指向第一个元素的'书签'。myVec.end()：返回指向最后一个元素之后（一个'不存在'的位置）的'书签'。
编译 (Compile)：C++ 代码（'食谱'）必须被'编译'（'烘焙'），才能变成电脑可执行的程序（'蛋糕'）。
第一部分：'魔法黑盒'—— std::sort 的基本用法
std::sort 的'按钮'需要你提供两个'书签'（迭代器），告诉它要排序的'范围'：
myVector.begin()：指向第一个元素。myVector.end()：指向最后一个元素之后的'无效'位置。
std::sort 会排序 [begin, end) 范围内的所有元素（包括 begin，不包括end）。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printVector(const string& title, const vector<int>& vec) {
cout << title << "[ ";
for (int x : vec) {
cout << x << " ";
}
cout << "]" << endl;
}
int main() {
vector<int> numbers = {12, 5, 13, 7, 2};
printVector("原始：", numbers);
std::sort(numbers.begin(), numbers.end());
printVector("排序后 (升序): ", numbers);
return 0;
}
PS C:\MyCode> g++ basic_sort.cpp -o basic_sort.exe -std=c++11
PS C:\MyCode> .\basic_sort.exe
原始： [ 12 5 13 7 2 ]
排序后 (升序): [ 2 5 7 12 13 ]
顿悟时刻： 默认情况下，std::sort 使用 operator<（小于号）来比较元素，实现升序排序。
第二部分：'递上纸条'——自定义比较器 (Comparator)
如果你想降序（从大到小）排序呢？你需要给 sort'递一张纸条'（第三个参数），告诉它新的'比较规则'。
这个'规则'是一个函数（或 C++11 的 Lambda 表达式），它必须：
- 接收两个同类型的参数（
const& 是最高效的方式）。
- 返回一个
bool 值。
- '黄金法则'： 如果你希望
a 排在 b 的前面，就返回 **true**；否则返回 false。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
bool compareDescending(const int& a, const int& b) {
return a > b;
}
int main() {
vector<int> numbers = {12, 5, 13, 7, 2};
printVector("原始：", numbers);
std::sort(numbers.begin(), numbers.end(), compareDescending);
printVector("排序后 (降序): ", numbers);
return 0;
}
PS C:\MyCode> g++ custom_sort.cpp -o custom_sort.exe -std=c++11
PS C:\MyCode> .\custom_sort.exe
原始： [ 12 5 13 7 2 ]
排序后 (降序): [ 13 12 7 5 2 ]
第三部分：'终极应用'——排序'自定义盒子' (struct)
std::sort 的真正威力在于排序自定义对象。
struct Person {
string name;
int age;
};
vector<Person> people = {{"Bob", 30}, {"Alice", 25}};
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct Person {
string name;
int age;
};
bool compareByAge(const Person& a, const Person& b) {
return a.age < b.age;
}
int main() {
vector<Person> people = {{"Charlie", 30}, {"Alice", 25}, {"Bob", 35}};
cout << "--- 原始列表 ---" << endl;
for (const auto& p : people) {
cout << " " << p.name << " (Age: " << p.age << ")" << endl;
}
std::sort(people.begin(), people.end(), compareByAge);
cout << "\n--- 按年龄排序后 ---" << endl;
for (const auto& p : people) {
cout << " " << p.name << " (Age: " << p.age << ")" << endl;
}
return 0;
}
PS C:\MyCode> g++ struct_sort.cpp -o struct_sort.exe -std=c++11
PS C:\MyCode> .\struct_sort.exe
--- 原始列表 ---
Charlie (Age: 30)
Alice (Age: 25)
Bob (Age: 35)
--- 按年龄排序后 ---
Alice (Age: 25)
Charlie (Age: 30)
Bob (Age: 35)
第四部分：std::sort vs std::stable_sort
std::sort 还有一个'兄弟'叫 std::stable_sort（也在 <algorithm> 中）。
- 问题： 如果你有两个'相等'的元素（比如，两个
Person 年龄都是 30），排序后它们原来的'前后'顺序可能会被打乱。
std::sort ('快，但不保证')：不保证保留'相等'元素的原始相对顺序。它优先追求最快的速度。std::stable_sort ('稳，稍慢')：保证保留'相等'元素的原始相对顺序。
- 例子：
{{"Charlie", 30}, {"Adam", 30}}
stable_sort 保证排序后 Adam 仍然在 Charlie 的前面（如果 Adam 原本就在前面，并且你只按年龄排）。
- 如果你不在乎相等元素的相对顺序（大部分情况），使用
std::sort（它更快）。
- 如果你必须保持相等元素的原始顺序，使用
std::stable_sort（它会稍慢一点）。
第五部分：'X 光透视'——亲眼目睹'自定义规则'被调用
我们无法（也不需要）用调试器'步入' (F11) std::sort 内部，因为它是一个高度优化的、编译好的'黑盒'。
但是，我们可以'步入'它调用我们的'自定义规则'！
'X 光'实战（基于 struct_sort.cpp）
- 设置断点：
- 动作： 在 VS Code 中，把你的鼠标移动到 '规则'函数
compareByAge 内部的第 19 行（return a.age < b.age;）的行号左边。
- 点击那个小 red dot，设置一个断点。
- 启动'子指时间'（F5）：
- 动作： 按下
F5 键。
- 你会看到： 程序执行
main，创建 vector，打印'原始列表'。
- 当程序执行到
std::sort(...) 这一行时，它会 **'跳进'你的 compareByAge 函数，'冻结'**在第 19 行！
- 开启'X 光'（观察'裁判'工作）：
- 动作： 仔细看那个'变量'(VARIABLES) 窗口。
- 你会看到：
a: {name: "Alice", age: 25}b: {name: "Charlie", age: 30}
- 顿悟时刻：
std::sort（'黑盒'）为了决定 'Alice' 和 'Charlie' 谁该排前面，它把这两个对象'递'给了你的'裁判' (compareByAge)！
- 动作： 按下
F10 键（'Step Over'）。
- 你会看到：
a.age < b.age (即 25 < 30) 计算为 true。函数返回 true。sort 知道了 'Alice' 应该在 'Charlie' 前面。
- 继续执行 (F5)。
- 第二次'冻结' (在
compareByAge 内部)：
- 动作： 按下
F5 键，程序会再次停在 compareByAge 断点处。
- 观察'变量'窗口：
a: {name: "Bob", age: 35}b: {name: "Charlie", age: 30}
- 顿悟时刻：
std::sort 现在正在比较 'Bob' 和 'Charlie'！
- 动作： 按下
F10 键。
- 你会看到：
a.age < b.age (即 35 < 30) 计算为 false。函数返回 false。sort 知道了 'Bob' 应该在 'Charlie' 后面。
- （继续按 F5，
sort 会调用你的'裁判'很多次…）
- 最终顿悟： 你亲眼见证了
std::sort 是如何利用你的'自定义规则'来驱动其内部（你看不见）的排序算法的。
动手试试！(终极挑战：你的'高级'排序)
- 复制本教程
struct_sort.cpp 的 Person 结构体和 main 函数框架。
- 修改
vector<Person> people，添加几个同龄人，比如：
{{"Charlie", 30}, {"Alice", 25}, {"David", 30}, {"Bob", 35}}
- **编写一个新的'自定义规则'**函数，名叫
compareByNameDescending。
- 规则： 必须按姓名进行降序排序（Z -> A）。
- 在
main 函数中，调用std::sort，但传入你这个新的 compareByNameDescending 规则。
- 打印最终结果，验证姓名是否按 Z 到 A 排序。
sort_challenge.cpp (你的 TODO):
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct Person {
string name;
int age;
};
int main() {
vector<Person> people = {{"Charlie", 30}, {"Alice", 25}, {"David", 30}, {"Bob", 35}};
cout << "--- 原始列表 ---" << endl;
cout << "\n--- 按姓名降序排序后 ---" << endl;
return 0;
}
这个挑战让你亲手实践了 std::sort 最强大的功能：根据你提供的任意逻辑，对任意对象列表进行排序。完成它，你就掌握了 C++ STL 中最强大的工具之一！
