std::sort比手写快排更值得用，因其采用introsort（快排+堆排+插入排序），性能更稳定且高度优化；手写易出错，如比较函数不满足严格弱序会导致乱序或报错。
std::sort 为什么比手写快排更值得用
绝大多数场景下，std::sort 就是你要的“快速排序”，它不一定是纯快排（实际是 introsort：快排 + 堆排 + 插入排序混合），但平均和最坏性能都更稳，且经过高度优化。自己实现 quick_sort 除非练手或有特殊约束（比如栈空间受限、必须确定性行为），否则纯属增加 bug 风险。
常见错误现象：std::sort 报错 invalid comparator，或排序结果乱序——大概率是自定义比较函数没满足严格弱序（比如用了 而不是 <code>）。
- 使用场景：对
std::vector、std::array、C 风格数组排序时，直接传迭代器即可 - 参数差异：第三个参数必须是可调用对象，且返回
bool；不能捕获局部变量后忘记声明为mutable（若需修改捕获值） - 性能影响：
std::sort对小数组自动切到插入排序，对递归过深自动切到堆排，避免 O(n²) 退化
std::vector<int> v = {3, 1, 4, 1, 5};
std::sort(v.begin(), v.end()); // 升序
std::sort(v.begin(), v.end(), std::greater<int>{}); // 降序手写快排时 pivot 选错就全崩了
选 pivot 不是“随便挑一个”，而是决定是否触发最坏复杂度的关键。用 v[0] 或 v[size-1] 在已排序/逆序数据上会稳定退化成 O(n²)。
容易踩的坑：partition 边界写错导致越界或死循环，尤其在处理重复元素多的数组（如全是 5）时，while (v[i] 这类条件极易卡住。
立即学习“C++免费学习笔记（深入）”；
- 推荐做法：用三数取中（
v[0]、v[mid]、v[end]中位数）做 pivot，再交换到末尾 - 必须检查分区后左右段长度，空段或单元素段直接 return，避免无意义递归
- 递归前先处理较短段，再用循环处理较长段（尾递归优化），能显著压低栈深度
int partition(std::vector<int>& v, int l, int r) {
int mid = l + (r - l) / 2;
if (v[mid] < v[l]) std::swap(v[l], v[mid]);
if (v[r] < v[l]) std::swap(v[l], v[r]);
if (v[r] < v[mid]) std::swap(v[mid], v[r]);
std::swap(v[mid], v[r]); // pivot 放末尾
int pivot = v[r];
int i = l;
for (int j = l; j < r; ++j) {
if (v[j] < pivot) {
std::swap(v[i++], v[j]);
}
}
std::swap(v[i], v[r]);
return i;
}std::sort 不能排序 const 容器或只读数据
这是编译期就报错的问题：std::sort 要求迭代器是可写的（RandomAccessIterator 且 value_type 可赋值）。对 const std::vector<int></int> 或字面量数组（如 const int a[] = {1,2,3}）直接调用会触发模板推导失败或 assignment 操作符不可用。
使用场景：想排序一串常量数据，又不想改原始定义？别硬套 std::sort。
- 方案一：复制到非 const 容器再排，如
std::vector<int> tmp{std::begin(a), std::end(a)}</int> - 方案二：用
std::array替代 C 数组，它支持拷贝构造，且std::sort可作用于其迭代器 - 注意：
std::string_view、std::span<const t></const>同样不可排，必须转成可写视图或复制
迭代器失效和移动语义影响排序结果
对含指针、智能指针或自定义类型的容器排序时，std::sort 内部交换元素靠的是 std::swap，而 swap 行为取决于类型是否支持移动。如果类没正确定义移动构造/赋值，或者禁用了移动（如显式删除了移动操作），就会退回到拷贝，可能引发意外副作用（比如拷贝时触发资源重复申请）。
常见错误现象：排序后容器里某些对象状态异常（如 std::unique_ptr 变成空，或自定义类里缓存索引错乱）。
- 检查类型是否可移动：
std::is_move_constructible_v<t></t>和std::is_move_assignable_v<t></t> - 对含裸指针的结构体，排序后原指针值不变，但所指内存顺序变了——别假设指针数组排序后指向关系仍成立
- 用
std::stable_sort替代时要注意：它不保证用快排，底层可能是归并，内存开销更大
标准库的排序已经足够好，真正要花时间的地方不是“怎么写快排”，而是理解你的数据分布、内存访问模式和类型语义——这些才决定最终性能上限。
