java - 错过的函数调用导致堆栈溢出

Question

很抱歉，如果这是在其他地方发布的(我找不到任何东西，因为我的问题相当具体)，但我明白(或至少在理论上)错误是什么；我在如何修复它时遇到了麻烦。该代码应该显示合并排序的工作原理；代码运行，但它永远不会调用函数调用“merge”(下面的代码，我知道在导入中调用所有内容是不好的做法，但这不是一个主要项目，所以我不在乎；也许它是只是预览，但它是写 import java.util.; 和 import java.security.;).

import java.util.*;
import java.security.*;

public class Merge {
    public static void mergeSort(int[] data) {
        sortArray(data, 0, data.length - 1);
    }

    private static void sortArray(int[] data, int low, int high) {
        if ((high - low) >= 1) {
            int m1 = low + high;
            int m2 = m1 + 1;

            System.out.printf("Split:  %s\n", subarrayString(data, low, high));
            System.out.printf("          %s\n", subarrayString(data, low, m1));
            System.out.printf("          %s\n\n", subarrayString(data, m2, high));

            sortArray(data, low, m1);
            sortArray(data, m2, high);

            merge(data, low, m1, m2, high);
        }
    }

    public static void merge(int[] data, int l, int m1, int m2, int r) {
        int lIndex = l, rIndex = r, cIndex = l, combined[] = new int[data.length];

        System.out.printf("Merge:  %s\n", subarrayString(data, l, m1));
        System.out.printf("             %s\n", subarrayString(data, m1, r));

        while (lIndex <= data[rIndex]) {
            if (data[lIndex] <= data[rIndex])
                combined[cIndex++] = data[lIndex++];
            else
                combined[cIndex++] = data[rIndex++];
        }

        if (lIndex == m2)
            while (rIndex <= r) combined[cIndex++] = data[rIndex++];
        else
            while (lIndex <= m1) combined[cIndex++] = data[rIndex++];
    }

    private static String subarrayString(int[] data, int low, int high) {
        StringBuilder temp = new StringBuilder();

        for (int i = 0; i < low; i++)
            temp.append("     ");

        for (int i = 0; i < high; i++)
            temp.append(" " + data[i]);

        return temp.toString();
    }

    public static void main2() {
        SecureRandom gen = new SecureRandom();

        int[] data = new int[10];

        for (int i = 0; i < data.length; i++) data[i] = 10 + gen.nextInt(50);

        System.out.printf("\nUnsorted Array:\n%s\n\n", Arrays.toString(data));
        mergeSort(data);
        System.out.printf("\nSorted Array:\n%s\n\n", Arrays.toString(data));
    }
}

如果您需要驱动程序文件，请告诉我。重申一下，问题是它永远不会到达合并函数调用并导致堆栈溢出错误。

Answer 1

堆栈溢出的常见原因是错误的递归调用。通常，这是在您的递归函数没有正确的终止条件时引起的。在您的代码中，第一个递归调用始终使用相同的参数 0 和 (length - 1) 调用并且没有终止，它将陷入无限循环。修复您的代码并更新 m1 的值，使其终止。

考虑数组长度为 6:

low = 0 and high = 5
 m1 = 5
sortArray(data, 0, 5);