快速排序实现出现Array index out of bound异常排查

这是一个选取数组首元素作为基准值的快速排序实现，代码如下：

public static int Partition(int[] container, int low, int high) 
{
    int pivot = container[low];
    int i = low, j = high;
    while (i<j) 
    {
        do
        {
            i++;
        } while (container[i]<=pivot);// 此处触发ArrayIndexOutBoundException异常
        do
        {
            j--;// 原注释对应i的遍历逻辑：递增i直至找到大于pivot的元素
        } while (container[j]>pivot);
        if (i<j) 
        {
           // 元素交换
            int temp = container[i];
            container[i] = container[j];
            container[j] = temp;
        }
    }
    int t2 = container[low];
    container[low] = container[j];
    container[j] = t2;
    return j;
}


public void QuickSort(int[] container, int low, int high) 
{
    if (low<high) 
    {
        int p = Partition(container, low, high);
        QuickSort(container, low, p);
        QuickSort(container,p+1,high);
    }
}

该实现的设计逻辑为：持续递增i值直到找到大于基准值pivot的元素，持续递减j值直到找到小于基准值pivot的元素。原逻辑认为外层while(i<j)可以避免数组索引越界，但实际运行仍会触发异常。

越界触发的根本原因 #

外层的i<j判断仅在每一轮大循环启动时生效，无法拦住do-while循环内部的索引溢出：

• do-while循环的特性是先执行循环体，再做条件判断，两个内层循环启动后会先执行i++/j--操作，再访问数组元素做值比较，过程中不会检查i、j是否超出当前处理的数组区间范围，也不会检查i是否已经大于等于j。
• 典型触发场景：当前处理区间内，从low+1位置开始的所有元素都小于等于基准值pivot时，i会持续递增，哪怕i已经超出当前区间上界、甚至超出数组最大索引，仍会执行container[i] <= pivot的判断，直接触发索引越界。
• 代码还存在注释错位问题：i的遍历逻辑注释被错误写到了j的自减行旁。

修复方案 #

给两个内层do-while的判断条件增加边界约束，保证i不会超过区间上界、j不会低于区间下界，同时修正错位的注释：

public static int Partition(int[] container, int low, int high) 
{
    int pivot = container[low];
    int i = low, j = high;
    while (i < j) 
    {
        do
        {
            i++;
            // 递增i直至找到大于pivot的元素，i不允许超过区间上界
        } while (i < high && container[i] <= pivot);
        do
        {
            j--;
            // 递减j直至找到小于等于pivot的元素，j不允许低于区间下界
        } while (j > low && container[j] > pivot);
        if (i < j) 
        {
            // 交换i、j位置的元素
            int temp = container[i];
            container[i] = container[j];
            container[j] = temp;
        }
    }
    // 将基准值交换到最终排序位置
    int t2 = container[low];
    container[low] = container[j];
    container[j] = t2;
    return j;
}

public void QuickSort(int[] container, int low, int high) 
{
    if (low < high) 
    {
        int p = Partition(container, low, high);
        QuickSort(container, low, p);
        QuickSort(container, p+1, high);
    }
}

修复后，i的递增最多走到high-1位置，j的递减最多走到low+1位置，不会出现索引超出数组范围的问题，排序逻辑和原设计完全一致。

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