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 作为排序键,并故意给每组放入多个元素。排序后观察姓名顺序,就能验证稳定性。

cpp
#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;
}

预期输出

text
1:B 1:D 2:A 2:C 2:E

B 原本就在 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。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

stable_sort 为什么保留原顺序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通