C++ std::sort为什么不稳定？stable_sort函数怎么用？

在C++的标准库中，std::sort和std::stable_sort都是常用的排序函数，但两者的核心差异在于排序后相等元素的相对顺序是否会保留，这也是很多开发者在实际开发中容易混淆的点。

std::sort的稳定性分析

std::sort默认是不稳定的排序函数，也就是说当待排序的元素存在相等值时，排序后这些相等元素的原始相对顺序可能会被改变。这是由std::sort的底层实现决定的，标准并没有规定std::sort的具体实现算法，但大多数标准库实现采用的是内省排序（Introsort），它是快速排序、堆排序和插入排序的结合体。

快速排序在划分过程中，对于相等的元素没有保证其相对顺序，而内省排序在快速排序退化时会切换到堆排序，堆排序同样不保证相等元素的原始顺序，因此最终std::sort无法保证稳定性。

我们可以通过一个简单的示例来验证std::sort的不稳定性：

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

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"张三", 80},
        {"李四", 90},
        {"王五", 80},
        {"赵六", 85}
    };
    // 按照分数排序，分数相同的学生原始顺序是张三在前王五在后
    std::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 << std::endl;
    }
    return 0;
}

运行上述代码后，分数为80的两个学生，张三和王五的相对顺序可能发生变化，这就是std::sort不稳定的直观体现。

stable_sort函数用法详解

std::stable_sort是C++标准库提供的稳定排序函数，它会保证排序后相等元素的原始相对顺序和排序前一致。其函数原型有两种重载形式：

// 第一种：使用默认的<比较
template< class RandomIt >
void stable_sort( RandomIt first, RandomIt last );

// 第二种：使用自定义比较函数comp
template< class RandomIt, class Compare >
void stable_sort( RandomIt first, RandomIt last, Compare comp );

参数说明：

• first：指向待排序序列起始位置的迭代器
• last：指向待排序序列末尾位置（尾后）的迭代器
• comp：自定义的比较函数，接收两个参数，当第一个参数应该排在第二个参数前面时返回true，默认使用<运算符比较

我们同样用上面的学生排序场景来演示stable_sort的用法：

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

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"张三", 80},
        {"李四", 90},
        {"王五", 80},
        {"赵六", 85}
    };
    // 使用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 << std::endl;
    }
    return 0;
}

运行上述代码后，分数为80的两个学生，张三始终会排在王五前面，和原始顺序一致，体现了stable_sort的稳定性。

两者的性能与选择建议

std::sort和std::stable_sort的性能差异主要来自于实现算法：

选择建议：

• 如果不需要保证相等元素的原始顺序，优先选择std::sort，它的空间开销更小，实际运行效率通常更高
• 如果需要保留相等元素的原始相对顺序，比如多关键字排序中先按第一关键字排，再按第二关键字稳定排序，或者业务要求相等元素顺序不变，就选择std::stable_sort

需要注意的是，stable_sort的额外空间开销在待排序元素数量很大时可能会比较明显，如果内存资源紧张且不需要稳定性，应避免使用stable_sort。

std::sortstable_sortC++排序排序稳定性修改时间：2026-07-23 18:06:40