为何该Hoare分区快速排序实现无越界错误且输出正确？

问题描述 #

当输入降序数组（例如[5,4,3,2,1]）时，这段Hoare分区代码中的变量i会持续递增直至超出数组边界。按常理这应触发段错误；即便未触发，交换越界的arr[i]与arr[j]时为何未引入垃圾值，且搭配快速排序函数后仍能得到正确的排序结果？

代码片段 #

int HoarePartition(int a[],int l,int r)
{
    int p,i,j,temp;
    p=a[l],i=l,j=r+1;
    do
    {
        do
        {
            i++;
        }while(a[i]<p);
        do
        {
            j--;
        }while(a[j]>p);
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }while(i<j);
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
    temp=a[l];
    a[l]=a[j];
    a[j]=temp;
    return j;
}

问题解析 #

1. 为何未触发段错误？

C语言中数组越界访问属于未定义行为——不是必然触发段错误。只有当越界访问的内存属于进程不可访问的区域（比如内核空间、其他进程的内存）时，才会触发段错误终止程序。如果越界的内存刚好是当前进程可访问的栈空间（比如数组后面的栈帧数据、填充字节），程序不会立刻崩溃，但这种行为极度危险，完全依赖运行环境的内存布局，不可依赖。

2. 交换越界值为何没引入垃圾值？

核心原因是循环内的越界交换被后续操作抵消了：

• 处理降序数组时，基准值p=a[l]是数组最大值，内层i的循环会一直递增，直到越界后遇到某个a[i]>=p（可能是栈上的随机值，但只要满足条件就停止）。
• 同时j的循环会递减到基准值的位置l（因为所有元素都<=p，只有a[l]等于p，不满足a[j]>p的循环条件）。
• 此时循环内执行一次a[i]（越界）和a[j]（基准位置）的交换，但外层循环的条件i<j不成立（i已经越界，远大于j），循环退出。
• 退出循环后，代码立刻再次执行a[i]和a[j]的交换——这相当于把刚才的越界交换完全撤销，数组内的有效元素没有被垃圾值污染。

3. 为何最终排序结果正确？

分区函数最终返回的j值是正确的：

• 两次交换抵消后，a[j]的位置还是原来的基准值。
• 最后一步交换a[l]和a[j]（此时j=l，等于无操作），返回j=l，即基准元素被放到了正确的位置（降序数组中最大值本就该在最左）。
• 后续快速排序递归处理j+1到r的子数组，这个过程会重复上述逻辑，最终完成整个数组的排序。

注意事项 #

虽然这段代码在特定场景下能正常运行，但越界访问是严重的bug，在不同的编译环境、内存布局下极有可能触发崩溃或产生错误结果。正确的Hoare分区应该在i的循环中加入i<=r的边界检查，避免越界：

do {
    i++;
} while (i <= r && a[i] < p);

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