java - 如果数组长度为 100000，则使用归并排序计算反转会给出负数

Question

我仍然是编程初学者，我正在学习在线类(class)(算法)

练习题之一是计算包含 100000 个随机排序的数字的文件中的反转次数

这是我的代码

    package algo_inversion;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;

public class Algo_inversion {
    public static int splitMerge(int[]A,int start,int mid,int finish){
        int count=0;
        int []L=new int[mid+2-start];
        int []R=new int[finish-mid+1];
        System.arraycopy(A, start, L, 0, L.length-1);
        L[L.length-1]=5000000;//infinity

        for(int i=0;i<R.length-1;i++){
            R[i]=A[mid+1+i];
        }
        R[R.length-1]=5000000;//infinity

        int x=0;
        int y=0;
        for(int k=start;k<finish+1;k++){
            if(L[x]<=R[y]){
                A[k]=L[x];
                x++;
            }
            else{
                A[k]=R[y];
                y++;
                count+=L.length-1-x;
            }
        }
        return count;        
    }
    public static int countMerge(int []A,int start, int finish){
        if(finish<=start){
            return 0;
        }
        else{
            int mid=(finish+start)/2;
                int leftCount=countMerge(A,start,mid);
                int rightCount=countMerge(A,mid+1,finish);
                int splitCount=splitMerge(A,start,mid,finish);
                return(leftCount+rightCount+splitCount);
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        int []a=new int[100001];
       Scanner in= new Scanner(new FileReader("IntegerArray.txt"));
       int i=0;
        while(in.hasNext()){
            a[i]=in.nextInt();
            i++;
        }
        in.close();
        System.out.println("inversions=: "+countMerge(a, 0, i-1));

    }
}

我在大小从 1 到 200 的随机数组上进行了尝试，效果非常好但是使用文件中的数组它给了我一个负数!我只是不知道是什么原因造成的，希望能得到任何帮助^_^

Answer 1

大小为 N 的数组中最坏情况的反转次数是 N*(N-1)/2 。 int 所能容纳的最高值大约为 20 亿，因此数组的大小大于 65,000有机会溢出 int ，使结果看起来为负。

您应该切换到long扩展计数器可表示的值的范围:

public static long splitMerge(int[]A,int start,int mid,int finish) {
    long count = 0;
    ...
}
public static long countMerge(int []A,int start, int finish) {
    ...
}