通用 MergeSort Java 实现堆栈溢出错误

Question

我正在尝试用 Java 编写一个通用的合并排序方法。

这是我的源代码：

import java.util.ArrayList;

import java.util.List;

/**

 * An implementation of MergeSort

 *

 * @param <T> the type of data held by the array.

 */

public class MergeSort<T extends Comparable<? super T>> implements ArraySort<T>

{

    /**

     * Sort the array using a MergeSort.

     *

     * (recursively breaks down the array into sub arrays until arrays of size 1 are reached.)

     * (then works backwards merging these arrays back into each other until a sorted array state is reached containing

     *  all the elements of the initial unsorted array, but now sorted).

     *

     * @param array the array to be sorted.

     * @return array (sorted)

     */

    @Override

    public T[] sort(T[] array)

    {

        //If the array being sorted is less than 2 elements, it is already sorted and cannot be split into two separate

        //     arrays, so return the initial array to prevent an exception.

        if(array.length < 2)

        {

            return array;

        }

        //Create two sub arrays from the initial array passed in.

        T[] temp1 = copy(array, 0, (array.length/2) - 1);

        T[] temp2 = copy(array, (array.length/2), array.length - 1);

        //Sort these two arrays.

        sort(temp1);

        sort(temp2);

        //Merge the two subarrays back into the initial array.

        merge(array, temp1, temp2);

        //return the now sorted array.

        return array;

    }

我不知道为什么，但是当我调用第 38 行和第 42 行时出现 StackOverflow 错误。

38 = T[] temp1 = copy(...) in the sort() method

42 = sort(temp1) in the sort() method.

这让我相信错误出在复制功能的某个地方，但我不知道如何解决问题或找到解决方案。

有人可以帮我解决这个通用合并排序的实现吗？

StackTrace 用于对 12 个元素的数组进行排序。

https://docs.google.com/document/d/1Ig5p7TZF_eX0Q_rroORnZUWnXtep7x-7cmDiSAZWlj8/edit?usp=sharing

Answer 1

你的数组复制是错误的。利用：&nbsp; &nbsp; private <T> T[] copy(T[] list, int from, int to) {&nbsp; &nbsp; &nbsp; &nbsp; return Arrays.copyOfRange(list, from, to);&nbsp; &nbsp; }您的代码中有更多错误（merge不处理不同长度的数组），但这应该可以解决您的问题。见List.toArray(T[])...如果列表适合指定的数组，则在其中返回。即您正在复制到原始数组中，而不是创建一个新数组，因此您的数组实际上永远不会减小大小。

Answer 2

您的条件不够好，您会在数组上获得无限排序调用。至少您应该包含大小等于 2 的数组：if(array.length&nbsp;<=&nbsp;2)此外，您的复制方法必须改进。无论如何，请复制/粘贴您的完整堆栈跟踪。