C++稳定排序详解（深入理解stable_sort与排序稳定性）

C++中的 stable_sort 函数

C++ STL 提供了 std::stable_sort 函数，位于 <algorithm> 头文件中。它的特点是：保证排序的稳定性，时间复杂度通常为 O(n log n)，最坏情况下为 O(n (log n)²)（取决于实现）。

基本语法

#include <algorithm>// 默认升序排序std::stable_sort(first, last);// 自定义比较函数std::stable_sort(first, last, comp);

• first：容器起始迭代器
• last：容器结束迭代器（不包含）
• comp：可选的比较函数或 lambda 表达式

实战示例：按成绩排序学生名单

下面是一个完整的 C++ 程序，演示如何使用 stable_sort 对学生按成绩排序，并保持同分学生的原始顺序：

#include <iostream>#include <vector>#include <algorithm>#include <string>struct Student {    std::string name;    int score;};int main() {    std::vector<Student> students = {        {"张三", 85},        {"李四", 90},        {"王五", 85},        {"赵六", 90}    };    // 使用 stable_sort 按成绩升序排序    std::stable_sort(students.begin(), students.end(),        [](const Student& a, const Student& b) {            return a.score < b.score;        }    );    // 输出结果    for (const auto& s : students) {        std::cout << s.name << ": " << s.score << "\n";    }    return 0;}

输出结果为：

张三: 85王五: 85李四: 90赵六: 90

可以看到，“张三”始终排在“王五”前面，因为他们在原始列表中就是这个顺序——这就是 C++稳定排序 的体现。

stable_sort 与 sort 的区别

C++ STL 还提供了 std::sort，它通常更快（平均 O(n log n)），但不保证稳定性。而 std::stable_sort 虽然可能稍慢，但能确保相同元素的相对顺序不变。

何时使用 stable_sort？

以下情况推荐使用 std::stable_sort：

• 进行多级排序（例如先按部门排序，再按工资排序）
• 处理日志、事件等需要保留原始顺序的数据
• 对结构体/类对象排序，且比较字段存在重复值
• 算法要求排序过程必须稳定（如某些图论或计算几何算法）

总结

通过本文，我们深入学习了 C++ 中的 稳定排序算法，特别是 std::stable_sort 的使用方法和适用场景。记住：当你需要在排序后保持相等元素的原始相对顺序时，务必选择 stable_sort 而非普通的 sort。

掌握 STL稳定排序 技巧，不仅能写出更健壮的代码，还能在面试和实际项目中展现你的专业素养。希望这篇教程对你理解 C++排序算法 和 stable_sort用法 有所帮助！