我的合并排序代码有什么问题？

Question

我在计算机课上遇到了合并排序的问题。我不断收到错误或返回原始ArrayList。

我相信合并排序涉及到将数组（列表）递归地对半拆分，直到只剩下一个元素，然后从这些单独的元素开始，按排序顺序合并它们。直到数组（列表）被排序为止。至于实际的排序部分，我试图在新的ArrayList中插入两半之间的较高值，直到它们都为空，在这种情况下，填充的ArrayList现在被排序。

这是我当前的代码：

public static ArrayList<Integer> mergesort(ArrayList<Integer> arr) {

    // Base case: if size of ArrayList is 1, return it.
    if (arr.size() < 2) {
        return arr;
    }

    // Else: Find the middle index.
    int middle = (arr.size() - 1) / 2;

    // Split into left and right halves.
    ArrayList<Integer> leftHalf = new ArrayList<Integer>();
    for (int i = 0; i < middle; i++)
        leftHalf.add(arr.get(i));

    ArrayList<Integer> rightHalf = new ArrayList<Integer>();
    for (int j = middle; j < arr.size(); j++)
        rightHalf.add(arr.get(j));

    // Recurse using the halves.
    mergesort(leftHalf);
    mergesort(rightHalf);

    // Sort and merge the two halves.
    return merge(leftHalf, rightHalf, arr);
}

// Merge two halves and sort them, and put the sorted values into the ArrayList sorted.
public static ArrayList<Integer> merge(ArrayList<Integer> arr1, ArrayList<Integer> arr2, ArrayList<Integer> sorted) {

    // While the ArrayLists are not empty, add sorted elements to ArrayList sorted.
    while (arr1.size() > 0 && arr2.size() > 0) {

        // If the first element in A is greater than the first in B, remove A and add to ArrayList sorted.
        if (arr1.get(0) >= arr2.get(0)) {
            sorted.add(arr1.get(0));
            arr1.remove(0);
        }
        // Else, remove from B and add to ArrayList sorted.
        else {
            sorted.add(arr2.get(0));
            arr2.remove(0);
        }
    }

    // If there're still elements in A due to arr being odd
    // add them to C since they will be the largest.
    if (arr1.size() > 0)
        sorted.add(arr1.get(0));

    return sorted;
}

我将感谢任何帮助，但是请不要给我一个完整的合并排序的实现，因为我想真正学习如何在未来做到这一点。

Answer 1

如MarquisDeMizzle所述，当arr.size（）=1时，中间=1。

    int middle = arr.size() / 2;

主合并循环复制完所有剩余元素后，由于您不知道arr1或arr2是先变为空，请同时选中：

    // copy any remaining elements
    while (arr1.size() > 0)
        sorted.add(arr1.get(0));

    while (arr2.size() > 0)
        sorted.add(arr2.get(0));

如果感兴趣，您可能想学习自底向上的合并排序。它跳过了所有的递归，开始时假设一个包含n个元素的数组是n个大小为1的运行，只需使用索引在原始数组和临时数组之间进行来回合并。

Answer 2

我看到两个迫在眉睫的问题。

首先，你有无限递归。假设您传入一个4值列表，并打印列表大小和中间值，您将得到：

4号、中1号、中1号、中2号、中0号、中0号、中2号、中0号。。。无限大

记住，Java在代码中进行整数除法。

第二，如果将arr参数从mergesort传递到merge，则不会从中删除任何内容。所以，即使你通过了无限递归，你最终还是会得到一个更大的列表，你原来的列表加上你所有的。添加（）