在Java插入排序中提前执行d--;为何抛出数组越界异常？

咱们先看看你这段出问题的代码：

public class JavaApplication28 { 
    public static void main(String[] args) { 
        int arr[]={5,4,3,2,1}; 
        int n=arr.length; 
        int d=0; 
        for(int i=1;i<n;i++){ 
            d=i; 
            while(d>0 && arr[d-1]>arr[d]){ 
                d--; // 这里提前执行了d--
                int temp=arr[d-1]; 
                arr[d-1]=arr[d]; 
                arr[d]=temp; 
            } 
        } 
        for(int k=0;k<n;k++){ 
            System.out.println(arr[k]); 
        } 
    } 
}

抛出的ArrayIndexOutOfBoundsException: -1异常，原因其实非常直接——你提前执行d--后，后续代码访问了负数索引的数组元素。

咱们拿第一次循环的场景拆解一下：

• 初始i=1，d=i=1
• while循环条件d>0 && arr[d-1]>arr[d]：1>0成立，且arr[0]=5>arr[1]=4也成立，进入循环
• 先执行d--，此时d变成0
• 接下来执行int temp=arr[d-1]，也就是arr[0-1] = arr[-1]——数组的合法索引范围是从0到length-1，负数索引完全不合法，直接触发越界异常

那正确的插入排序逻辑应该怎么写？我们需要先把当前位置的元素和前一个位置的元素交换，再把指针往前移（也就是d--），这样就能保证每次访问数组时，索引都是合法的：

while(d>0 && arr[d-1]>arr[d]){
    // 先交换当前d和d-1位置的元素
    int temp=arr[d];
    arr[d]=arr[d-1];
    arr[d-1]=temp;
    // 再把指针往前移，继续比较
    d--;
}

这么修改后，每次d--之后，下一次循环会先判断d>0，只有满足条件才会继续执行数组访问，从根源上避免了负数索引的出现。

简单说，你把d--的时机搞反了：提前让指针越界，后续代码自然会访问到不存在的数组位置。

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