合并排序和递归混淆/代码不起作用

Question

我已经在这里呆了几天，阅读了许多伪代码并观看了解释递归和归并排序的视频。我理解归并排序并且有点理解递归——除非它适用于我下面的代码中的数组。我进行了一些调试，无论出现越界错误，我的程序似乎都没有正确排序。我很迷茫，很感激你能提供的任何帮助！

问题：1) 数组上的递归是什么意思？它是否创建了一个由原始数组保存的子数组？——如果有道理的话。2）为什么我的代码会遇到越界错误，即使我按照教程学习了 t 并且在每次通过后都设置了 k 值。具体是遇到了这个问题。

这是代码：

public class Merge {

    public static void main(String[] args) {

    }

    static void mergeSort(int arr[]){

        int r = arr.length - 1;

        Merge.sort(arr,0,r);

        System.out.println(arr);

    }

    static void sort(int arr[], int p, int r){

        if(p<r){

            int q = (p+r)/2;

            sort(arr,p,q);

            sort(arr,q+1,r);

            merge(arr,p,q,r);

        }

    }

    static void merge(int arr[], int p, int q, int r){

        int n1 = q-p+1;

        int n2 = r-q;

        int L[] = new int[n1];

        int R[] = new int[n2];

        for(int i = 0; i< n1; i++){

            L[i] = arr[i];

        }

        for(int j = 0; j< n2; j++){

            R[j] = arr[q+1+j];

        }

        int i = 0, j = 0;

        int k = 1;

        while(i<n1 && j<n2){

            if(L[i]<= R[j]){

                arr[k] = L[i];

                i++;

            }

            else{

                arr[k] = R[j];

                j++;

            }

            k++;

        }

        while(i<n1){

            arr[k] = L[i];

            i++;

            k++;

        }

Error occurs here --> while(j<n2){

            arr[k] = R[j];

            k++;

        }

    }

}

感谢您的帮助！

编辑：只是想说我对这篇文章的精彩回复有多棒，非常感谢您的时间。

Answer 1

让我们稍微分解一下您的问题 - 具体来说，递归是什么意思？你可以把它想象成一个循环——它对自己执行一个操作，直到它达到停止条件。以for循环为例for(int i = 0; i < 2; i++)将执行操作，直到达到变量 i 不再小于 2 的情况。同样，递归地void methodLoop(int input){&nbsp; &nbsp; int i = input;&nbsp; &nbsp; if(i < 2){&nbsp; &nbsp; &nbsp; &nbsp;methodLoop(i+1);&nbsp; &nbsp; }&nbsp; &nbsp; else{&nbsp; &nbsp; &nbsp; System.out.println("Base case reached! I is no longer less than 2!");&nbsp; }}执行类似的操作，只是用递归代替！这对数组意味着什么？这取决于。您在问题中提到的是一个称为多维数组的概念 - 数组中的数组。这些像普通数组一样工作，它只是一个在每个索引中包含另一个数组的数组 - 这些实例化如下String[][] multidimensionalarray = new array[4][4]为了形象化这样的概念，将其视为坐标网格可能更容易，索引是坐标位置，该索引处的值包含有关该位置的信息。例如，假设多维数组已经填充了这样的数据，它可能看起来像：4 a b c d3 e f g h2 i j k l1 m n o p&nbsp; 1 2 3 4然后 multidimensionarray[2][3] 的值将返回字符串 k！