合并排序算法

Question

我一直在解决与归并排序相关的问题，但不知道我的程序有什么问题，请您看一下？

问题是给出一个未排序的数组，它会在不改变原始数组的情况下提供排序。请让我知道我的错误在哪里

public static int []  mergeSort(int[] in){

        int [] temp = in.clone();

        if (temp.length <= 1){

            }


        else{
            int [] first = new int[temp.length/2];
            int [] second = new int [temp.length - first.length];

            for (int i=0; i<first.length; i++){
                first[i] = temp[i];
            }

            for (int i = 0; i < second.length; i++){
                second[i] = temp[first.length+i];
            }

            mergeSort(first);
            mergeSort(second);
            merg(first,second,temp);

        }

    return temp;
    }
    public static void merg(int [] first, int[] second, int []newTemp){


        int i =0;
        int j = 0;
        int k = 0;
        while(i <first.length && j < second.length ){

            if(first[i] <=second[j]){

                newTemp[k] = first[i];
                i++;
            }
            else{
                newTemp[k] = second[j];
                j++;

            }
            k++;

        }
        while (i < first.length){
            newTemp[k] = first[i];
            i++;
            k++;
        }
        while(j < second.length){
            newTemp[k]= second[j];
            j++;
            k++;
        }

    }

Answer 1

问题是因为您正在克隆数组，并且每次调用 mergeSort() 函数时，它都会再次克隆数组。只有在第一次调用函数时才需要克隆它。

这是针对您的问题的完整解决方案。您应该调用第一个 mergeSort() 函数。

public static int[] mergeSort(int[] in) {
    return mergeSort(in, 0);
}

public static int[] mergeSort(int[] in, int number_of_times_called) {

    int[] temp;
    if (number_of_times_called == 0)
        temp = in.clone();
    else
        temp = in

    if (temp.length <= 1){
        return temp;
    }


    else{
        int [] first = new int[temp.length/2];
        int [] second = new int [temp.length - first.length];

        for (int i=0; i<first.length; i++){
            first[i] = temp[i];
        }

        for (int i = 0; i < second.length; i++){
            second[i] = temp[first.length+i];
        }

        mergeSort(first);
        mergeSort(second);
        merg(first,second,temp);

    }

    return temp;
}

public static void merg(int [] first, int[] second, int []newTemp){


    int i =0;
    int j = 0;
    int k = 0;
    while(i <first.length && j < second.length ){

        if(first[i] <=second[j]){

            newTemp[k] = first[i];
            i++;
        }
        else{
            newTemp[k] = second[j];
            j++;

        }
        k++;

    }
    while (i < first.length){
        newTemp[k] = first[i];
        i++;
        k++;
    }
    while(j < second.length){
        newTemp[k]= second[j];
        j++;
        k++;
    }

}

合并排序算法

Merge Sorting Algorithms

java

sorting

algorithm

mergesort