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

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

当我在main方法中运行这个程序时，我得到了原始数组的打印。不知道是什么问题。当我单独测试时，合并方法可以工作。

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,

我花了很多时间寻找这个问题。

Answer 1

答案如@Mysticial所说，除了需要在merge方法中复制数组:

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] + ",");
    }
}

希望这对你有帮助!

Answer 2

这个问题实际上相当复杂。

主要的问题是，你只是合并到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,