java - 归并排序算法错误

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();
    }
}

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

Answer 1

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

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 是一个与您的输入具有相同数组的新字段，而不是包含该数组的相同字段，因此赋值使得 puts 成为一个单独的字段中的数组 array 而不触及原始)。不幸的是，这个解决方案给我们留下了问题 1.5，因为我们没有改变 left和 right调用mergesort() ，在这种情况下，我们需要存储 merge() 的结果.

如果你想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在列表末尾，这样您就不必跟上实际末尾的位置。

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