关于快速排序Hoare分区未做边界检查的原因问询

很多快速排序的Hoare分区实现里，寻找比基准值（pivot）大/小元素的循环都没加边界检查，看起来好像会越界，但其实这是安全的，核心原因在于基准值本身就是数组中的一个元素。

拿你给出的原代码举例：

# Partition using Hoare's Partitioning scheme
def partition(arr, low, high):
 
    pivot = arr[low]
    (i, j) = (low - 1, high + 1)
 
    while True:
 
        while True:
            i = i + 1
            if arr[i] >= pivot:
                break
 
        while True:
            j = j - 1
            if arr[j] <= pivot:
                break
 
        if i >= j:
            return j
 
        swap(arr, i, j)

为什么不会越界？ #

1. i的循环不会越上界：
   pivot选的是arr[low]，当i从low-1开始递增时，只要i走到low的位置，arr[i]就等于pivot，满足arr[i] >= pivot的条件，循环立刻终止。哪怕数组是完全降序的，i也不会走到high+1的位置——因为在到达low时就已经触发break了。

2. j的循环不会越下界：
   同理，j从high+1开始递减，当j走到low的位置时，arr[j]等于pivot，满足arr[j] <= pivot的条件，循环终止，不会走到low-1的位置。

你添加的边界检查反而有问题 #

看你修改后的代码：

# Partition using Hoare's Partitioning scheme
def partition(arr, low, high):
 
    pivot = arr[low]
    (i, j) = (low - 1, high + 1)
 
    while True:
 
        while True:
            i = i + 1
            if arr[i] >= pivot and i < high:
                break
 
        while True:
            j = j - 1
            if arr[j] <= pivot and j > low:
                break
 
        if i >= j:
            return j
 
        swap(arr, i, j)

这里的边界条件i < high和j > low是错误的：

• 当i走到high位置时，如果arr[high] >= pivot（比如分区后右侧只剩pivot的情况），i < high不成立，条件整体为假，循环会继续让i递增到high+1，直接触发数组越界。
• 同理，当j走到low位置时，j > low不成立，循环会让j递减到low-1，同样触发越界。

举个降序数组的实际运行例子 #

比如数组是[5,4,3,2,1]，low=0，high=4，pivot是5：

1. i初始为-1，第一次递增到0，arr[0]=5 >=5，break，i停在0，不会继续越界。
2. j初始为5，第一次递减到4，arr[4]=1 <=5，break，j停在4。
3. 交换i和j位置的元素，数组变成[1,4,3,2,5]。
4. 下一轮循环：i从0开始递增，直到i=4时arr[4]=5 >=5，break；j从4递减到3时arr[3]=2 <=5，break。此时i=4 >=j=3，返回j，整个过程没有越界。

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