Java归并排序实现逆序对计数报数组下标越界问题排查

运行基于归并排序实现数组逆序对计数的代码时，抛出数组越界异常：index 4 is out of bounds for 4 length，原实现代码如下：

package dsa450;

import java.util.*;

public class countInversion {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the size of Array");
        int n=sc.nextInt();
        int arr[]=new int[n];
        System.out.println("Enter the size of Array");
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }

        int p=arr.length;
        int temp[]=new int[n];
        int ans=mergeSort(arr,temp,0,n-1);
        System.out.println(ans);

    }

    static int mergeSort(int[] arr,int[]temp,int l,int r) {
         int inv=0;
         int mid;
        if (l<r) {
        
            mid=(l+r)/2;
            inv+= mergeSort(arr,temp,l, mid);
            inv+= mergeSort(arr,temp,mid+1,r);
            inv+= merge(arr,temp,l,mid+1,r);
        }
           return inv;
    }

    private static int merge(int []arr,int []temp,int l,int mid,int r) {
        
           
        int i=0;
        int j=0;
        int k=0;
        int swap=0;
        while(i<=mid-1 && j<=r) {
            if(arr[i]<=arr[j]) {
                temp[k++]=arr[i++];
                
            }
            else {
                temp[k++]=arr[j++];
                swap+=(mid-i);
            }
        }
        while(i<=mid-1) {
            temp[k++]=arr[i++];
            
        }
        
        while(j<=r) {
            temp[k++]=arr[j++];
            
        }
        
        for(i=l;i<=r;i++) {
            arr[i]=temp[i];
        }
        
        return swap;
    }

}

异常截图

核心错误全部集中在merge方法的指针初始化逻辑，和标准归并实现的偏差点如下：

• 三个遍历指针初始值完全错误：归并排序每次处理的是原数组中[l, r]区间的子段，不是从0下标开始的整个数组。原代码将左段指针i、右段指针j、临时数组写入指针k全部初始化为0，一方面会导致遍历左右段时访问的不是当前待归并的子段数据，逻辑完全失效；另一方面写入临时数组时从0位置开始累加，处理长度为4的数组时k值会累加到4，直接访问temp[4]触发越界，和遇到的报错完全匹配。
• 临时数组回写逻辑存在隐患：因为指针初始值错误，回写时temp[i]取到的是临时数组前置位置的默认值0，会覆盖原数组的有效数据，即使不触发越界也会得到错误的计算结果。
• 附加小问题：main方法中输入数组元素前的提示语重复打印了"Enter the size of Array"，属于文案错误不影响运行，但容易误导输入。

将merge方法中的三个指针初始值改为对应子段的起始位置即可：

• 左段遍历指针i初始值设为l，对应左段区间[l, mid-1]
• 右段遍历指针j初始值设为mid，对应右段区间[mid, r]
• 临时数组写入指针k初始值设为l，和待归并区间的起始位置对齐

修正后的完整可运行代码：

package dsa450;

import java.util.*;

public class countInversion {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the size of Array");
        int n=sc.nextInt();
        int arr[]=new int[n];
        // 修正提示文案
        System.out.println("Enter the array elements");
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }

        int temp[]=new int[n];
        int ans=mergeSort(arr,temp,0,n-1);
        System.out.println("The number of inversions is: " + ans);

    }

    static int mergeSort(int[] arr,int[]temp,int l,int r) {
         int inv=0;
         int mid;
        if (l<r) {
            mid=(l+r)/2;
            inv+= mergeSort(arr,temp,l, mid);
            inv+= mergeSort(arr,temp,mid+1,r);
            inv+= merge(arr,temp,l,mid+1,r);
        }
        return inv;
    }

    private static int merge(int []arr,int []temp,int l,int mid,int r) {
        // 修正指针初始值
        int i=l;
        int j=mid;
        int k=l;
        int swap=0;
        while(i<=mid-1 && j<=r) {
            if(arr[i]<=arr[j]) {
                temp[k++]=arr[i++];
            }
            else {
                temp[k++]=arr[j++];
                swap+=(mid-i);
            }
        }
        while(i<=mid-1) {
            temp[k++]=arr[i++];
        }
        
        while(j<=r) {
            temp[k++]=arr[j++];
        }
        
        // 回写临时数组到原数组对应区间
        for(i=l;i<=r;i++) {
            arr[i]=temp[i];
        }
        
        return swap;
    }
}

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