合并排序和递归 confusion/code 不工作

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++;
        }
    }
}

感谢您的帮助！

编辑：只是想说我非常感谢对此 post 的惊人回复，非常感谢您抽出宝贵的时间。

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] 的值将 return 字符串 k!

Answer 2

老实说，我认为您的句子 'recursion on an array' 没有任何意义。

您的代码有一个数组 arr，该数组已排序。您的 merge 方法应该对该数组的各个部分进行排序，但每次调用它时，它都具有相同的整个数组对象。没有子数组；这只是由这个方法来排序这个数组的相关部分。如果这个方法没有做它应该做的事情，那么就会出现问题。

让我们仔细看看出现错误的循环：

    while(j<n2){
        arr[k] = R[j];
        k++;
    }

假设我们用 j < n2 进入这个循环。会发生什么？

我们进入循环是因为j < n2，所以我们将R[j]复制到arr[k]，然后递增k。我们回到循环的顶部，我们发现 j 仍然小于 n2 因为两个变量都没有改变，所以我们将 R[j] 复制到 arr[k] 并增加 k 再次。我们回到循环的顶部，发现 j 仍然小于 n2 并再次循环。依此类推，直到最终 k 从 arr 的末尾掉下来，我们得到一个 ArrayIndexOutOfBoundsException.

在合并排序的这一部分，我们试图将尚未合并到 arr 的 R 的内容复制到 arr，但我们忘记递增 j。因此，要修复此循环，请增加 j 以及 k:

    while(j<n2){
        arr[k] = R[j];
        j++;
        k++;
    }

请注意，之前的循环，即以 while(i<n1) 开头的循环，递增 i 和 k。这一变化现在使两个循环看起来更相似。

那么，我们再次运行我们的代码，会发生什么？我们仍然得到 ArrayIndexOutOfBoundsException。显然我们还没有解决问题，但是如果我们只是遇到同样的错误，我们是否取得了任何进展？

merge方法的目的是合并arr从位置p到q以及从位置q+1到r包容。如果两个子数组都排序了，那么合并后 arr 从 p 到 r 的整个子数组将被排序。

但是，当我们将值写回 arr 时，我们从索引 1 开始。这个对吗？假设 arr 的长度为 2，p = 0、q = 0 和 r = 1。我们有两个元素要排序。第一个写到哪里，第二个写到哪里？

答案是第一个被写入 arr[1]，而您的代码抛出异常，因为它试图将第二个写入 arr[2]，它不存在。

您希望 k 从您正在排序的子数组的开头开始。您希望 k 从 p.

开始

所以替换行

        int k = 1;

和

        int k = p;

我们再试一次，现在我们发现代码不再抛出异常，而是打印一些难以理解的东西，比如[I@65fb1cd。恼人的是，这就是 Java 默认情况下打印数组的方式。要解决此问题，请将行 import java.util.Arrays; 添加到您的文件并替换行

        System.out.println(arr);

和

        System.out.println(Arrays.toString(arr));

您的代码现在应该会在运行时打印出一个数字列表。

但是，我们现在发现我们的代码没有正确排序数组。我要求它对值 8, 1, 4, 9 进行排序，结果返回 1, 1, 8, 9。 1 已复制，4 已消失。

再次回想一下，merge 方法的目的是将 arr 从 p 排序到 r。仔细查看哪些值从数组复制到 L 和 R:

        for(int i = 0; i< n1; i++){
            L[i] = arr[i];
        }
        for(int j = 0; j< n2; j++){
            R[j] = arr[q+1+j];
        }

请注意这两个循环之间的任何区别，除了使用 j 而不是 i、n2 而不是 n1 和 R 而不是 L?

请注意，当您复制到 R 时，您正在复制从位置 q+1 开始的值。这些是第二个排序子数组中的值。但是，当您复制到 L 时，您是从位置 0 开始复制值。这不一定是第一个排序的子数组开始的地方。那当然是从p.

开始

将第一个循环替换为：

        for(int i = 0; i< n1; i++){
            L[i] = arr[p+i];
        }

最后，我们运行代码并发现我们现在有一个可用的合并排序程序。

合并排序和递归 confusion/code 不工作

Mergesort & recursion confusion/code not working

java

recursion

mergesort