Mergesort Implementation ..计算数组中的反转次数

Question

我正在参加算法的在线课程,并尝试实现一个在数字列表中查找反转次数的mergesort实现.但是,由于返回的反转次数明显低于我在执行暴力攻击时所获得的数量,因此无法确定我的实施方式是错误的.我已经将我的mergesort方法的实现放在下面

 /**
   * 
  */

 package com.JavaReference;

 import java.io.BufferedReader;
import java.io.FileReader;
 import java.io.IOException;

public class ReadFile {


public static void main(String args[]){
    int count=0;
    Integer n[];


int i=0;
    try{
    n=OpenFile();
    int num[] = new int[n.length];

    for (i=0;i<n.length;i++){
        num[i]=n[i].intValue();
    //  System.out.println( "Num"+num[i]);
    }
    count=countInversions(num);


    }
    catch(IOException e){
        e.printStackTrace();
    }

    System.out.println(" The number of inversions"+count);


}




 public static Integer[] OpenFile()throws IOException{

    FileReader fr=new FileReader("C:/IntegerArray.txt");// to put in file name.

BufferedReader textR= new BufferedReader(fr);
int nLines=readLines();
System.out.println("Number of lines"+nLines);

Integer[] nData=new Integer[nLines];
for (int i=0; i < nLines; i++) {
    nData[ i ] = Integer.parseInt((textR.readLine()));

    }
textR.close();

return nData;


}

public static int readLines() throws IOException{


FileReader fr=new FileReader("C:/IntegerArray.txt");
BufferedReader br=new BufferedReader(fr);


int numLines=0;
//String aLine;

while(br.readLine()!=null){
    numLines++;
}
System.out.println("Number of lines readLines"+numLines);
return numLines;

}

public static int countInversions(int num[]){

int countLeft,countRight,countMerge;
int mid=num.length/2,k;


if (num.length<=1){

    return 0;// Number of inversions will be zero for an array of this size.
}

int left[]=new int[mid];
int right[]=new int [num.length-mid];


for (k=0;k<mid;k++){
    left[k]=num[k];
}

for (k=0;k<mid;k++){
    right[k]=num[mid+k];
}

countLeft=countInversions(left);
countRight=countInversions(right);

int[] result=new int[num.length];
countMerge=mergeAndCount(left,right,result);
/*
 * Assign it back to original array.
 */
for (k=0;k<num.length;k++){
    num[k]=result[k];
}

return(countLeft+countRight+countMerge);
}
private static int mergeAndCount(int left[],int right[],int result[]){
int count=0;
int a=0,b=0,i,k=0;
while((a<left.length)&&(b<right.length)){

    if(left[a]<right[b]){
        result[k]=left[a++];// No inversions in this case.

    }
    else{// There are inversions.

        result[k]=right[b++];
        count+=left.length-a;
    }
    k++;

    // When we finish iterating through a.

if(a==left.length){
    for (i=b;i<right.length;i++){
        result[k++]=right[b];

    }

    }
else{
    for (i=a;i<left.length;i++){

    }
}






}


return count;
  }
  }

我是Java和算法的初学者,所以任何富有洞察力的建议都会很棒!

Answer 1

我发现了两个错误:

• 在countInversions()中,何时num被拆分left并right假设right有m元素.num.length然而,当它是奇数时,它将是m + 1元素.解决方案是使用right.length而不是m.
• 在mergeAndCount()中,处理一个子数组为空而另一个仍然有一些元素的位未正确完成.

附注:除了方法(顺便说一下,返回一个方法)之外,
绝对没有理由Integer在你的程序中使用.Integer.parseInt()int

更正代码:

/**
*
*/

package com.JavaReference;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class ReadFile {

    public static void main(String args[]){
        int count=0;
        Integer n[];

        int i=0;
        try{
            n=OpenFile();
            int num[] = new int[n.length];

            for (i=0;i<n.length;i++){
                num[i]=n[i].intValue();
                // System.out.println( "Num"+num[i]);
            }
            count=countInversions(num);

        }
        catch(IOException e){
            e.printStackTrace();
        }

        System.out.println(" The number of inversions"+count);

    }

    public static Integer[] OpenFile()throws IOException{

        FileReader fr=new FileReader("C:/IntegerArray.txt");// to put in file name.

        BufferedReader textR= new BufferedReader(fr);
        int nLines=readLines();
        System.out.println("Number of lines"+nLines);

        Integer[] nData=new Integer[nLines];
        for (int i=0; i < nLines; i++) {
            nData[ i ] = Integer.parseInt((textR.readLine()));

        }
        textR.close();

        return nData;

    }

    public static int readLines() throws IOException{

        FileReader fr=new FileReader("C:/IntegerArray.txt");
        BufferedReader br=new BufferedReader(fr);

        int numLines=0;
        //String aLine;

        while(br.readLine()!=null){
            numLines++;
        }
        System.out.println("Number of lines readLines"+numLines);
        return numLines;

    }

    public static int countInversions(int num[]){

        int countLeft,countRight,countMerge;
        int mid=num.length/2,k;

        if (num.length<=1){

            return 0;// Number of inversions will be zero for an array of this size.
        }

        int left[]=new int[mid];
        int right[]=new int [num.length-mid];

        for (k=0;k<mid;k++){
            left[k]=num[k];
        }

        // BUG 1: you can't assume right.length == m
        for (k=0;k<right.length;k++){
            right[k]=num[mid+k];
        }

        countLeft=countInversions(left);
        countRight=countInversions(right);

        int[] result=new int[num.length];
        countMerge=mergeAndCount(left,right,result);
        /*
        * Assign it back to original array.
        */
        for (k=0;k<num.length;k++){
            num[k]=result[k];
        }

        return(countLeft+countRight+countMerge);
    }
    private static int mergeAndCount(int left[],int right[],int result[]){
        int count=0;
        int a=0,b=0,i,k=0;
        while((a<left.length)&&(b<right.length)){

            if(left[a]<right[b]){
                result[k]=left[a++];// No inversions in this case.

            }
            else{// There are inversions.

                result[k]=right[b++];
                count+=left.length-a;
            }
            k++;
        }

        // BUG 2: Merging of leftovers should be done like this
        while (a < left.length)
        {
            result[k++] = left[a++];
        }
        while (b < right.length)
        {
            result[k++] = right[b++];
        }

        return count;
    }
}