合并排序有问题 [英] Trouble with Merge Sort

问题描述

对于我的java作业，我正在努力编写一个递归合并排序类。截至目前，我有3个方法，一个驱动方法来启动递归，递归 mergeSort 方法和一个合并方法。根据我更改的变量，我的输出是一个全零的数组或我的原始数组以相同的顺序。唯一的原因是原始的 mergeSort 方法必须接受一个数组而 merge 方法不能返回任何内容。非常感谢任何帮助

For my java homework I am struggling to write a recursive merge sort class. As of right now I have 3 method a "driver" method to start the recursion, the recursive mergeSort method and a merge method. Depending on what variables I change my output is either an array of all zeros or my original array in the same order. The only thing is the original mergeSort method must take in one array and the merge method cannot return anything. Any help with be much appreciated

import java.util.Arrays;
public class merge2 {
    public static void main(String[] args){
        int []a={22,45,1,4,89,7,0};
        mergeSort(a);
        System.out.println(Arrays.toString(a));                 
    }

    public static void mergeSort(int [] a){
        mergeSort(a,0,a.length-1);
    }

    public static void mergeSort(int []a, int beg,int end){
        if(beg<end){
            int mid=(beg+end)/2;
            mergeSort(a,beg,mid);
            mergeSort(a,mid+1,end);
            merge(a,beg,mid,end);
        }
    }

    private static void merge(int []a, int beg, int middle, int end){
        int [] d=new int[a.length];
        int mid=middle+1; //start of second half of array
        for(int i=0;i<d.length;i++){
            if(beg<=middle && mid<=end){  
                if(a[beg]<=a[mid]) {
                d[i]=a[beg];
                beg++;
                } else if(a[mid]<=a[beg]){
                        d[i]=a[mid];
                        mid++;
                }
            }else if(beg>middle){ 
                d[i]=a[mid];
                mid++;
            }else if(mid==a.length){
                d[i]=a[beg];
                beg++;
            }
        }
        for(int w=0;w<d.length;w++){
            a[w]=d[w];
        }
    }
}

推荐答案

好的我修复了你的解决方案。您的主要问题是在标有 //< = here 的行上。当 mid 运行结束索引时，您没有将值从 a 分配给 d 所以它留满了 0 。您必须使用> = 替换 == 才能解决此问题。

我也是用索引修复你的工作。您不必在每个级别上运行整个数组。你的复杂性也会受到这种影响。我认为它约为 O（n ^ 2）。只运行在此递归级别处理的数组的一部分就足以与 O（nlog（n））复杂性保持一致。

Ok I fixed your solution. Your main problem was on line marked with //<= here. When mid run over end index you were not assigning values from a to d so it was left filled with 0. You had to replace == with >= to overcome this issue.
I also fixed your work with indexes. You don't have to run over whole array on each level. Also your complexity suffers this way. I think its about O(n^2). It's enough to run only over part of array which is processed on this recursion level to keep with O(nlog(n)) complexity.

固定算法如下

public static void main(String[] args){
    int []a={22,45,1,4,89,7,0};
    mergeSort(a);
    System.out.println(Arrays.toString(a));

}

public static void mergeSort(int [] a){
    mergeSort(a,0,a.length-1);
}

public static void mergeSort(int []a, int beg,int end){
    if(beg<end){
        int mid=(beg+end)/2;
        mergeSort(a,beg,mid);
        mergeSort(a,mid+1,end);
        merge(a,beg,mid,end);
    }
}

private static void merge(int []a, int beg, int middle, int end){
    int [] d=new int[a.length];
    int mid=middle+1; //start of second half of array
    int beg1=beg;
    for(int i=beg1;i<=end;i++){
        if(beg<=middle && mid<=end){  
            if(a[beg]<=a[mid]) {
            d[i]=a[beg];
            beg++;
            } else if(a[mid]<=a[beg]){
                    d[i]=a[mid];
                    mid++;
            }
        }else if(beg>middle){         
            d[i]=a[mid];
            mid++;
        }else if(mid>=end){ //<= here
            d[i]=a[beg];
            beg++;
        }
    }
    for(int w=beg1;w<=end;w++){
        a[w]=d[w];
    }
}

这篇关于合并排序有问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！