C / C++ / 系统课时
stable_sort 为什么保留原顺序
stable_sort 为什么保留原顺序
当排序记录只比较一个关键字段时,经常会出现多个元素“排序键相等”的情况。stable_sort 的价值就在这里:它不仅完成排序,还保证这些等价元素保持排序前的相对顺序,因此特别适合多级排序、分组展示和需要保留原始先后关系的场景。
学习目标
- 理解稳定排序中“保留原相对顺序”的准确含义
- 区分
sort与stable_sort对等价元素的保证 - 能在需要保持次级顺序时正确选择
stable_sort
什么叫稳定排序
假设有一批记录,排序时只比较 group。如果两条记录的 group 相同,那么从比较器角度看它们是等价的。稳定排序要求:这些等价记录排序之后仍保持原来的先后关系。
例如原数据依次是 A(group=2)、B(group=1)、C(group=2)、D(group=1)。按 group 升序后,两个 group=1 的元素仍应是 B、D,两个 group=2 的元素仍应是 A、C。
std::stable_sort 明确提供这一保证;std::sort 只保证最终满足排序规则,不保证等价元素的相对顺序。某次运行中 sort 看起来也可能保持顺序,但不能把这种现象当成程序语义依赖。
用代码观察相对顺序
下面只把 group 作为排序键,并故意给每组放入多个元素。排序后观察姓名顺序,就能验证稳定性。
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Record {
int group;
std::string name;
};
int main() {
std::vector<Record> records{
{2, "A"},
{1, "B"},
{2, "C"},
{1, "D"},
{2, "E"}
};
// 比较器只关注 group,同组记录彼此属于等价元素。
std::stable_sort(records.begin(), records.end(),
[](const Record& left, const Record& right) {
return left.group < right.group;
});
for (const auto& record : records) {
std::cout << record.group << ':' << record.name << ' ';
}
std::cout << std::endl;
}预期输出
1:B 1:D 2:A 2:C 2:EB 原本就在 D 前面,所以排序后仍是 B、D;A、C、E 原本也是这个顺序,因此同组排序后仍保持 A、C、E。这就是“稳定”的实际含义。
sort 与 stable_sort 的区别
两者都接受随机访问迭代器,也都可以使用自定义比较器。关键差异不是“谁能排序”,而是是否承诺等价元素的原始顺序。
| 算法 | 等价元素相对顺序 | 典型选择 |
|---|---|---|
std::sort |
不保证 | 只关心最终排序键顺序 |
std::stable_sort |
保证保留 | 还需要保留既有次序 |
多级排序为什么需要稳定性
稳定排序的一个典型用途是分阶段建立排序优先级。例如记录已经按姓名排列,随后再用 stable_sort 按部门排序,那么最终结果会先按部门分组,并在每个部门内部继续保持原有姓名顺序。
反过来,如果第二次使用不稳定的 sort,同部门记录之前建立好的顺序就没有保证。因此,当程序需要“按主字段重新分组,但保留已有次级顺序”时,stable_sort 比 sort 更符合需求。
如果等价元素的内部顺序完全无关,就不必为了“看起来更整齐”强制使用稳定排序;真正需要依赖原始顺序、多级排序结果或业务录入顺序时,再选择 stable_sort。