5

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

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];
        }
    }
}
4

2 回答 2

3

这是 mergeSort 方法的伪代码。我看到您忽略了一个或两个要素的基本情况：

if (sublist has only one value)
   do nothing
else if (sublist has two values)
   switch if necessary
else    // recursion, divide list into two halves
   Find midpoint of current sublist
   Call mergeSort and process left sublist
   Call mergeSort and process right sublist
   merge left and right sublists

至于您的合并方法，它是创建一个新数组而不是修改现有数组。我建议使用 ArrayLists 来实现它：

private void merge(int[] a, int first, int mid, int last)
  {
    ArrayList<Integer> left = new ArrayList<Integer>(mid - first + 1), right = new ArrayList<Integer>(last - mid);
    for(int m = first; m <= mid; ++m)   //initialize left sublist
    {
      left.add(a[m]);
    }
    for(int m = mid + 1; m <= last; ++m)    //initialize right sublist
    {
      right.add(a[m]);
    }
    int i = first;
    while(!left.isEmpty() || !right.isEmpty())  //while either list has an element
    {
      if(left.isEmpty())
      {
        a[i++] = right.remove(0);
      }
      else if(right.isEmpty())
      {
        a[i++] = left.remove(0);
      }
      else if (left.get(0) < right.get(0))
      {
        a[i++] = left.remove(0);
      }
      else
      {
        a[i++] = right.remove(0);
      }
    }
  }
于 2013-03-12T19:47:30.767 回答
1

好的，我修复了您的解决方案。您的主要问题是在线标记为//<= here。当mid运行结束索引时，您没有从ato分配值，d因此它被填充0. 您必须替换==为>=才能解决此问题。
我还用索引修复了你的工作。您不必在每个级别上运行整个阵列。您的复杂性也会以这种方式受到影响。我认为它大约O(n^2)。只运行在此递归级别上处理的数组的一部分以保持O(nlog(n))复杂性就足够了。

固定算法如下

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];
    }
}
于 2013-03-12T21:21:56.257 回答