Lomuto分区易错因返回“≤pivot末索引”却被误作pivot位置，致区间重叠或遗漏；必须将pivot置末尾并执行swap归位；常见错误为越界或无限递归。
为什么Lomuto分区在C++里容易写错边界
因为partition函数返回的是“最后一个≤pivot元素的索引”，但新手常误以为是pivot最终位置，导致递归调用时左右区间重叠或遗漏一个元素。Lomuto方案必须确保pivot放在末尾，且循环结束时swap(arr[i], arr[high])——这个swap不能省，否则pivot没归位。
常见错误现象：std::out_of_range 或无限递归，多因low和high传参时没做if (low 检查；或者把<code>i初值设为low（应为low - 1）。
-
i从low - 1开始，每次遇到≤pivot就先++i再swap - 循环用
j从low遍历到high - 1，不包含high（pivot所在） - 最后
swap(arr[i + 1], arr[high])，返回i + 1——这才是pivot的终态下标
Hoare分区为何更难调试但性能更好
Hoare方案不用额外swap pivot，左右指针从两端向内收缩，在首次相遇时就完成分区，平均交换次数更少。但它不保证pivot落在返回索引上，返回值只是分界点，左右子数组都需递归——这点和Lomuto有本质区别，容易漏掉quick_sort(arr, low, pivot_index)中的pivot_index是否该包含。
典型错误：把while (arr[i] 写成<code><=，或忘记在do-while中加i < j保护，导致越界访问；还有人直接用return i，其实应返回j（或i，取决于实现方向），标准Hoare返回的是左半区右边界。
立即学习“C++免费学习笔记（深入）”；
- 初始化
i = low - 1,j = high + 1，然后do { ++i; } while (arr[i] - 对应
do { --j; } while (arr[j] > pivot)，两个do-while必须配对 - 相遇判断用
if (i >= j) return j，之后递归范围是[low, j]和[j + 1, high]
C++原地排序必须处理的三个细节
模板参数、迭代器支持和重复元素稳定性不是可选项，而是决定代码能否编译通过或跑出预期结果的关键。比如用std::vector<int>::iterator传参时，low和high必须是同类型，不能混用int下标；又比如全相同元素时，Lomuto可能退化成O(n²)，而Hoare在arr[i] == pivot时不移动指针，反而更鲁棒。
- 模板函数声明建议用
template <typename RandomIt, typename Compare = std::less<>>，兼容自定义比较 - 分区内避免
int下标运算，统一用std::distance(low, high)判空，或直接if (low >= high) return - 为防栈溢出，小数组（如
std::distance(low, high) < 10）应切回std::insertion_sort，但注意std::sort内部已做此优化，自己实现时别忘了
一个能直接粘贴测试的Hoare版完整片段
下面这段去掉注释就能跑，适用于std::vector<int>或原始数组指针，关键在于hoare_partition返回后，左右区间都含有效数据，递归时不能跳过任一端点：
template <typename T>
int hoare_partition(std::vector<T>& arr, int low, int high) {
T pivot = arr[low];
int i = low - 1, j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
std::swap(arr[i], arr[j]);
}
}
<p>void quick_sort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int p = hoare_partition(arr, low, high);
quick_sort(arr, low, p); // 注意：p 是左区间的右边界，包含在内
quick_sort(arr, p + 1, high); // 右区间从 p+1 开始
}
}</p>真正容易被忽略的是：Hoare分区不固定pivot位置，所以无法像Lomuto那样用pivot值做后续剪枝；另外，当数组极小时（如2个元素），i和j可能初始就交叉，do-while里的条件必须严格匹配，否则第一次循环就崩。
