0

我已经实现了使用归并排序计算数组反转的程序。程序与归并排序相同，倒数计数略有变化。

public class HMergeSortVer1 {

    public int inversions;

    public void msort(int [] A,int p, int r){
        if(p<r){
            int q=(int) Math.floor((r+p)/2);
        //  System.out.println("q--"+q);
            msort(A, p, q);
            msort(A, q+1, r);
            merge(A,p,q,r);
        }

    }

    private void merge(int [] A,int p,int q,int r){
        //System.out.println("In the merge");
        int n1=q-p+1; // number of elements in left array
        int n2=(r-q);
        int[] L=new int[n1+1];
        int[] R=new int[n2+1];
        for(int i=0;i<n1;i++){
            L[i]=A[p+i];
        }
        for(int j=0;j<n2;j++){
            R[j]=A[q+j+1];
        }
        L[n1]=Integer.MAX_VALUE;
        R[n2]=Integer.MAX_VALUE;
        int i=0;
        int j=0;
        for(int k=p;k<(r+1);k++){
            if(L[i]<= R[j]){                
                A[k]=L[i];
                i=i+1;
            }
            else {
                A[k]=R[j];
                j=j+1;
                int numOFElements=n1-i; 
                inversions=inversions+numOFElements; // this counts inversion
            }
        }
    }

}

它适用于某些情况，但在其他情况下会给出错误的输出。如果我遗漏了什么，请告诉我。

4

2 回答 2

0

问题是您使用“反转”作为“int”数据类型，因此对于非常大的输入它会溢出。改用“long”，它应该可以正常工作。

于 2013-07-10T22:56:22.717 回答
0

这是 Cormen book 的相同实现。但在书中它假设数组是 1 索引的。大概就是这个了。考虑到您有 0 索引数组，请尝试更改您的代码。

如果它是 0-indexed 那么你的 n1 变量应该等于 qp

于 2013-07-05T03:19:20.553 回答