我正在上一门关于算法的在线类(class)，并尝试实现一个合并排序实现，以查找数字列表中的反转次数。但是，我不知道我的实现有什么问题，因为返回的反转次数明显低于我在使用蛮力方法时得到的次数。我将合并排序方法的实现放在下面
/**
*
*/
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 和算法的初学者，所以任何有见地的建议都会很棒!
最佳答案
我发现了两个错误:
- 在 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;
}
}
关于java - Mergesort 实现.. 计算数组中的反转次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9765567/