自上而下递归方法不起作用，不确定如何修复它。 Java

Question

我的 "Data Structure and Algorithm class" 有一个家庭作业问题 - 在 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]);
    }
}
}

这里是 Driver：

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 434 3 3 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 68 7 091 27 65 28 68 7 091 27 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 83 85=85[813]

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

未排序数组： 035 175 270 392 436 它一直持续到我收到错误为止： RecursiveMergeSort.Split(RecursiveMergeSort.java:16) RecursiveMergeSort.Split(RecursiveMergeSort.java:17) 线程 "main" java.lang.WhosebugError 中的排序数组异常它似乎与第 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)

自上而下递归方法不起作用，不确定如何修复它。 Java

Top Down Recursive method isn't working and not sure how to fix it. Java

java

algorithm

mergesort

recursive-datastructures