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

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){

    int i = input;

    if(i < 2){

       methodLoop(i+1);

    }

    else{

      System.out.println("Base case reached! I is no longer less than 2!");

  }

}

执行类似的操作，只是用递归代替！

这对数组意味着什么？这取决于。您在问题中提到的是一个称为多维数组的概念 - 数组中的数组。这些像普通数组一样工作，它只是一个在每个索引中包含另一个数组的数组 - 这些实例化如下

String[][] multidimensionalarray = new array[4][4]

为了形象化这样的概念，将其视为坐标网格可能更容易，索引是坐标位置，该索引处的值包含有关该位置的信息。例如，假设多维数组已经填充了这样的数据，它可能看起来像：

4 a b c d

3 e f g h

2 i j k l

1 m n o p

  1 2 3 4

然后 multidimensionarray[2][3] 的值将返回字符串 k！