归并排序算法错误

Question

嘿，我一直在 Eclipse 中使用 java 开发合并排序器应用程序。出于某种原因，我无法弄清楚，这让我很生气...

这是我正在处理的主要文件

public class MergeSorter {

    public Integer[] sort(Integer[] array) {
        return mergesort(array);
    }


    private Integer[] mergesort(Integer[] array) {
      if(array.length > 1) {
          Integer[] left = new Integer[array.length /2];
          Integer[] right = new Integer[array.length - left.length];

          mergesort(left);
          mergesort(right);

          merge(left, right);
        }
        return array;
    }


    public Integer[] merge(Integer[] left, Integer[] right) {
        int leftI = 0;
        int rightI = 0;
        int newI = 0;
        Integer[] newArr = new Integer[left.length + right.length];

        while (leftI < left.length && rightI < right.length) {
            if (left[leftI] < right[rightI]) {
                newArr[newI] = left[leftI];
                leftI++;
            } else {
                newArr[newI] = right[rightI];
                rightI++;
            }
            newI++;
        }

        // Either the left or the right may still have elements
        for (int i = leftI; i < left.length; i++) { // left
            newArr[newI] = left[i];
            newI++;
        }
        for (int i = rightI; i < right.length; i++) { // right
            newArr[newI] = right[i];
            newI++;
        }
        return newArr;
    }


    public void printCollection(Integer[] items) {
        for (int i = 0; i < items.length; i++) {
            System.out.print(items[i] + " ");
        }
        System.out.println();
    }
}

还有一个驱动程序文件，其中包含运行此代码的所有内容。有人告诉我我需要将合并排序器 class 通用化为使用 arrayLists 而不是数组，但我不知道该怎么做。我在想这是我需要使用列表的地方吗？但不确定，如有任何帮助，我们将不胜感激

Answer 1

你的逻辑有两个主要的整体。首先，你的归并排序 returns 无论如何都是输入。其次，您的合并数组永远不会被存储。

private Integer[] mergesort(Integer[] array) {
  if(array.length > 1) {
      Integer[] left = new Integer[array.length /2];
      Integer[] right = new Integer[array.length - left.length];

      mergesort(left); //problem 1.5: more on this later...
      mergesort(right);

      merge(left, right); //problem 2: stored array is returned but not stored
    }
    return array; //problem 1: returns array unchanged
}

解决问题2很简单。我们只需要将输出分配给这样的字段：

Integer[] result = merge(left,right);

或

array = merge(left,right);

使用其中一个或这些，result 或 array 将不会保留在 merge() 中完成的工作。您选择的策略将取决于您是否要修改输入。

这种关系实际上可能是违反直觉的，但是如果您希望您的输入保持不变，您可以使用第二行，现在问题 1 也已解决，因为我们已经更改 array。（输入未更改，因为 Java 是 按值传递 意味着 array 是一个新字段，与您的输入具有相同的数组，而不是包含该数组，因此赋值使得在字段 array 中放置一个单独的数组而不触及原始数组）。不幸的是，这个解决方案给我们留下了问题 1.5，因为我们没有通过调用 mergesort() 来更改 left 和 right，在这种情况下我们需要存储 [=16] 的结果=].

如果你想 mergesort() 改变输入数组（这不是一个不合理的想法）那么我们需要创建上面给出的单独的 Integer[] results 并将它的值复制到数组中保存的 int array。这也会提示问题 1.5，但可能会改变您方法的意图。

编辑： 还有第三个问题我没有提到。在 mergesort() 中，您创建了 left 和 right，但它们从未被填充。您应该将 array 中的值复制到 left 或 right 的一半中。类似于：

for(int i=0; i<left.length; i++) left[i] = array[i]; for(int i=0; i<right.length; i++) right[i] = array[left.length+i];

现在回答你的第二个问题，用 ArrayList<Integer> 完成你所做的每一件事应该不难。 The documentation 列出所有方法，您可以经常将 ArrayList 视为数组（execpt 而不是 array[i] 或 array[i]=value，您必须使用方法 array.get(i) 和 array.set(i,value)).但是，您可以使用 array.add(value) 之类的方法来简化事情，该方法将 value 放在列表的末尾，这样您就不必跟上实际结束的位置。

希望这可以帮助您准确了解问题所在并解决它们，这样您的大脑就可以对编程提供的所有其他精彩细节发痒

归并排序算法错误

Merge sort algorithm error

java

eclipse

mergesort