Java 数组操作和递归

Question

所以我花了相当多的时间来努力理解我的代码有什么问题。我有一个示例程序，我将其与我的示例程序进行了比较，该程序有效。我的代码结构与示例（使用两种方法）不同（按照我的教授的要求，全部采用一种方法）。我应该创建一个递归的、分而治之的解决方案来计算 int 数组中的反转。

我不明白为什么示例程序在整个递归过程中保持对输入数组的操作，而我的却没有。我知道 Java 是按值传递的，所以我很困惑为什么这个例子有效。任何帮助我理解这些解决方案的差异将不胜感激！谢谢！

具有两种方法的示例代码 - merge 和 invCounter:

public static long merge(int[] arr, int[] left, int[] right) {
  int i = 0, j = 0, count = 0;
  while (i < left.length || j < right.length) {
     if (i == left.length) {
        arr[i+j] = right[j];
        j++;
     } else if (j == right.length) {
        arr[i+j] = left[i];
        i++;
     } else if (left[i] <= right[j]) {
        arr[i+j] = left[i];
        i++;
     } else {
        arr[i+j] = right[j];
        count += left.length-i;
        j++;
     }
  }
  return count;
}

//the recursive function
public static long invCounter(int[] arr) {
  int sum = 0;

  if (arr.length < 2)
     return 0;

  int m = (arr.length + 1) / 2;
  int left[] = Arrays.copyOfRange(arr, 0, m);
  int right[] = Arrays.copyOfRange(arr, m, arr.length);
  sum += invCounter(left);
  sum += invCounter(right);
  sum += merge(arr, left, right);
  return sum;
}

我的单方法实现（尝试）：

public static int invCounter(int ranking[]) {
  int sum = 0;
  int result[] = new int[ranking.length];
  int resIndx = 0;

  if (ranking.length < 2) {
     return 0; //base case
  }

  //divide
  int left[] = Arrays.copyOfRange(ranking, 0, ranking.length/2);
  int right[] = Arrays.copyOfRange(ranking, ranking.length/2,                    
   ranking.length);
  sum += invCounter(left);
  sum += invCounter(right);

  int i = 0, j = 0;
  while (i < left.length || j < right.length) {
     if (i == left.length) {
        //i empty, just add j
        result[resIndx++] = right[j++];
     }
     else if (j == right.length) {
        //j empty, just add i
        result[resIndx++] = left[i++];
     }
     else if (right[j] < left[i]) {
        //inversion 
        result[resIndx++] = right[j++];
        sum += left.length - i;
     }
     else {
        //no inversion
        result[resIndx++] = left[i++];
     }
  }

  ranking = Arrays.copyOf(result, result.length);

  return sum;
}

为什么示例程序能够通过递归维护更新的数组，而我的却不能？

更新 (10/22/15)：所以我发现如果我将 result 替换为 ranking 并直接修改这个数组，我能够得到正确的结果。但我现在的问题是，为什么我不能使用结果数组来临时存储结果，然后在最后将它们复制到排名（参数）数组中？在我看来，这与将值放入之前所做的完全相同，但是如果我在最后更改 ranking ，则不会反映对

的更改。

Answer 1

您的方法不会修改 rankings 参数，而是创建一个新的 int 数组（结果），然后您对其进行处理。尝试直接在排名数组上设置值，而不是结果数组，或者简单地将结果变量设置为排名。

public static int invCounter(int ranking[]) {
  int sum = 0;
  int result[] = ranking;
//other code...

编辑：或者您可以复制它的内容，但不能使用 Arrays.copyOf，因为它首先创建一个新数组，然后复制到其中。请改用 System.arrayCopy 复制到现有数组中：

System.arrayCopy(result, 0, rankings, 0, result.length();

Java 数组操作和递归

Java Array Manipulation and Recursion

java

arrays

recursion

mergesort

divide-and-conquer