为何我的插入排序在特定测试用例中出现数组越界错误？

你的代码出现数组越界的根本原因是while循环缺少边界判断条件，当待插入元素是数组中最小的元素时，循环会持续让i递减到0，此时继续访问arr[i-1]就等于访问arr[-1]，这显然超出了数组的合法索引范围（数组索引从0开始）。

具体场景拆解 #

看你失败的测试用例：10 2 3 4 5 6 7 8 9 10 1，待插入的元素是1，它比数组中所有元素都小：

1. 初始时i = n-1 = 9，copy = 1
2. 进入循环判断copy < arr[i-1]（即1 < arr[8] = 10），条件成立，执行元素后移，i减到8
3. 重复这个过程，i会依次减到7、6...直到0
4. 此时循环判断copy < arr[i-1]，也就是arr[-1]，直接触发数组越界异常

而成功的测试用例5 2 4 6 8 3中，待插入的3不是数组最小元素，当i减到1时，arr[i-1] = arr[0] = 2，3 < 2不成立，循环提前终止，不会触发越界。

修复方案 #

修改while循环的条件，增加i > 0的判断，确保只有当i大于0时才去访问arr[i-1]：

static void insertionSort1(int n, int[] arr) {
    int copy = arr[n-1];
    int i = n - 1;
    // 新增i > 0的判断，避免访问arr[-1]
    while (i > 0 && copy < arr[i-1]){ 
        arr[i] = arr[i-1];
        for(int k = 0; k < arr.length; k++){
            System.out.print(arr[k] + " ");
        }
        System.out.println();
        i--;
    }
    arr[i] = copy;
    for(int m = 0; m < arr.length; m++){
        System.out.print(arr[m] + " ");
    }
}

这样当i递减到0时，循环条件不满足，会直接退出循环，然后把copy赋值给arr[0]——这正是最小元素应该在的位置，同时彻底避免了数组越界问题。

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