std::sort并非纯快排，而是introsort（快排+堆排+插入排序的混合体），兼顾平均O(n log n)性能与最坏O(n log n)保障；报错“invalid comparator”通常因比较函数不满足严格弱序。
std::sort 就是 C++ 里的快排，但不完全等价
标准库的 std::sort 在绝大多数实现（如 libstdc++、libc++）中用的是 introsort —— 快排 + 堆排 + 插入排序的混合体。它规避了快排最坏 O(n²) 的风险，又保留了平均 O(n log n) 的性能。别自己手写快排除非真有特殊需求（比如教学、嵌入式无 STL、或需要确定性 pivot 策略）。
常见错误现象：std::sort 报错 “invalid comparator”，其实是比较函数没满足严格弱序：比如用了 而不是 <code>，或对相等元素返回 true。
- 使用场景：容器随机访问迭代器可用时（
std::vector、std::array、原生数组），std::sort是首选 - 参数差异：第三个参数必须是可调用对象，且签名应为
bool( const T&, const T& )；lambda 更安全，避免捕获导致的生命周期问题 - 性能影响：自定义 comparator 若有副作用或开销大（如字符串比较未用
string_view），会显著拖慢排序
手写快排时 pivot 选错，递归栈直接爆掉
用首/尾元素当 pivot，在已排序或逆序数据上会退化成链表式递归，深度 O(n)，轻则栈溢出，重则超时。g++ 默认栈空间有限，std::stack 模拟也容易忘清空。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 用三数取中（
median-of-three）：取首、中、尾三者中位数作为 pivot，能大幅降低退化概率 - 小数组切片（
size ）改用插入排序，减少递归层数和函数调用开销 - 尾递归优化：对较小的子区间先递归，较大者用循环处理，避免深栈 —— 即只递归左半边，右半边用 while 循环迭代
- 别用
rand()做随机 pivot：它不是线程安全的，且周期短；改用std::random_device+std::mt19937
std::sort 对自定义类型排序，operator
如果类里只定义了 operator，但实际要按多个字段排序（比如先按 <code>score 降序，再按 name 升序），硬塞进 operator 会导致语义混乱，且无法复用。
更灵活的做法是分离比较逻辑：
- 用 lambda 直接传给
std::sort：std::sort(v.begin(), v.end(), [](const auto& a, const auto& b) { return a.score != b.score ? a.score > b.score : a.name - 定义命名比较器结构体，显式控制
operator()，便于测试和复用 - 注意：若字段含指针或引用，比较时未判空，运行时可能崩溃 —— 比如
std::string*成员未检查是否为nullptr - 兼容性影响：C++20 引入了
std::ranges::sort，支持投影（projection），可更干净地提取排序键，但老项目慎用
std::stable_sort 不等于“更慢的 sort”，该用就得用
当数据本身有隐含顺序（比如日志按时间追加，同一时间戳有多条），且你希望相同 key 的元素保持原有相对位置，std::sort 不能保证这点 —— 它是不稳定的。这时候必须换 std::stable_sort。
但它代价不小：
- libstdc++ 实现是归并排序，额外 O(n) 空间；若内存紧张（如嵌入式），得权衡
- 对小数组（
n ），<code>std::stable_sort可能比std::sort慢 2–3 倍，别盲目替换 - 没有“稳定版”的 partial_sort 或 nth_element，想取 top-K 且保序？只能先 stable_sort 再截取，或自己维护索引数组
真正容易被忽略的是：稳定性不是免费的，也不是默认的。只要业务逻辑依赖“相同优先级下先来后到”，就必须显式选 std::stable_sort，而不是靠测试数据碰巧没暴露问题。
