三路划分通过隔离重复元素而非避免重复来防止退化：将等于基准的元素集中到中间段[lt, gt]，递归仅处理小于段[low, lt-1]和大于段[gt+1, high]，配合随机或三数取中选基准，避免pivot偏斜。
三路划分怎么应对重复元素导致的递归退化
普通快排在遇到大量重复元素时，partition 函数反复把相等元素分到左右子区间，导致每次递归只减少一两个元素，实际退化成 O(n²)。三路划分的核心不是“避免重复”，而是“隔离重复”——把所有等于基准的元素一次性推到中间段，后续完全跳过这部分递归。
关键指针行为：lt、gt、i 为什么这样设计
三路划分依赖三个指针协同移动：lt（小于区右边界）、gt（大于区左边界）、i（当前扫描位）。常见错误是让 i 在交换 arr[i] 和 arr[gt] 后也自增——这会漏判刚从右边换过来的未知值。
arr[i] ：交换 <code>arr[i]和arr[lt]，然后lt++、i++-
arr[i] == pivot：直接i++（不交换，不移动边界） -
arr[i] > pivot：交换arr[i]和arr[gt]，仅gt--（i不动）
这个设计保证了：扫描结束时，[low, lt-1] 全小于，[lt, gt] 全等于，[gt+1, high] 全大于——中间段长度可能很大，但后续递归直接跳过。
基准选择必须配合三路划分，否则白搭
即使用了三路 partition，如果还用固定取首/尾作 pivot，在极端重复数据（如全为 5）下，第一次划分后 lt = low、gt = high，整个数组被划进中间段，递归直接终止——看似快，实则隐藏风险：若数据是“几乎全等 + 少量离群值”，固定 pivot 仍可能让 lt 或 gt 偏移极小，退化重现。
必须搭配：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 随机选 pivot：
swap(arr[low], arr[low + rand() % (high - low + 1)]) - 或三数取中：
median_of_three(arr, low, mid, high)，再 swap 到low
否则三路划分只是“看起来更聪明”，实际没解决根本的 pivot 偏斜问题。
递归调用范围别写错：中间段真的不能进递归
划分完成后，常见手误是写成 QuickSort(arr, low, lt-1) 和 QuickSort(arr, gt+1, high) —— 这没错；但有人会多写一句 QuickSort(arr, lt, gt)，以为“保险起见”。这是严重错误：中间段所有值已等于 pivot，无需任何比较或交换，强行递归只会增加栈开销，且在 lt > gt 时引发越界。
正确做法只有两段递归：
QuickSort(arr, low, lt - 1); QuickSort(arr, gt + 1, high);
中间段 [lt, gt] 是最终位置，原地不动——这才是三路划分节省时间的关键落点。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
