引子：被破坏的原有顺序

在C++项目开发中，我们经常使用STL的vector来存储数据，并使用库中的sort函数进行排序。但如果不了解排序算法“稳定性”的概念，就很容易掉入陷阱。

假设我们有一个vector，它已经按照学生的姓名进行了升序排序。现在，我们希望按照分数进行降序排序，但期望是：对于分数相同的学生，他们之间的原有顺序（即按姓名排好的顺序）能够得以保留。

让我们看一段示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct Student {
    string name;
    int score;

    // 为了方便输出，重载 << 运算符
    friend ostream& operator<<(ostream& os, const Student& s) {
        os << "(" << s.name << ": " << s.score << ")";
        return os;
    }
};

int main() {
    vector<Student> students = {
        {"Alice", 85},
        {"Bob", 91},
        {"Charlie", 91}, // Bob和Charlie分数相同，但Bob的姓名在Charlie之前
        {"David", 78}
    };

    cout << "原始顺序（按姓名排好）: ";
    for (const auto& s : students) cout << s << " ";
    cout << endl << endl;

    // 现在我们想按分数降序排列
    sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        return a.score > b.score; // 降序
    });

    cout << "按分数降序排序后: ";
    for (const auto& s : students) cout << s << " ";
    cout << endl;

    return 0;
}

运行结果可能如下：

原始顺序（按姓名排好）: (Alice: 85) (Bob: 91) (Charlie: 91) (David: 78) 
按分数降序排序后: (Bob: 91) (Charlie: 91) (Alice: 85) (David: 78)

这个结果看起来没问题，Bob和Charlie都是91分，并且Bob仍然在Charlie前面，符合我们的预期。但这是有保障的吗？

答案是否定的。 std::sort默认不保证稳定性。这意味着，在所有情况下，它都不承诺会保持相等元素的原始相对顺序。虽然在这个简单的例子中我们看到了“正确”的结果，但一旦数据量变大、比较函数变复杂或者使用的C++标准库实现不同，结果可能会变为：

按分数降序排序后: (Charlie: 91) (Bob: 91) (Alice: 85) (David: 78)

注意，Bob和Charlie的顺序发生了交换！原有按姓名排好的顺序被破坏了。这就是因为没有使用稳定排序（stable_sort） 导致的。

第一部分：vector的排序函数与稳定排序的概念

vector支持的排序函数

对于std::vector，我们主要使用头文件中的两个排序函数：

1. std::sort

• 功能：对范围 [first, last) 内的元素进行排序。
• 稳定性：不稳定排序（Unstable Sort）。
• 原理：它通常被实现为一种内省排序（Introsort）。内省排序是快速排序、堆排序和插入排序的混合算法。
• 开始时采用快速排序：递归划分数据集。
• 当递归深度过深时（超过 log(n) 级别）：转为堆排序，避免快速排序在最坏情况下O(n^2)的时间复杂度。
• 当元素数量很少时（例如 <= 16）：转为插入排序，因为对于小数据集，插入排序的常数因子很小，效率更高。
• 特点：平均和最坏情况下的时间复杂度均为O(N·log(N))，是绝大多数场景下的首选，效率极高。

2. std::stable_sort

• 功能：对范围 [first, last) 内的元素进行排序，并保证保留相等元素的顺序。
• 稳定性：稳定排序（Stable Sort）。
• 原理：它通常采用归并排序（Mergesort） 或它们的变种。
• 如果内存充足，通常使用外部归并排序。
• 如果内存不足，可能会使用一种原地归并排序的变种，或者分配临时内存，但其核心思想始终是“分治”与“合并”，而合并过程在遇到相等元素时会优先取前一子序列的元素，从而保证了稳定性。
• 特点：时间复杂度也是O(N·log(N))或O(N·log(N)^2)，但常数因子通常比sort大，因为它需要更多的比较或移动操作来维持稳定性。

如何选择？

• 如果不关心相等元素的原始顺序，或者确定比较条件能唯一区分所有元素（即没有相等的元素），使用std::sort，因为它更快。
• 如果需要保持相等元素的原始相对顺序（就像我们上面的例子），则必须使用std::stable_sort。

修正上面的代码：

只需将sort替换为stable_sort，就能在任何情况下保证Bob一定在Charlie之前。

stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    return a.score > b.score;
});

第二部分：常见排序算法的稳定性与原理

下表列出了常见排序算法的分类、原理和稳定性。

第三部分：C++ STL容器排序功能对比

C++ STL中的容器并非都支持排序，只有序列容器（如vector, deque, list） 和关联容器的相关操作涉及排序。

总结与建议：

1. 默认选择std::sort：对于vector和deque，在不需要稳定性时，它是性能最好的选择。
2. 需要稳定性时选择std::stable_sort：当需要保持相等元素的原始顺序时使用。
3. 对链表排序用成员函数list::sort()：不要对std::list和std::forward_list使用std::sort，必须使用其自带的成员函数sort()。
4. 关联容器自身有序：它们通过内部的数据结构（红黑树）自动维护顺序，无需调用排序算法。