快速排序代码出现ArrayIndexOutOfBoundsException异常求助

你的快速排序代码抛出数组越界异常，问题出在partition方法的两个内层while循环缺少边界限制：

• 第一个循环while(arr[start]<=pivot)未限制start的上限，当数组所有元素都小于等于基准值时，start会一直递增到ub+1，此时访问arr[start]会超出数组范围。
• 第二个循环while(arr[end]>pivot)未限制end的下限，当数组所有元素都大于基准值时，end会一直递减到lb-1，访问arr[end]同样会越界。

修复后的完整代码：

public class Solution {

    public static int partition(int []arr,int lb,int ub)
    {
        int start=lb;
        int end=ub;
        int pivot=arr[lb];
        while(start<end)
        {
            // 增加start < ub的边界限制，防止越界
            while(start < ub && arr[start]<=pivot)
            {
                start++;
            }
            // 增加end > lb的边界限制，防止越界
            while(end > lb && arr[end]>pivot)
            {
                end--;
            }
            if(start<end)
            {
                int temp=arr[start];
                arr[start]=arr[end];
                arr[end]=temp;
            }
        }
        int temp=arr[lb];
        arr[lb]=arr[end];
        arr[end]=temp;
        return end;
    }
    
    public static void quickSort(int[] input,int startIndex, int endIndex) {
        if(startIndex<endIndex)
        {
            int loc=partition(input, startIndex, endIndex);
            quickSort(input,startIndex,loc-1);
            quickSort(input,loc+1,endIndex );
        }
    }
    
}

关键修复点说明 #

• 给第一个内层while循环添加start < ub，确保start不会超出数组的上边界（数组最大索引为ub）。
• 给第二个内层while循环添加end > lb，确保end不会低于数组的下边界（数组最小索引为lb）。

修改后既能避免数组越界，又能保证快速排序的逻辑正确性。

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