悠悠楠杉
网站页面
C++算法排序与自定义比较函数应用
11/16
在现代C++开发中，std::sort 是最常用且高效的排序工具之一。它基于快速排序的优化版本——内省排序（Introsort），结合了快速排序、堆排序和插入排序的优点，能够在平均 $O(n \log n)$ 的时间复杂度下完成数据排序。然而，标准库默认使用 < 运算符进行升序排列，面对复杂的数据结构或特殊排序需求时，我们必须自定义比较函数来控制排序逻辑。
要真正掌握 std::sort 的灵活性，关键在于理解如何为其提供自定义的比较规则。C++ 提供了多种方式实现这一点：普通函数、函数对象（仿函数）、Lambda 表达式以及重载运算符。每种方式都有其适用场景，合理选择能显著提升代码可读性与维护性。
假设我们有一个学生信息结构体：
cpp
struct Student {
std::string name;
int age;
double score;
};
如果我们希望按成绩从高到低排序，就不能依赖默认行为。此时，可以定义一个比较函数：
cpp
bool compareByScore(const Student& a, const Student& b) {
return a.score > b.score; // 降序
}
然后在调用 std::sort 时传入该函数：
cpp
std::vector<Student> students = {{"Alice", 20, 88.5}, {"Bob", 19, 92.0}, {"Charlie", 21, 76.0}};
std::sort(students.begin(), students.end(), compareByScore);
这种方式清晰明了，适用于简单场景。但若需要频繁更改排序策略，函数命名可能变得冗长，维护成本上升。
更进一步，我们可以使用函数对象（Functor）。通过定义一个类并重载 operator()，可以在对象内部封装状态，实现更复杂的比较逻辑：
cpp
struct CompareByAgeThenName {
bool operator()(const Student& a, const Student& b) const {
if (a.age != b.age) {
return a.age < b.age;
}
return a.name < b.name;
}
};
调用方式几乎不变：
cpp
std::sort(students.begin(), students.end(), CompareByAgeThenName{});
函数对象的优势在于支持状态保存，例如可以加入是否忽略大小写的选项，或者动态调整权重。
然而，在大多数现代C++项目中，Lambda 表达式已成为首选方案。它简洁、局部化，无需额外声明函数或类：
cpp
std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
return a.score > b.score;
});
如果需要多级排序，Lambda 同样胜任：
cpp
std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
if (a.score != b.score) return a.score > b.score;
return a.name < b.name;
});
这种写法将逻辑集中于一处，极大提升了代码的内聚性。
值得注意的是，无论采用哪种方式，比较函数必须满足“严格弱序”（Strict Weak Ordering）的要求。这意味着对于任意元素 a、b、c：
- 不允许
comp(a, a)为真（非自反） - 若
comp(a, b)为真，则comp(b, a)必须为假（反对称） - 若
comp(a, b)和comp(b, c)均为真，则comp(a, c)也必须为真（传递性）
违反这些规则可能导致未定义行为，甚至程序崩溃。
此外，当处理类类型时，也可以直接在类中重载 < 运算符，使 std::sort 能直接工作。但这限制了排序方式的多样性，通常建议仅为主排序逻辑重载，其余情况仍使用自定义比较器。
综上所述，std::sort 配合自定义比较函数是C++中处理排序问题的核心手段。开发者应根据实际需求灵活选用函数、函数对象或 Lambda。尤其在大型项目中，清晰的比较逻辑不仅提升性能，更增强了代码的可读性与可维护性。掌握这些技巧，是写出高效、健壮C++程序的重要一步。
