Hoare快速排序中为何仅左半递归区间包含pivot？

核心本质：Hoare分区的返回值不是pivot的最终位置 #

产生这个疑问的核心原因是混淆了Hoare分区和Lomuto分区的返回值语义：

• Lomuto分区执行完成后，返回值p就是pivot的最终排序位置，满足所有A[lo..p-1] <= pivot、所有A[p+1..hi] >= pivot，pivot已经落在正确位置，后续递归自然可以将它排除在两个子区间外。
• Hoare分区的逻辑完全不同：双指针从两端向中间遍历的过程，只保证一个核心性质——返回值p是区间分割点，所有A[lo..p]的元素都小于等于所有A[p+1..hi]的元素。pivot本身并没有被放到最终排序位置，它可能落在左半段，也可能落在右半段，无法提前排除出递归区间。

为什么pivot被包含在lo..p区间，而不是p+1..hi？ #

这和分区函数的返回值选择直接相关，没有硬性的对错规则：

• 你贴的伪代码中，分区函数返回的是右指针最终停留的位置。双指针交叉终止时，右指针的位置天然是左半段的右端点，因此递归必须写成quicksort(A, lo, p)和quicksort(A, p+1, hi)，才能保证两个子区间无重叠、无遗漏覆盖所有元素，这种写法下pivot自然落在左半区间。
• 如果写分区函数时最终返回左指针的停留位置，递归边界就要对应调整为quicksort(A, lo, p-1)和quicksort(A, p, hi)，这时候pivot就会落在右半区间，逻辑完全等价，只要返回值语义和递归边界匹配即可。

不存在“pivot只能放左区间不能放右区间”的限制，唯一要求是边界写法和分区返回值的语义对齐。

会不会出现lo..p等于原区间导致无限递归？ #

正确实现的Hoare分区不会出现这个问题。
Hoare分区的循环终止条件天然保证：只要传入区间满足lo < hi，返回的分割点p一定满足lo <= p < hi。简单算一下子区间长度就能验证收敛性：

• 原区间长度为hi - lo + 1
• 左区间lo..p的长度为p - lo + 1，由于p < hi，最大长度为(hi-1) - lo +1 = hi - lo，比原区间长度小1
• 右区间p+1..hi的长度为hi - (p+1) + 1 = hi - p，由于p >= lo，最大长度为hi - lo，同样比原区间长度小1

两个子区间长度都严格小于原区间，递归一定会在有限步内收敛到区间长度为0或1的终止条件，根本不会出现子区间和原区间完全一致的情况。
维基百科提到的无限递归风险，只会出现在错误实现中：比如指针移动条件写错（例如把左指针的判断条件A[i] < pivot写成A[i] <= pivot，或反过来写错右指针条件），导致返回的p等于hi，这时候左区间和原区间完全一致，才会触发死循环。那种需要额外交换pivot的处理，是Hoare最早提出的原始版本里的兼容逻辑，现在主流的正确实现只要指针判断条件写对，不需要额外加交换逻辑就能保证算法正常终止。

内容的提问来源于stack exchange，提问作者AndW