快速排序分区函数为何在指针越界时仍正常工作且无无限循环？

问题代码 #

int partition(int A[], int low, 
int high)
{
   int pivot = A[low];
   int i = low + 1;
   int j = high;
   int temp;

do
{
    while (A[i] <= pivot)
    {
        i++;
    }

    while (A[j] > pivot)
    {
        j--;
    }

    if (i < j)
    {
        temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
} while (i < j);

// Swap A[low] and A[j]
temp = A[low];
A[low] = A[j];
A[j] = temp;
return j;

}

疑问 #

当执行while (A[i] <= pivot)循环时，如果左侧所有元素都小于等于pivot，i会持续递增直至超出数组边界（high）；同理，while (A[j] > pivot)循环会让j在右侧元素都大于pivot时递减。
若i或j越界（例如i > high），难道不会导致do-while循环意外终止甚至进入无限循环吗？
比如输入数组为{12, 6, 7, 9, 10}，pivot为12时，i指针会递增到5（超出边界），但代码仍能正常运行并得到正确的分区结果。
请问：为何这段代码在i看似越界的情况下仍能正常工作？又是如何避免无限循环的？

解析 #

1. 越界后仍能正常运行的原因 #

以你举的例子{12,6,7,9,10}（low=0，high=4，pivot=12）来说：

• i从1开始递增，因为所有元素都<=12，i最终会到5（超出high=4）。
• 此时进入第二个while (A[j] > pivot)循环，j初始为4，A[4]=10<=12，循环直接终止，j保持4。
• 接下来判断i < j？5<4不成立，不会执行交换，直接退出do-while循环。
• 最后交换A[0]和A[4]，数组变为{10,6,7,9,12}，返回j=4，逻辑完全正确。

核心是：即使i越界，后续的j循环会快速终止，随后通过i < j的判断直接结束整个do-while循环，不会让越界的内存访问影响程序核心逻辑。

2. 不会触发无限循环的原因 #

无限循环的前提是i < j永远为真，但无论哪种场景都不满足：

• 若i越界（i>high），j最小只会到low（当j=low时，A[j]=pivot，while(A[j]>pivot)会终止），此时i>high >=j，i<j不成立，循环结束。
• 若j越界（j<low），i初始是low+1，必然大于j，i<j不成立，循环结束。
• 正常分区场景下，每次循环要么交换i、j位置的元素，要么i/j移动后导致i>=j，循环必然会终止。

3. 隐藏的风险 #

虽然代码大多时候能运行，但越界访问内存属于未定义行为：数组外的内存值是不确定的，有可能刚好是大于pivot的值让i停止，但也可能是小于等于pivot的值，导致i持续递增直到触发内存错误（比如程序崩溃）。

更严谨的写法应该给while循环加上边界判断，彻底避免越界：

// 修改后的循环条件，添加边界检查
while (i <= high && A[i] <= pivot) { i++; }
while (j >= low && A[j] > pivot) { j--; }

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