std::sort 平均和最坏时间复杂度是多少
std::sort 在 C++ 标准中只要求平均时间复杂度为 O(N log N)，不保证最坏情况仍是 O(N log N)；但所有主流实现（GCC libstdc++、Clang libc++、MSVC STL）都采用**内省排序（introsort）**，因此实际最坏时间复杂度也是 O(N log N)。
这和纯 std::qsort（C 风格）或手写快排不同——后者若 pivot 选得差，可能退化到 O(N²)。而 std::sort 不会，它会在递归过深时自动切换策略。
常见误解：以为 std::sort 就是“快排”，其实它是个混合策略：
- 小数组（通常 ≤ 16 元素）用插入排序（
std::insertion_sort） - 中等规模用三数取中 + 尾递归优化的快速排序
- 递归深度超过
2 × floor(log₂ N)时，切到堆排序（std::make_heap+std::sort_heap）
为什么内省排序要限制递归深度
快排的递归深度直接关联 pivot 质量。最坏情况下（如已排序数组 + 固定首元素作 pivot），每次只减少一个元素，递归深度达 N，栈空间爆炸且性能崩坏。
立即学习“C++免费学习笔记（深入）”；
内省排序用 log N 级别的深度阈值作为“安全阀”：
- libstdc++ 中阈值定义为
2 * std::__lg(__last - __first)（即2 × floor(log₂ len)） - 一旦当前递归调用栈深度超过该值，立即放弃快排，改用堆排序兜底
- 堆排序虽常数大，但严格
O(N log N)且原地、稳定栈空间（O(1)辅助空间）
这个切换不是在运行时“检测是否变慢”，而是**纯深度计数**——不看数据分布，只防最坏递归路径。
std::sort 不稳定，但 stable_sort 是堆排序吗
不。这是个高频混淆点：std::sort 是不稳定的（equal elements 可能换位），而 std::stable_sort 保证稳定性，但它**不一定是堆排序**。
实际实现策略更复杂：
- libstdc++：小数组用插入排序；较大时尝试归并排序（
std::merge），若内存足够则分配临时缓冲区，否则降级为原地归并（代价高） - libc++：优先用归并排序，有额外内存就用外部分配，否则 fallback 到某种优化过的堆排序变体
- MSVC STL：类似，但对小数组用自底向上归并，避免递归栈
所以 std::stable_sort 时间复杂度通常是 O(N log N)，但空间复杂度可能是 O(N)（取决于是否能分配缓冲区）。它和 std::sort 的内省机制完全无关。
自定义比较函数影响内省排序行为吗
不影响核心流程（递归深度监控、算法切换逻辑），但会影响：
-
std::sort对比较函数的要求：必须是 **strict weak ordering**，否则行为未定义（UB）——可能崩溃、死循环、或看似排好实则错乱 - 若比较函数有副作用（比如打印日志、修改外部状态），会被多次调用且顺序不可预测（快排分治过程导致）
- 比较开销大会拖慢整体性能，但不会触发提前切换到堆排序——切换只看递归深度，不看单次比较耗时
一个典型错误是写成：[a, b] { return a —— 这违反 strict weak ordering（相等时返回 true，导致排序器误判等价关系），结果不可靠。
内省排序的精妙之处不在“多聪明”，而在“多保守”：它不赌数据分布，而是用可证的深度上界 + 确定性兜底，把最坏情况关进笼子。真正容易被忽略的是——你无法通过重载 operator 或传入 lambda 来改变它的切换逻辑，那部分完全由实现封闭管理。
