c++oding="utf-8" ?>
std::sort已足够快，无需手写——它采用introsort（快排+堆排降级+插入排序），含三数取中、递归防护、内联与向量化优化；-O2/-O3下为高效汇编，-O0则性能骤降。
std::sort 已经足够快，别轻易自己写
绝大多数场景下，std::sort 比你手写的快排更快、更稳。它底层是 introsort（快排 + 堆排序降级 + 小数组插入排序），还带三数取中、递归深度防护、编译器内联和向量化优化。你在 -O2 或 -O3 下调用 std::sort，实际执行的是高度优化的汇编代码；而 -O0 下性能可能断崖下跌——这不是算法问题，是优化开关没开。
常见错误现象：std::sort 在已近序或大量重复数据上表现差？先确认是不是用了 -O0 编译，或者传了低效比较器（比如对 std::string 用 operator 但没考虑 short string optimization）。
- 除非 profiling 明确指出排序是瓶颈，且输入满足「重复率 >30%」+「规模 >1000」，否则不要替换
std::sort - 想稳定排序？用
std::stable_sort，但它不解决重复元素问题，且内存开销更大 - 需要保序去重？
std::unique配合erase是标准做法，不是排序替代方案
三路快排只在高重复数据上真有用
三路快排把数组划成「小于 pivot」「等于 pivot」「大于 pivot」三段，递归只处理两边，中间重复块直接跳过。当重复元素占比高时（比如日志状态码、枚举值数组），它能把平均时间趋近 O(n)；但常数因子比双路快排高，小数组或低重复率（
实操建议：直接复用经典三指针模板，注意边界和迭代器有效性：
void quick3way(std::vector<int>& nums, int l, int r) {
if (l >= r) return;
int pivot = nums[l];
int lt = l, i = l + 1, gt = r;
while (i pivot) std::swap(nums[i], nums[gt--]);
else i++;
}
quick3way(nums, l, lt - 1);
quick3way(nums, gt + 1, r);
}</int>
- 基准选
nums[l]简单，但易被恶意输入卡死；生产环境建议加三数取中或随机 swap -
std::vector可用，std::list不适用——三路依赖随机访问 - 别用
std::partition手动拼三路：容易迭代器失效或越界，且无法保证“等于”段连续
std::sort 根本不支持三路逻辑
std::sort 的比较器只能返回 true/false，底层无法感知「等于」态，所以它没法利用三路划分。你传的 operator 或 lambda 只能做二元判断，标准库不会、也不能据此合并相等块。
如果你硬要结合三路思想又不想脱离标准库，可行路径只有：
- 先用
std::sort排好，再用std::nth_element+ 自定义分区逻辑提取中位数段（适合 Top-K 类需求） - 对
std::vector<:string>这类类型，三路收益极小——字符串比较开销远大于分支预测失败成本 - 别试图 patch libstdc++ 源码改 introsort 递归阈值：它是编译期硬编码，升级工具链即失效
手写快排必须加至少两项基础优化
如果真要手写（比如面试、嵌入式无 STL、或教学演示），不加优化的裸快排在真实数据上极易退化。必须包含：
- 小数组切换：当
r - l 时，调用插入排序 —— 省掉递归开销和 pivot 选择成本 - 抗退化 pivot：至少用三数取中（
nums[l]、nums[mid]、nums[r]中间值），比纯随机更可控 - 避免栈溢出：introsort 的递归深度阈值默认是
2 * floor(log2(n))，手写版若没降级机制，大数据量下可能爆栈
真正难的从来不是写出来，而是验证边界条件：空数组、全等元素、已排序、逆序、含 INT_MIN/INT_MAX —— 这些 case 一跑就暴露指针越界或死循环。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
