为什么这个归并排序实现不起作用？

Question

以下是我实现的归并排序。

private static void mergeSort(int[] a, int low , int high,int[] res)
{
    int mid = (low + high)  /2;
    if (low  < high)
    {
        mergeSort(a,low,mid-1,res);
        mergeSort(a,mid,high-1,res);
        merge(a,low,mid,high,res);

    }
}



   private static void merge(int[] a, int low , int mid , int high,int[] res)
{

    int i = low;
    int j = mid ;

    int k =0;

    while (i < mid && j < high)
        if(a[i] < a[j])
               res[k++] = a[i++];
        else
              res[k++] = a[j++];


    while(i < mid)
        res[k++] = a[i++];

    while(j < high)
        res[k++] =a[j++];
}

当我在主方法中运行此程序时，我会得到原始数组的打印。不确定问题出在哪里。当我单独测试合并方法时，它是有效的。

public static void main(String[] args)
{
    int[] a = {45,24,53,13,54,45,63,23};
    int[] res = new int[a.length];
    mergeSort(a,0,a.length,res);
    for(int i=0 ; i < res.length ; i++)
    {
       System.out.print(res[i] +",");
    }
}

输出：

 45,24,53,13,54,45,63,23,

我花了很多时间寻找问题，但是无法解决它。

- user2434

Answer 1

问题实际上相当复杂。

主要问题在于您只合并到res，但从未再次使用它。因此，您最终会在每个递归级别上将其覆盖。

这是一个修补过的版本，可以在a和res之间来回合并。它确实会破坏a的内容，因此可能不是您想要的。

private static void mergeSort(int[] a, int low , int high,int[] res)
{
    int mid = (low + high)  /2;
    if (low + 1 < high)
    {
        //  Sort sub-parts
        mergeSort(a,low,mid,res);
        mergeSort(a,mid,high,res);

        //  Copy back to "a"
        for (int c = low; c < high; c++){
            a[c] = res[c];
        }

        //  Merge back to "res"
        merge(a,low,mid,high,res);
    }else{
        res[low] = a[low];
    }
}

private static void merge(int[] a, int low , int mid , int high,int[] res)
{

    int i = low;
    int j = mid;

    int k = low;   //  Use "low" instead of 0.

    while (i < mid && j < high)
        if(a[i] < a[j])
               res[k++] = a[i++];
        else
              res[k++] = a[j++];


    while(i < mid)
        res[k++] = a[i++];

    while(j < high)
        res[k++] =a[j++];
}

输出：

13,23,24,45,45,53,54,63,

- Mysticial

---

如果我改变递归调用，就会在“main”线程中出现异常java.lang.StackOverflowError :( - user2434

嗯...程序在其他地方出了问题。当我运行这个程序时，输出结果是0,0,0,0,54,45,63,23。 - user2434

很奇怪，我正在测试它，看起来对我来说没问题：13,23,24,45,45,53,54,63, - Mysticial

你是否进行了这个更改：int k = low;？如果你将它保留为零，你会得到0,0,0,0,54,45,63,23,。 - Mysticial

如果使用 low < high，由于无限递归，它将导致堆栈溢出。 - Mysticial

Answer 2

答案就像 @Mysticial 所说的那样，唯一的例外是数组需要在合并方法内部进行复制：

private static void mergeSort(int[] a, int low , int high,int[] res)
{
    int mid = (low + high)  /2;
    if (low + 1 < high)
    {
        //  Sort sub-parts
        mergeSort(a,low,mid,res);
        mergeSort(a,mid,high,res);

        //  Merge back to "res"
        merge(a,low,mid,high,res);
    }else{
        res[low] = a[low];
    }
}

private static void merge(int[] a, int low , int mid , int high,int[] res)
{

    int i = low;
    int j = mid;

    int k = low;   //  Use "low" instead of 0.

    while (i < mid && j < high)
        if(a[i] < a[j])
               res[k++] = a[i++];
        else
              res[k++] = a[j++];


    while(i < mid)
        res[k++] = a[i++];

    while(j < high)
        res[k++] =a[j++];

    //  Copy back to "a"
        for (int c = low; c < high; c++){
            a[c] = res[c];
        }

}

无论如何，需要注意的是这样做将覆盖原始数组...因此您可能希望包装对mergeSort的调用以避免它：

private static int[] mergeSort(int[] a){
    int[] b = new int[a.length];
    int[] tmp = new int[a.length];
    System.arraycopy(a, 0, b, 0, a.length);
    mergeSort(b, 0, b.length, tmp);
    return b;
}

public static void main(String[] args) {
    int[] a = {45, 24, 53, 13, 54, 45, 63, 23};
    int[] res = mergeSort(a);
    for (int i = 0; i < res.length; i++) {
        System.out.print(res[i] + ",");
    }
}

希望这能帮到你！

- Federico Vera