std::sort底层采用内省排序，融合快速排序、堆排序和插入排序以兼顾平均性能、最坏保障与小数据效率；需注意其不稳定、要求严格弱序比较器、仅支持随机访问迭代器。
std::sort 底层用的是 内省排序（Introsort），不是单一算法，而是快速排序、堆排序和插入排序的混合实现。
std::sort 为什么选内省排序？
它要同时解决三个现实问题：
- 快速排序平均性能好（
O(n log n)），但最坏情况退化到O(n²)（比如已排序数组选首/尾作 pivot） - 堆排序最坏也是
O(n log n)，但常数大、缓存不友好 - 插入排序对小数组（通常 ≤16 元素）比快排还快，且稳定
内省排序的做法是：
- 主体用三数取中 + 尾递归优化的快速排序
- 当递归深度超过阈值（一般是
2 × floor(log₂(n))），切换为堆排序，防止最坏退化 - 当子区间长度 ≤ 小阈值（常见是 16），直接切到插入排序
这个组合在实践中兼顾了平均性能、最坏保障和小数据效率。
实际使用中你需要注意什么？
-
std::sort不保证稳定性：相同元素的相对顺序可能改变。需要稳定排序请用std::stable_sort - 自定义比较器必须满足 严格弱序（strict weak ordering），否则行为未定义。常见错误包括：
return a （违反反对称性）- 比较逻辑依赖外部可变状态（如全局变量）
- 对浮点数直接用
而不处理 NaN
- 它要求迭代器是 随机访问迭代器，所以不能对
std::list或std::forward_list直接用std::sort；前者得用list::sort()，后者基本得转容器
std::partial_sort 是另一个故事
它用的是堆排序（大顶堆），只保证前 k 个最小/最大元素有序，其余无序。时间复杂度是 O(n log k)，适合“找 Top-K”场景，和 std::sort 的目标完全不同。
真正容易被忽略的点是：内省排序的“切换逻辑”完全由标准库实现决定，用户不可控也不可见——你调用 std::sort，就等于信任它的混合策略；想干预排序过程（比如强制用归并或观察每步分区），就得自己写。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
