C++ std::sort与std::stable_sort的排序稳定性差异

在C++标准库中，std::sort 和 std::stable_sort 是最常用的两个排序算法。虽然它们都能将序列排好序，但在处理“相等”元素的方式上存在本质区别。本文将通过实际代码演示和底层原理分析，帮你彻底搞懂何时该用哪一个。

1. 理解排序稳定性的核心概念

定义区别：排序算法的“稳定性”是指，如果两个元素通过比较操作符判定为相等，排序后它们的相对位置是否保持不变。

• 稳定排序：如果元素 A 和元素 B 相等，且排序前 A 在 B 前面，排序后 A 依然在 B 前面。
• 不稳定排序：如果元素 A 和 元素 B 相等，排序后它们的位置可能会互换，相对顺序无法保证。

std::stable_sort 保证稳定性，而 std::sort 不保证。

2. 动手实验：直观观察差异

为了亲眼看到这种差异，我们需要构造一个包含相等数据但具备不同属性的场景，分别调用这两个算法并观察输出结果。

步骤 1：创建测试数据结构

定义一个 Employee 结构体，包含 id、name 和 score。我们将按照 score 进行排序，重点关注 score 相同时，id 的顺序变化。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // 包含排序算法

struct Employee {
    int id;
    std::string name;
    int score;

    // 仅用于方便打印输出
    void print() const {
        std::cout << "ID: " << id << ", Name: " << name << ", Score: " << score << std::endl;
    }
};

步骤 2：编写比较函数

实现一个比较函数，告诉排序算法只根据 score 来决定大小，忽略 id。

bool compareByScore(const Employee& a, const Employee& b) {
    return a.score < b.score;
}

步骤 3：初始化并运行 std::sort

创建一个 vector，放入几组数据。注意：这里特意将 ID 较小的员工排在 ID 较大的员工前面，且分数相同。

void test_std_sort() {
    std::vector<Employee> staff = {
        {101, "Alice", 90},
        {102, "Bob", 85},
        {103, "Charlie", 90}, // 与 Alice 分数相同，但 ID 更大
        {104, "David", 85}    // 与 Bob 分数相同，但 ID 更大
    };

    std::cout << "--- 原始数据 ---" << std::endl;
    for (const auto& e : staff) e.print();

    // 调用 std::sort
    std::sort(staff.begin(), staff.end(), compareByScore);

    std::cout << "--- std::sort 结果 ---" << std::endl;
    for (const auto& e : staff) e.print();
}

步骤 4：初始化并运行 std::stable_sort

复制相同的数据，但这次 使用 std::stable_sort。

void test_std_stable_sort() {
    std::vector<Employee> staff = {
        {101, "Alice", 90},
        {102, "Bob", 85},
        {103, "Charlie", 90},
        {104, "David", 85}
    };

    std::cout << "--- 原始数据 ---" << std::endl;
    for (const auto& e : staff) e.print();

    // 调用 std::stable_sort
    std::stable_sort(staff.begin(), staff.end(), compareByScore);

    std::cout << "--- std::stable_sort 结果 ---" << std::endl;
    for (const auto& e : staff) e.print();
}

步骤 5：对比输出结果

运行上述两段代码，你很可能会看到类似下面的输出（注意 std::sort 的不确定性行为）：

std::sort 的可能输出（分数相同时，ID 顺序可能乱掉）：

--- std::sort 结果 ---
ID: 103, Name: Charlie, Score: 85  <-- 原本在后面的 ID 跑到了前面
ID: 102, Name: Bob, Score: 85
ID: 101, Name: Alice, Score: 90
ID: 103, Name: Charlie, Score: 90

std::stable_sort 的输出（分数相同时，ID 顺序保持原样）：

--- std::stable_sort 结果 ---
ID: 102, Name: Bob, Score: 85      <-- ID 102 依然在 ID 104 前面
ID: 104, Name: David, Score: 85
ID: 101, Name: Alice, Score: 90    <-- ID 101 依然在 ID 103 前面
ID: 103, Name: Charlie, Score: 90

3. 深入底层：为什么会有差异？

这种差异源于它们底层的实现算法。

• std::sort (内省排序 Introsort)：

  • 它是快速排序、堆排序和插入排序的混合体。
  • 快速排序的核心是“分区”和“交换”。当两个元素相等时，交换操作可能会改变它们的相对位置。
  • 因为追求极致的速度，C++ 标准不强制要求它保持稳定性。

• std::stable_sort (归并排序 Merge Sort)：

  • 它主要基于归并排序实现。
  • 归并排序在合并两个有序子序列时，如果当前元素相等，算法会优先选择前一个子序列的元素，从而自然地保持了原始顺序。
  • 为了维持这种稳定性，它通常需要额外的内存空间。

4. 权衡性能与内存：如何选择？

在实际开发中，不能只看功能，还需要考虑性能和资源消耗。

核心结论：

1. 默认使用 std::sort：如果你的对象是简单类型（如 int, double），或者对象的排序完全基于数值大小，不关心相等元素的前后位置，std::sort 通常更快且省内存。
2. 必须使用 std::stable_sort：
   • 你正在对结构体排序，且第一关键字排序后，还隐含希望保留第二关键字的原始顺序（如上面的 score 相同按 id 原序排）。
   • 你正在进行多级排序（例如先按部门排，再按薪资排，且不能打乱部门内部的相对顺序）。

5. 决策流程图

当你在代码中犹豫不决时，遵循以下逻辑图来快速做出决定：