为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

弑天下 2022-01-19 10:35:43
我正在尝试用 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() method42 = sort(temp1) in the sort() method.这让我相信错误出在复制功能的某个地方,但我不知道如何解决问题或找到解决方案。有人可以帮我解决这个通用合并排序的实现吗?StackTrace 用于对 12 个元素的数组进行排序。https://docs.google.com/document/d/1Ig5p7TZF_eX0Q_rroORnZUWnXtep7x-7cmDiSAZWlj8/edit?usp=sharing
查看完整描述

2 回答

?
森栏

TA贡献1810条经验 获得超5个赞

你的数组复制是错误的。


利用:


    private <T> T[] copy(T[] list, int from, int to) {

        return Arrays.copyOfRange(list, from, to);

    }

您的代码中有更多错误(merge不处理不同长度的数组),但这应该可以解决您的问题。


见List.toArray(T[])


...如果列表适合指定的数组,则在其中返回。


即您正在复制到原始数组中,而不是创建一个新数组,因此您的数组实际上永远不会减小大小。


查看完整回答
反对 回复 2022-01-19
?
慕妹3146593

TA贡献1820条经验 获得超9个赞

您的条件不够好,您会在数组上获得无限排序调用。

至少您应该包含大小等于 2 的数组:

if(array.length <= 2)

此外,您的复制方法必须改进。

无论如何,请复制/粘贴您的完整堆栈跟踪。


查看完整回答
反对 回复 2022-01-19
  • 2 回答
  • 0 关注
  • 146 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信