Top Down递归方法不起作用，不确定如何解决。 Java

Question

我的“数据结构和算法类”有作业问题-在Java中实现自上而下的递归合并排序。通过生成一个由100个数字组成的随机序列，以原始的未排序形式打印它们，对它们进行排序，然后按照它们的排序顺序将它们打印出来，来证明您的排序有效。

并且我做了一些编码，这似乎是正确的，但是我遇到了一个错误，无法弄清楚我做错了什么。

class RecursiveMergeSort
{
void TopDownMergeSort(int[] mainArray, int[] copyArray) // mainArray, copyArray, int n
{
    CopyArray(mainArray, copyArray);
    Split(copyArray, 0, 100, mainArray);
}

private void Split(int[] copyArray, int start, int end, int[] mainArray)
{
    if(end - start < 2)
    {
        return;
    }
    int middle = (end + start) / 2;
    Split(mainArray, start, middle, copyArray);
    Split(mainArray, start, end, copyArray);
    CombineArray(copyArray, start, middle, end, mainArray);
}

private void CombineArray(int[] mainArray, int start, int middle, int end, int[] copyArray)
{
    int s = start; //a
    int m = middle; //b

    for (int i = start; i < end; i++)
    {
        if(s < middle && (m >= end || mainArray[s] <= mainArray[m]))
        {
            copyArray[i] = mainArray[s];
            s = s + 1;
        }
        else
        {
            copyArray[i] = mainArray [m];
                    m = m + 1;
        }
    }

}

private void CopyArray(int[] mainArray, int[] copyArray)
{
    System.arraycopy(mainArray, 0, copyArray, 0, 100);
}

void UnsortedArray(int[] unsortedArray)
{
    for(int i = 0; i < unsortedArray.length; i++)
    {
        int random = (int)Math.floor(Math.random() * 100) + 1;
        unsortedArray[i] = random;
        System.out.println("\t" + i + unsortedArray[i]);
    }
}

void SortedArray(int[] unsortedArray)
{
    for(int i = 0; i < unsortedArray.length; i++)
    {
        System.out.println("\t: " + i + unsortedArray[i]);
    }
}
}

这里是驱动程序：

public class RecursiveDriver
{
public static void main(String[] args)
{
    int[] randomNumbers = new int[100];
    int[] sorted = new int[100];


    RecursiveMergeSort test = new RecursiveMergeSort();
    System.out.println("Unsorted Array:");
    test.UnsortedArray(randomNumbers);
    System.out.println("Sorted Array");
    test.TopDownMergeSort(randomNumbers, sorted);
    test.SortedArray(randomNumbers);
}
}

这是我期望的：

未分类列表：100 61 8 76 51 89 30 63 11 1 47 74 85 63 80 45 18 34 74 25 8 90 61 44 25 2 40 100 47 1 72 24 86 80 87 75 46 85 14 30 43 31 27 48 96 96 26 20 44 1 67 1 30 35 87 78 18 46 37 31 6 61 62 92 71 45 6 10 12 38 96 14 22 83 96 31 65 74 58 47 87 65 28 61 91 73 3 92 87 22 68 0 9 18 13 89 36 8 35 44

排序列表：0 1 1 1 1 2 3 6 6 8 8 8 9 10 11 12 13 14 14 18 18 18 20 22 22 24 25 25 26 27 28 30 30 30 31 31 31 34 35 35 36 37 38 40 43 44 44 44 45 45 46 46 47 47 47 48 51 58 61 61 61 61 62 63 63 65 65 67 68 71 72 73 74 74 74 75 76 78 80 80 80 83 85 85 86 87

这就是我运行脚本时得到的结果：但我得到：

未排序数组：035175270392436并且一直持续到出现错误为止：RecursiveMergeSort.Split（RecursiveMergeSort.java:16）的线程“ main”中的java.lang.StackOverflowError的排序数组异常（RecursiveMergeSort.Split（RecursiveMergeSort.java:17））似乎与16/17行有关，但我不确定如何解决。感谢您提供的所有帮助。

Answer 1

    int middle = (end + start) / 2;
    Split(mainArray, start, middle, copyArray);
    Split(mainArray, start, end, copyArray);
    CombineArray(copyArray, start, middle, end, mainArray);

应该是

    int middle = (end + start) / 2;
    Split(mainArray, start, middle, copyArray);
    Split(mainArray, middle, end, copyArray);
    CombineArray(copyArray, start, middle, end, mainArray);

您超级亲密，只是第二个递归调用的起始索引应该是从中间索引到结尾，而不是从起点一直到结尾（导致堆栈溢出错误）

附带说明-您应该重命名方法以符合标准，例如：它们以小写字母开头，例如：

private void combineArray(int[] mainArray, int start, int middle, int end, int[] copyArray)