我要评论在 c++ 标准库中，std::sort() 和 std::stable_sort() 都用于对容器中的元素进行排序，但二者最根本的区别在于稳定性。
1、排序的稳定性是个什么玩意
如果两个元素相等（比较结果为等价），排序后它们的相对顺序与原序列中保持一致。
2、到底谁更稳定
- std::sort() 是不稳定的排序算法，意味着相等元素的相对顺序在排序后可能被改变。
- std::stable_sort() 是稳定排序，保证相等元素的原始输入顺序在排序后保持不变。
3、它们内部的实现方式
- std::sort() 通常采用introsort（内省排序），结合快速排序、堆排序和插入排序，平均性能极佳。
- std::stable_sort() 多基于归并排序（merge sort），因其天然具备稳定性，适合分治策略下的有序合并。
尽管 stable_sort() 提供了稳定性保障，但其代价是更高的内存消耗和潜在的性能下降（尤其在大数据集上）。对于金融系统、考试排名、事件日志等场景，稳定性是硬性需求，应无条件选用 stable_sort()。
4、小结
- std::sort：更快、更省内存，但不保证稳定性。
- std::stable_sort：稍慢、更耗内存，但保证稳定性。
- 一句话：性能优先用 sort，顺序敏感用 stable_sort。
- 备注：对于频繁排序的小型容器，可考虑使用 std::list::sort()
5、示例代码
#include <string>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>//sort
using std::vector;
using std::list;
using std::string;
struct student
{
string name;
double score;
student(const string &n, double s) : name(n), score(s) {}
// 重载 operator< 以按score升序排序(list::sort)
bool operator<(const student& other) const {
return score < other.score;
}
};
bool comparebyscore(const student& a, const student& b) {
return a.score > b.score; // 降序
}
//
bool comparestudent(const student& a, const student& b) {
if (a.score != b.score){
return a.score < b.score;
}
return a.name < b.name; // 成绩相同时按名字升序
}
int main(int argc, char *argv[])
{
std::vector<student> studentarray = {
{"candy", 91.0},
{"body", 91.0},
{"andy", 91.0},
{"lucy", 91.0},
{"lily", 90.5},
{"luck", 92.5},
{"kandy", 95.0},
};
do{
std::cout << "v1: std::sort" << std::endl;
auto v1 = studentarray;
std::sort(v1.begin(), v1.end(), [](const student &a, const student &b){
return a.score > b.score;//降序
});
for (const auto& s : v1) {
std::cout << s.name << ": " << s.score << "\n";
}
}while(false);
do{
// 使用 stable_sort 保证同分学生顺序不变
std::cout << "\nv2: std::stable_sort" << std::endl;
auto v2 = studentarray;
std::stable_sort(v2.begin(), v2.end(), comparebyscore);
for (const auto& s : v2) {
std::cout << s.name << ": " << s.score << "\n";
}
}while(false);
do{
// 对于频繁排序的小型容器，可考虑使用 std::list::sort()（稳定且链表友好）
std::list<student> studentlist;
for (const auto& s : studentarray){
studentlist.push_back(s);
}
// 使用 std::list::sort() 进行排序
std::cout << "\nlist1: sort" << std::endl;
auto list1 = studentlist;
list1.sort(); // 使用 operator<
for (const auto& s : list1) {
std::cout << s.name << ": " << s.score << "\n";
}
//使用自定义比较函数
std::cout << "\nlist2: comparestudent" << std::endl;
auto list2 = studentlist;
list2.sort(comparestudent);
for (const auto& s : list2) {
std::cout << s.name << ": " << s.score << "\n";
}
}while(false);
return 0;
}
总结
到此这篇关于c++ sort()与stable_sort()使用的文章就介绍到这了,更多相关c++ sort()与stable_sort()使用内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论