java - 递归合并排序 - 堆栈溢出错误

Question

我正在做一个学校项目，我必须编写一个执行合并排序的程序。 mergeSort() 方法是递归的，会导致堆栈溢出错误。我知道如果递归方法无休止地继续，就会发生这种情况，但我无法弄清楚我的代码中是什么让它不停下来。

如有任何帮助，我们将不胜感激。

这是代码(它使用我的教授提供的 Sort.java 程序运行，如果这说明为什么没有 main 方法):

public class Merge {

    /**
     * Sort an array, in-place, using merging.
     * @param array The array to be sorted.
     * POSTCONDITION: The elements of array are in ascending order.
     */
    public static void sort(int[] array) {

        int[] tempArray = mergeSort(array);
        for (int i = 0; i < tempArray.length; i++) {
            array[i] = tempArray[i];
        }
    }

    /**
     * Extract the portion of an array from start up to (excluding) stop.
     * @param array The source array.
     * @param start The starting index (inclusive).
     * @param stop  The ending index (exclusive).
     * @return An array containing the same elements the portion of array.
     * PRECONDITION: 0 <= start <= stop <= array.length
     */
    private static int[] subarray(int[] array, int start, int stop) {

        int[] newArray = new int[stop-start];
        for (int i = 0; i < newArray.length; i++) {
            newArray[i] = array[start + i];
        }
        return newArray;
    }

    /**
     * Merge two sorted arrays into one new array.
     * @param first The first array, already sorted.
     * @param second The second array, already sorted.
     * @return A new array containing the elements of first and second,
     *         in order.
     */
    private static int[] merge(int[] first, int[] second) {

        int[] newArray = new int[first.length + second.length]; 
        int count = 0;
        int i = 0;
        int j = 0;
        while ((i < first.length) || (j < second.length)) {
            if ((i < first.length) && (j < second.length)) {
                if (first[i] < second[j]) {
                    newArray[count++] = first[i++];
                } else { 
                    newArray[count++] = second[j++];
                }
            } else if (j < second.length) {
                newArray[count++] = second[j++]; 
            } else if (i < first.length) { 
                newArray[count++] = first[i++];
            }
        }
        return newArray;
    }

    /**
     * Sort an array by merging.
     * @param array The array to sort.
     * @return A new array containing the elements of array, in order.
     */
    private static int[] mergeSort(int[] array) {
        int split = 0;
        if (array.length < 2) {
            return array;
        } else {
            split = array.length%2;
            int[] array1 = mergeSort(subarray(array, 0, split));
            int[] array2 = mergeSort(subarray(array, split, array.length));
            return merge(array1, array2);
        }
    }  
}

Answer 1

我假设 split = array.length%2; 应该是 split = array.length/2;

如果数组的长度是偶数，这将需要一段时间，因为第二个子数组实际上将等于原始数组，并且您会得到无限递归。对于奇数长度的数组，第二个子数组将是偶数长度，并且您再次获得无限递归。

---

要调试无限递归，首先使用 printf 语句检查正在发生的事情就在递归之前(因为这可能是出错的地方)以确保递归按计划进行，例如:

split = array.length%2;
System.err.printf(
    "%d broken into %d (%d to just before %d) and %d (%d to just before %d).\n",
    array.length, split, 0, split, array.length - split, split, array.length);
int[] array1 = mergeSort(subarray(array, 0, split));
int[] array2 = mergeSort(subarray(array, split, array.length));
return merge(array1, array2);

看看事情是否以它们应该的方式变小了。