为什么我的归并排序执行缓慢？

Question

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

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

Answer 1

创建数组副本到 add/remove 单个项目是一种非常昂贵的数据操作方式。使用 ArrayList 或 'LinkedList' 而不是普通数组！

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

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

Answer 2

因为arrayRem效率极低。

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

所以在消耗了第一个元素之后，你复制了 999 999 个元素。
消耗完第二个元素后，您将复制 999 998 个元素。
消耗完第三个元素后，你正在复制 999 997 个元素。
(此处省略999 996行)
在消耗完第 1 000 000 个元素后，您正在复制 0 个元素。

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

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

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

为什么我的归并排序执行缓慢？

Why is my implementation of merge sort slow?

java

sorting

performance

mergesort

time-complexity