C++ sort与stable_sort使用教程

sort不保证相等元素的相对顺序，使用高效混合算法，平均时间复杂度O(n log n)；stable_sort保持相等元素的原有顺序，适用于多级排序或需保留输入顺序的场景；两者用法相似，均需包含<algorithm>头文件并传入迭代器范围及可选比较函数，选择时根据是否需要稳定性决定。

在C++中，sort 和 stable_sort 是标准模板库（STL）<algorithm> 中用于排序的两个重要函数。它们都能对容器或数组中的元素进行排序，但在排序稳定性上有关键区别。

sort：快速但不保证稳定

sort 使用高效的混合排序算法（通常是快速排序、堆排序和插入排序的结合），时间复杂度平均为 O(n log n)，但不保证相等元素的相对顺序不变。

基本用法：

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

std::vector<int> nums = {5, 2, 8, 2, 9};

// 默认升序排序
std::sort(nums.begin(), nums.end());

// 自定义排序规则（例如降序）
std::sort(nums.begin(), nums.end(), std::greater<int>());

// 或使用 lambda 表达式
std::sort(nums.begin(), nums.end(), [](int a, int b) {
    return a > b;  // 降序
});

stable_sort：保持相等元素的顺序

stable_sort 保证相等元素在排序后仍保持原有的相对顺序。适用于需要保留输入顺序逻辑的场景，比如按多个字段排序时先按次要字段排，再按主要字段稳定排序。

用法与 sort 类似：

std::vector<std::pair<int, char>> data = {{1, 'a'}, {2, 'b'}, {1, 'c'}};

// 按 pair 的 first 排序，stable_sort 会保持 first 相同的元素原有顺序
std::stable_sort(data.begin(), data.end(),
    [](const auto& a, const auto& b) {
        return a.first < b.first;
    });

// 结果中 {1,'a'} 仍排在 {1,'c'} 前面

关键区别与选择建议

• 性能：sort 通常更快，因为不需要维护稳定性。
• 稳定性：当需要保持相等元素的原始顺序时，必须用 stable_sort。
• 适用场景：
  • 普通数值排序：用 sort。
  • 多级排序、自定义结构体且关心顺序：用 stable_sort。

基本上就这些。记住包含 <algorithm>，传入迭代器范围，按需提供比较函数。不复杂但容易忽略稳定性需求。