java - mergeSort - Java 中的破坏性与非破坏性

Question

有人可以向我解释一下实现 mergeSort 算法的非破坏性函数与此函数/mergeSort 算法的破坏性实现之间的区别吗？

public class MergeSort{

    public static int[] merge(int[] A, int[] B){
        System.out.println("merge: |A|="+A.length+", |B|="+B.length);
        for(int i=0; i<A.length; i+=1) System.out.print(A[i] + ",");
        System.out.println();
        for(int i=0; i<B.length; i+=1) System.out.print(B[i] + ",");
        System.out.println();

        int [] C = new int[ A.length + B.length ];
        int a = 0, b = 0;
        for( int c = 0; c < C.length; c+=1 ){
            if (a == A.length ){
                C[c] = B[b];
                b+=1;
            }else if (b == B.length ){
                C[c] = A[a];
                a+=1;
            }else{
                if (A[a] < B[b]){
                    C[c] = A[a];
                    a+=1;
                }else{
                    C[c] = B[b];
                    b+=1;
                }
            }
        }
        for(int i=0;i<C.length;i+=1) System.out.print(C[i] + ",");
        System.out.println();
        return C;
    }

    public static int[] mergeSort(int[] M){
        System.out.println("mergesort : |M|="+M.length);
        for(int i=0; i<M.length; i+=1) System.out.print(M[i] + ",");
        System.out.println();

        if (M.length ==1){
            int [] C = new int[1]; 
            C[0] = M[0];
            return C;
        }

        int[] A = new int[ M.length/2 ];
        System.arraycopy(M,0,A,0,M.length/2);
        int[] AA = mergeSort(A);
        int[] B = new int[ M.length - M.length/2 ];
        System.arraycopy(M,M.length/2,B, 0, M.length - M.length/2);
        int[] BB = mergeSort(B);

        return merge(AA,BB); 

    }// mergeSort

}

如上所述，我知道这个函数返回输入数组的“副本”(非解构性)。如何将其更改为破坏性函数，换句话说，输入数组本身发生变异，而不是生成副本。

Answer 1

你可以很容易地覆盖原始数组中的值，假设你的 mergeSort() 方法执行了它应该做的事情，这样的事情就可以很好地工作。

public void overwritingMergeSort(int[] M) {
    int[] sorted = mergeSort(M);
    for(int i = 0; i < sorted.length; i++) {
        M[i] = sorted[i];
    }
}

int[] arr = new int[]{2,5,1,4,3};
System.out.println(Arrays.toString(arr));
overwritingMergeSort(arr);
System.out.println(Arrays.toString(arr));

打印:

[2,5,1,4,3]
[1,2,3,4,5]