使用应该相同的变量时的两个不同答案（mergeSort）

Question

我有点困惑，正在寻找一些说明，所以我正在研究数据结构和算法，并且正在研究归并排序。本质上我想 return 排序列表并打印它以测试我是否正确实现了代码，但是我决定不将数据复制回原始数组而是 return 临时数组。我注意到当我最后 return temp 时，我会得到一个不同的答案，而不是在复制回来后 returned 原始数组（名为 a）。想知道是否有人可以解释为什么会这样。谢谢！下面是正确打印的代码，如果您在合并方法中将 return 更改为 temp，您会注意到列表停止正确排序

public class mergeSort {

public static void main(String[] args) {

    int[] a = new int[10];

    for(int i = 0; i < a.length; i++) {

        a[i] = (int)(Math.random()*30+1);
        System.out.println(i + ": " + a[i]);
    }

    mergeSort(a);
}

public static void  mergeSort(int[] a) {


    int[] temp = new int[a.length];

    a = mergeSort(a, 0, a.length, temp);

    for(int i = 0; i < a.length; i++){

        System.out.println(a[i]);
    }

}

public static int[] mergeSort(int[] a, int start, int end, int[] temp) {

    int mid;


    //Recursive method
    if(1 < end-start) {

        mid = start + (end-start)/2;
        mergeSort(a, start, mid, temp);
        mergeSort(a, mid, end, temp);
        a = merge(a, start, mid, end, temp);
    }

    return a;


}

public static int[] merge(int[] a, int start, int mid, int end, int[] temp) {


    int currL = start;
    int currR = mid;
    int currT;

    for(currT = start; currT < end; currT++) {

        if(currL < mid && (currR >= end || a[currL] < a[currR])) {

            temp[currT] = a[currL];
            currL++;
        }

        else{

            temp[currT] = a[currR];
            currR++;
        }

    }

    for(currT = start; currT < end; currT++) {
        a[currT] = temp[currT];
    }

    return a;

} 
}

Answer 1

考虑：

mergeSort(a, 0, 10, temp);

它调用：

mergeSort(a, 0, 5, temp);
mergeSort(a, 5, 10, temp);
a = merge(a, 0, 5, 10, temp);

mergeSort(a, 0, 5, temp)returns后，子数组a[0]到a[5]必须排序，mergeSort(a, 5, 10, temp)returns后，子数组 a[5] 到 a[10] 必须排序。

如果 merge 不修改原始数组 a 就不会发生这种情况。

请注意，赋值 a = merge(a, start, mid, end, temp); 不会更改传递给 mergeSort 方法的原始数组。因此 merge 本身必须通过将数据从 temp 数组复制回 a.

来修改传递给它的数组 a

编辑：

顺便说一句，请注意 merge return 是什么并不重要，只要它将合并后的元素从 temp 数组复制回 a数组。

您可以将其 return 类型更改为 void，排序仍然有效：

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

public static void merge(int[] a, int start, int mid, int end, int[] temp) {
    int currL = start;
    int currR = mid;
    int currT;

    for(currT = start; currT < end; currT++) {
        if(currL < mid && (currR >= end || a[currL] < a[currR])) {
            temp[currT] = a[currL];
            currL++;
        } else {
            temp[currT] = a[currR];
            currR++;
        }
    }
    for(currT = start; currT < end; currT++) {
        a[currT] = temp[currT];
    } 
}

使用应该相同的变量时的两个不同答案（mergeSort）

Two different answers when using variables that should be the same (mergeSort)

java

arrays

sorting

recursion

mergesort