std::sort是推荐使用的“快速排序”实现，实际为introsort（快排+堆排+插入排序），最坏O(n log n)，需#include <algorithm>，支持自定义比较器，小数组自动切插入排序。
std::sort 就是你要的“快速排序”
绝大多数情况下，std::sort 就是你该用的“快速排序”——它不一定是教科书上的快排，但比手写快排更稳、更快、更安全。标准库实现通常混合了 introsort（快排 + 堆排 + 插入排序），在最坏情况下也能保证 O(n log n)，而纯快排可能退化到 O(n²)（比如已排序数组+固定轴点）。
常见错误现象：std::sort 编译失败，常因忘了 #include <algorithm>；或传入裸数组时写成 std::sort(arr, arr + n) 却漏掉 n 导致越界。
- 使用场景：对
std::vector、std::array或 C 风格数组排序，且不需要稳定排序 - 参数差异：第三个参数可传自定义比较器，比如
std::sort(v.begin(), v.end(), std::greater<int>())降序 - 性能影响：对小容器（
size < 32），std::sort内部会自动切到插入排序，无需手动优化
手写快排只在极少数情况值得做
除非你在写算法题调试、教学演示，或必须控制分区逻辑（比如按多个字段分层 pivot），否则不建议手写。自己写的快排容易出错，而且现代编译器对 std::sort 的内联和优化远超手动代码。
常见错误现象：递归爆栈（没设递归深度限制）、分区逻辑错（比如 i 和 <code>i 混用）、pivot 选错位置导致死循环。
立即学习“C++免费学习笔记（深入）”；
- 必须加递归剪枝：当子区间长度 ≤10 时改用
std::insertion_sort或直接返回 - pivot 推荐用三数取中（
arr[left],arr[mid],arr[right]中位数），避免退化 - 别用
rand()做随机 pivot：线程不安全，且RAND_MAX可能太小；改用std::random_device+std::mt19937
std::stable_sort 不等于“慢”，但别乱换
如果你需要相等元素保持原始顺序（比如先按姓名排、再按年龄排），才用 std::stable_sort。它底层通常是归并排序，时间复杂度稳定 O(n log n)，但空间开销略大（需额外 O(n) 内存）。
常见错误现象：误以为 std::stable_sort 更“可靠”，结果在内存受限嵌入式环境里触发 OOM；或在不需要稳定性时强行替换 std::sort，白丢 10%~20% 性能。
- 使用场景：多关键字排序的第二轮、处理有隐含顺序的数据（如日志时间戳相同但需保先后）
- 兼容性影响：所有标准库都支持，但某些旧交叉编译器（如 ARM GCC 4.8）对
std::stable_sort的模板实例化可能更耗时 - 替代方案：若只需局部稳定（比如最后 100 个元素），可考虑
std::partial_sort+ 手动补位
自定义类型排序必须重载 operator< 或传比较器
std::sort 对自定义类默认调用 operator<。如果没定义，编译直接报错：invalid operands to binary expression。别指望它自动按成员字典序比较——C++ 不搞 Python 那套。
常见错误现象：定义了 operator< 但用了 const 不匹配（比如声明为 bool operator<(const T& other) const 却漏掉末尾 const）；或比较器捕获了局部变量但没声明 [&] 导致悬垂引用。
- 推荐写法：用 lambda 传比较器，显式、短小、无歧义，比如
std::sort(v.begin(), v.end(), [](const auto& a, const auto& b) { return a.x < b.x; }); - 性能注意：lambda 若捕获大对象（如
[big_vec]）会引发拷贝；应优先用[&]或只捕获所需字段 - 陷阱：若类有指针成员且
operator<比较的是地址而非内容，排序结果不可预测
真正麻烦的从来不是“怎么写快排”，而是 pivot 选得是否鲁棒、迭代器范围是否闭合、比较逻辑是否满足严格弱序——这些细节一错，程序就静默错排，比崩溃还难查。
