java - Java 合并排序算法的问题

Question

我在使用这个合并排序算法时遇到了问题。我总共有 3 个方法来进行合并排序，加上调用它的 main 方法。它没有输出排序的数组，我不确定我哪里出错了。当我查看它时，这一切在我看来都是正确的，我不确定错误是否在方法的递归部分中，或者是否仅在其中一个类中。任何帮助将不胜感激，谢谢!这是我的代码:

/**
 * To do: Implement merge sort.
 * @param array the array to sort
 * @return the sorted array
 */
public static int[] mergeSort(int[] array) {
    // call mergeSort(int [], int, int) to initiate sorting
    //throw new UnsupportedOperationException()
    return mergeSort(array, 0, array.length-1);
}

/**
 * To do: Implement overloaded merge sort method.
 * @param array the array to sort
 * @param begin the starting index of the array to be sorted
 * @param end the last index of the array to be sorted
 */
private static int[] mergeSort(int[] array, int begin, int end) {
    // you need to write the merge sort algorithm here
    // use this method mergeSort(int [], int, int) and merge(int [], int[])
    // to complete it
    //throw new UnsupportedOperationException();


    if(begin < end) {
        int [] left = new int[array.length/2];
        int [] right = new int[array.length - left.length];

        //copies first half of array into left
        for(int i = 0; i < left.length; i++) {
            left[i] = array[i];
        }
        //copies second half into right array
        for(int j = 0; j < right.length; j++) {
            right[j] = array[left.length + j];
        }

        mergeSort(left);
        mergeSort(right);
        return merge(left, right);
    }
    return array;
}


/**
 * To do: Merge two sorted arrays into one and return it
 * @param left the first array
 * @param right the second array
 * @return the sorted merged array
 */
private static int[] merge(int[] left, int[] right) {
    // merge two sorted array such way that it remains sorted
    //throw new UnsupportedOperationException();
    int [] sorted = new int[left.length + right.length];

    int leftIndex = 0;
    int rightIndex = 0;

    for(int j = 0; j < sorted.length; j++ ) {
        if( leftIndex <= left.length-1 && rightIndex <= right.length-1) {

            if(left[leftIndex] < right[rightIndex]) {
                sorted[j] = left[leftIndex];
                leftIndex++;
            }
            else {
                sorted[j] = right[rightIndex];
                rightIndex++;
            }
        }
        else if( leftIndex < left.length) {
            sorted[j] = left[leftIndex];
            leftIndex++;
        }
        else if(rightIndex< right.length) {
            sorted[j] = right[rightIndex];
            rightIndex++;
        }
    }

    return sorted;
}

Answer 1

您的 mergeSort 函数不是就地的，即它返回一个新数组，而不是更改同一数组中元素的顺序。因此，这两行:

            mergeSort(left);
            mergeSort(right);

绝对不会有任何影响。

将其更改为:

            left = mergeSort(left);
            right = mergeSort(right);

另一条评论:尽管您的合并排序是O(NlogN)，但您仍使用大量复制数组，这会产生大量开销。尽量使用就地操作，避免创建额外的数组。大多数情况下，合并排序在任何时候使用的数组不超过 2 个。