使用 Java 进行合并排序，合并步骤中的行为令人困惑

Question

当我尝试用java进行合并排序算法时，算法中还出现了一些不清楚的行为。

• 该算法工作正常，没有问题，我来这里是为了获得一些有关该算法的澄清，该算法的表现不符合我的预期。

• 这是相同的合并排序算法，唯一的区别是我使用java的“BigInteger”类型来解决我的特定问题。因此该算法是基于 biginteger 类型进行排序的，因此存在一些小的额外步骤......

首先让我们检查一下我写的代码。

import java.math.BigInteger;
import java.util.Arrays;
import java.util.List;

public class MergeSorter {
    public BigInteger[] Merge_Sort(BigInteger[] Arr, int start,  int end){
        if(start<end){
            int mid = (start+end)/2;
            Merge_Sort(Arr, start, mid);
            Merge_Sort(Arr, mid+1, end);
            Merge(Arr, start,mid, end);
        }
        return Arr;
    }

    public void Merge(BigInteger[] Arr, int start, int mid, int end){
        int n1 = mid - start+1;
        int n2 = end - mid;

        BigInteger[] left = new BigInteger[n1+1];
        BigInteger[] right = new BigInteger[n2+1];

        for(int i=0; i<n1; i++){
            left[i] = Arr[start+i-1];
        }

        for(int j=0; j<n2; j++){
            right[j] = Arr[mid+j];
        }

        left[n1] =  null;
        right[n2] = null;

        int i=0;
        int j=0;
        for(int k=start-1;k<end; k++ ){
            if(left[i]!=null && right[j]!=null){
                if((left[i].compareTo(right[j])==-1)
                        ||(left[i].compareTo(right[j])==0)){
                    Arr[k] = left[i];
                    i++;
                }else{
                    Arr[k] = right[j];
                    j++;
                }
            }else if(right[j]!=null){
                Arr[k] = right[j];
                j++;
            }else if(left[i]!=null){
                Arr[k] = left[i];
                i++;
            }else{
                break;
            }
        }
    }
}

什么让我脑子沸腾？ （如何以及问题是什么）

在合并步骤中，“Merge(Arr, start,mid, end);”我们使用递归来运行、开始、中间和结束变量值，但是，这里发生了类似“神奇”的事情，也就是说， 数组如何在不返回的情况下进行排序，或者我是否缺少一些有关递归的更多知识？...

这就是我被困住的地方......

我尝试了一些简单的方法来暴露行为，如下所示：

public void printer(int inc, int start, int mid, int end){
    inc++;
    System.out.println("inc: "+inc);
    System.out.println("Merge Step Runs with: "+"Start: "+start+" mid: "+mid+" end: "+end);
}

public void Merge_Sort(int inc, int start,  int end){
    if(start<end){
        int mid = (start+end)/2;
        Merge_Sort( inc,start, mid);
        Merge_Sort( inc,mid+1, end);

        printer( inc,start, mid, end);
    }

}

事情不会相加，inc不会像合并排序中的数组那样被替换。

希望收到您的来信，以获取更多参考资料，以便更好地阅读（如果有任何与此背景相关的内容）。

Answer 1

数组如何在不返回的情况下进行排序

参数

arr

是对数组的引用，因此当

Merge

写入 arr (

arr[...] = ...

) 时，它会更新原始数组。