三路快排需用lt、gt、i三指针将区间划分为三段，避免重复元素导致退化；标准std::sort不自动启用三路分区，故手写时须显式实现该逻辑。
三路快排在 C++ 中怎么写才不退化成 O(n²)
标准 std::sort 对含大量重复元素的数组不会自动切三路，它用的是 introsort（混合堆+快排+插入），但面对 vector<int>{1,1,1,...,2,2,2,...,3}</int> 这类数据，普通快排分区仍可能反复把相等元素扫进同一侧，导致递归深度失控。
手写三路快排的关键是：用三个指针 lt、gt、i 把区间划为「
- 基准选
nums[l]或随机索引，**别用nums[r]且不打乱——升序数组下直接 O(n²)** -
i从l+1开始，不是l；lt初始化为l，gt初始化为r - 循环中遇到
nums[i] == pivot时，只做i++，不交换——这是“三路”和“双路”的本质区别 - 递归调用时，左段是
[l, lt-1]，右段是[gt+1, r]，中间[lt, gt]全等，不用再排
void quick3way(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 <= gt) {
if (nums[i] < pivot) swap(nums[lt++], nums[i++]);
else if (nums[i] > pivot) swap(nums[i], nums[gt--]);
else i++;
}
quick3way(nums, l, lt - 1);
quick3way(nums, gt + 1, r);
}
std::sort 能不能直接利用三路逻辑
不能。C++ 标准库不暴露三路接口，std::sort 的比较器只返回 true/false，无法表达「小于/等于/大于」三态。你传进去的 operator 或 lambda 只能做二元判断，底层没法据此合并相等块。
如果你只是想省事又需要处理重复元素，更现实的做法是：先用 std::sort 排好，再用 std::unique 去重（或配合 erase），但注意这会改变原顺序且不压缩中间段——它只是把重复项挪到末尾。
立即学习“C++免费学习笔记（深入）”；
- 真正要保序压缩重复段，得自己遍历+双指针，比如用
std::remove_duplicates（C++20）或手写std::unique_copy -
std::stable_sort不解决重复问题，它只保证相等元素相对位置不变，性能还更差 - 对
std::vector<string></string>这类类型，三路快排收益有限——字符串比较本身开销大，分支预测失效比分区不均影响更大
什么时候三路快排反而更慢
当重复元素占比低于 ~15%，或者数据规模小于 100 时，三路快排的额外指针管理和分支判断会拖慢速度，不如标准 std::sort 的高度优化汇编实现。
还有两个隐蔽坑：
- 对
std::list或其他非随机访问容器，三路快排无法高效 swap 中间元素，必须转成 vector 再排，内存和时间成本翻倍 - 自定义类型若没有
operator 但有 <code>operator==，三路逻辑里容易误用==替代比较，导致分区错乱——三路依赖的是严格全序，不是等价关系 - 多线程环境下，手写递归分治若没加栈深限制（如改用迭代+显式栈），可能触发 stack overflow，而
std::sort内部做了深度控制
替代方案：partial_sort + unique 组合够不够用
够用，但要看场景。如果你只需要前 k 个最小值且允许重复，std::partial_sort 比完整三路快排快得多；如果还要去重后再取 top-k，就先 std::sort + std::unique，再 std::make_heap 做 top-k。
但注意：std::unique 不是删除函数，它只把重复项移到末尾并返回新逻辑长度，你得手动 erase 才真正缩容：
auto last = std::unique(v.begin(), v.end()); v.erase(last, v.end());
这个组合在工程中更稳——没栈溢出风险，兼容所有迭代器类型，且编译器对 STL 函数内联和向量化更友好。三路快排只在你知道数据结构、重复率极高、且 profiling 确认瓶颈在排序时才值得投入。
真正难的不是写对三路分区，而是判断当前数据到底适不适合它——测一遍 std::sort 和你手写的耗时差，比看理论复杂度管用得多。
