归并排序的问题

Question

我正在为我的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];
        }
    }
}

- user1943221

---

你尝试过在调试器中逐步执行代码，看看它似乎出了什么问题吗？ - millimoose

Answer 1

这里是归并排序方法的伪代码。我看到你已经忽略了只有一个或两个元素的基本情况：

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);
      }
    }
  }

- gparyani

---

+1 鼓励任何愿意深入实现归并排序的人。 - Philip Tenn

谢谢，我修改了我的mergeSort方法以适应您的伪代码和合并方法，但是当我运行它时，会出现堆栈溢出错误。我忘了提到我们不能使用ArrayList，但我可以进行修改。 - user1943221

Answer 2

好的，我已经修复了你的解决方案。你的主要问题在标有//<= here的行上。当mid超过结束索引时，你没有将a到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];
    }
}

- Ondrej Bozek

---

非常感谢。运行得非常完美。一旦我开始以调试模式运行它，我意识到我遍历了整个数组，但不确定应该在哪些值处停止。 - user1943221

我可以问一下，在标记为//<=的那一行为什么很重要吗？我使用了==，因为我认为如果mid等于end，那么数组的那一半已经排序好了，并且需要复制beg-middle之间的值。 - user1943221

如果你到达了数组的上限 (mid==end)，你需要将值从a复制到d并增加mid (mid++)(现在mid==end+1)。但是，如果下半部分的数字比上半部分大，你不能停在这里，你还必须复制它。也许如果有(mid==end+1)而不是(mid>=end)会更准确。 - Ondrej Bozek