Mergesort Implementation ..计数阵列中的反转次数

Question

我正在参加算法的在线类，并尝试实现在数字列表中查找反转次数的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; 
    } 
} 

Answer 2

您可以尝试在Java中，这就地归并FPGA实现。但是最少需要1个临时数据容器（在这种情况下是ArrayList）。还计算倒数。

///

Sorter.java

public interface Sorter { 

    public void sort(Object[] data); 

    public void sort(Object[] data, int startIndex, int len); 

} 

MergeSorter实现类

MergeSorter.java

import java.util.List; 
import java.util.ArrayList; 

public class MergeSorter implements Sorter { 

    private List<Comparable> dataList; 
    int num_inversion; 

    public MergeSorter() { 
     dataList = new ArrayList<Comparable> (500); 
     num_inversion = 0; 
    } 

    public void sort(Object[] data) { 
     sort(data, 0, data.length); 
    } 

    public int counting() { 
     return num_inversion; 
    } 

    public void sort(Object[] data, int start, int len) { 
     if (len <= 1) return; 
     else { 
      int midlen = len/2; 

      sort(data, start, midlen); 
      sort(data, midlen + start, len - midlen); 
      merge(data, start, midlen, midlen + start, len - midlen); 
     } 
    } 

    private void merge(Object[] data, int start1, int len1, int start2, int len2) { 
     dataList.clear(); 

     int len = len1 + len2; 

     // X is left array pointer 
     // Y is right array pointer 

     int x = start1, y = start2; 
     int end1 = len1 + start1 - 1; 
     int end2 = len2 + start2 - 1; 

     while (x <= end1 && y <= end2) { 

      Comparable obj1 = (Comparable) data[x]; 
      Comparable obj2 = (Comparable) data[y]; 

      Comparable<?> smallobject = null; 
      if (obj1.compareTo(obj2) < 0) { 
       smallobject = obj1; 
       x++; 
      } 
      else { 
       smallobject = obj2; 
       y++; 
       num_inversion += (end1 - x + 1); 
      } 

      dataList.add(smallobject); 
     } 

     while (x <= end1) { 
      dataList.add((Comparable)data[x++]); 
     } 
     while (y <= end2) { 
      dataList.add((Comparable)data[y++]); 
     } 

     for (int n = start1, i = 0; n <= end2; n++, i++) { 
      data[n] = dataList.get(i); 
     } 

    } 
} 

（其他类似QuickSorter，BubbleSorter或InsertionSorter可以分拣机接口上实现）

对于测试，创建一个驱动程序类和类型主要方法

public static void main(String[] args) { 

    Object[] data = ............... 
    Sorter sorter = new MergeSorter(); 
    sorter.sort(data) 

    for (Object x : data) { 
     System.out.println(x); 
    } 
    System.out.println("Counting invertion: " + ((MergeSorter)sorter).counting()); 
} 

Answer 3

我看到它的方式，计算数组中的反转次数是找到一种方法来按升序对数组进行排序。下面这个想法，这里是我的解决方案：

int countInversionArray(int[] A) { 
    if(A.length<=1) return 0; 
    int solution = 0; 

    for(int i=1;i<A.length;i++){ 
     int j = i; 
     while(j+2<A.length && A[j] > A[j+1]){ 
      invert2(j,j+1,A); 
      solution++; 
      j++; 
     } 
     j=i; 
     while(j>0 && A[j] < A[j-1]){ 
      invert2(j,j-1,A); 
      solution++; 
      j--; 
     } 
    } 

    return solution; 
} 

private void invert2(int index1, int index2, int[] A){ 
    int temp = A[index1]; 
    A[index1] = A[index2]; 
    A[index2] = temp; 
} 

Answer 4

我发现罗伯特·塞奇威克书

1. 阅读 “在Java语言算法” 一分辩解决方案here about merge
2. 见java code for counting of inversion