0

我已经实现了合并排序以与我的分配算法一起使用。它可以工作，但是对于大量的测试用例，返回结果需要很长时间，而且不应该。我已经清除了我的主要方法，并且我确信合并排序是问题所在。有人能解释一下我做了什么让它如此低效吗？

    public static double[] merge(double[] arrayA, double[] arrayB){
        double[] arrayC = new double[0];

        while((arrayA.length != 0) && (arrayB.length != 0)){
            if(arrayA[0]>arrayB[0]){
                arrayC = Array.arrAdd(arrayC, arrayB[0]);
                arrayB = Array.arrRem(arrayB);
            }else{
                arrayC = Array.arrAdd(arrayC, arrayA[0]);
                arrayA = Array.arrRem(arrayA);
            }
        }
        while(arrayA.length != 0){
            arrayC = Array.arrAdd(arrayC, arrayA[0]);
            arrayA = Array.arrRem(arrayA);
        }
        while(arrayB.length != 0){
            arrayC = Array.arrAdd(arrayC, arrayB[0]);
            arrayB = Array.arrRem(arrayB);
        }

        return arrayC;
    }

    public static double[] mergeSort(double[] arrayA){
        if(arrayA.length == 1){
            return arrayA;
        }

        int a;
        int b;

        if(arrayA.length % 2 != 0){
            a = (arrayA.length+1)/2;
            b = (arrayA.length-1)/2;
        }else{
            a = (arrayA.length)/2;
            b = (arrayA.length)/2;
        }

            double[] array1 = new double[a];
            double[] array2 = new double[b];

        for(int i=0; i<array1.length; i++){
            array1[i] = arrayA[0];
            arrayA = Array.arrRem(arrayA);

        }
        for(int i=0; i<array2.length; i++){
            array2[i] = arrayA[0];
            arrayA = Array.arrRem(arrayA);
        }

        array1 = mergeSort(array1);
        array2 = mergeSort(array2);

        return merge(array1, array2);
    }

我还包括我的“arrAdd”和“arrRem”方法，它们用于在数组末尾添加一个元素并从索引 0 中删除一个元素。

    public static double[] arrAdd(double[] arrayA, double value){
        double[] arrayB = new double[arrayA.length+1];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length);
        arrayB[arrayA.length] = value;
        return arrayB;
    }

    public static double[] arrRem(double[] arrayA){
        double[] arrayB = new double[arrayA.length-1];
        System.arraycopy(arrayA, 1, arrayB, 0, arrayA.length - 1);
        return arrayB;
    }
4

2 回答 2

1

因为arrayRem效率极低。

假设您有一个包含 100 万个元素的数组。你想通过这些元素。您可以通过查看第一个元素来执行此操作，然后通过将所有其他元素复制到更靠近前面的位置来删除第一个元素，并重复此操作直到数组为空。

因此，在使用第一个元素后，您将复制 999 999 个元素。
使用第二个元素后，您将复制 999 998 个元素。
使用第三个元素后，您将复制 999 997 个元素。
（此处省略 999 996 行）
在消耗第 1 000 000 个元素后，您将复制 0 个元素。

也就是说，要读取长度为 100 万的数组，您将复制总共 1 000 000 * 500 000 = 500 000 000 000 个元素。这需要一段时间。

合并排序的正确实现将通过递增索引来读取数组，而不是通过递增删除第一个元素并每次复制所有剩余元素。

类似地，添加元素的有效方法是创建一个足够大的数组以预先容纳所有元素，然后通过跟踪下一个元素应该写入的索引，将每个单个元素写入正确的位置，而不是复制添加的每个元素的所有现有元素。

于 2021-10-16T19:27:07.040 回答
0

创建数组的副本以添加/删除单个项目是一种操作数据的非常昂贵的方法。使用ArrayListor 'LinkedList' 而不是普通数组！

如果您需要一种更快的方式来处理原始类型，请查看 Colt 库：

https://dst.lbl.gov/ACSSoftware/colt/

于 2021-10-16T19:25:10.357 回答