合并排序 - 如何汇总所有递归数组调用？

Question

我正在学习计算机科学，我们目前的任务是用2^k (k = 1-16)的数组长度和随机数以及每个位置来编写合并排序算法。我们必须通过合计所有递归数组调用的长度来输出该算法的运行时间。

我们老师举了以下例子：数组长度=4：运行时=2*2 4*1=8

我目前的逻辑是，每个实例都只是数组的长度，这就是为什么我认为在每次递归调用后添加 array.length 就足够了。然而，这发出了太多的调用...

我的数组输出…

长度4: 4 8 12 (0...3)

长度8: 8 16 24 32 40 48 56 (0...7)

长度16:16 32 48 64 80 96 112 128 144 160 176 192 208 224 240（0…15）

有一点很清楚，输出总是等于初始数组长度。我已经把正确的值加粗了，这些值应该是最终的输出...如果我理解正确的话。

有人能帮我计算运行时间吗？

我的代码：

请记住，intArr大小通常不是16[或8或4]，而是“值”，即2^k引用。我降低了大小，以便更容易在运行时计算中发现故障。

import java.util.Random;

public class Mergesort {

    Random generator = new Random();

    static int runtime;
    static int base = 2;
    static int potency = 1 + (int) (Math.random() * ((16)));
    static int value = (int) java.lang.Math.pow(base, potency);
    public static int[] intArr = new int[16];

    {
        for (int i = 0; i < intArr.length; i++) {
            intArr[i] = generator.nextInt(100);
        }
    }

    public static void main(String[] args) {
        Mergesort ms = new Mergesort();
        int[] arr = ms.splitHalf(0, intArr.length - 1); 

        System.out.println("Mergesort-Algorithm" + "\n" + "\n" + "Position:" + " Wert");
        for (int i = 0; i < arr.length; i++) { 
            System.out.println(i + 1 + ": " + arr[i]);
        }
    }

    public int[] splitHalf(int l, int r) { 
        if (l < r) { 
            int q = (l + r) / 2;
            splitHalf(l, q); 
            splitHalf(q + 1, r); 
            merge(l, q, r); 
        }
        return intArr; 
    }

    private void merge(int l, int q, int r) { 
        int[] arr = new int[intArr.length];
        int left;
        int right;

        for (left = l; left <= q; left++) {
            arr[left] = intArr[left];
        }
        for (right = q + 1; right <= r; right++) {
            arr[r + q + 1 - right] = intArr[right];
        }
        left = l;
        right = r;
        for (int k = l; k <= r; k++) { 
            if (arr[left] <= arr[right]) { 
                intArr[k] = arr[left]; 
                left++; 
            } else {
                intArr[k] = arr[right]; 
                right--; 
            }
        }
        runtime = runtime + arr.length;
        System.out.println(runtime);
    }
}

Answer 1

您使用的是整数数组＜code＞intArr＜/code＞，在整个程序中它的长度是固定的。因此，每次执行runtime=runtimearr.length添加数组的初始长度。然而，它需要添加您正在处理的当前“范围”以获得正确的数字。

您应该更改您的方法接口，以获得更好的代码结构。

// gets two sorted arrays and returns the merged sorted array of both
static int[] merge(int[] firstSortedArray, int[] secondSortedArray) {
    int[] result = int[firstSortedArray.length + secondSortedArray.length];
    // merge both arrays into result
    return result;
}

// gets an input array and returns the same array in a sorted fashion
static int[] split(int[] inputArray) {
    // an array of size zero/one is already sorted and can be return unchanged
    if(inputArray.length == 0 || inputArray.length == 1)
        return inputArray; 

    int[] leftSortedHalf = split(/*copy first half here*/);
    int[] rightSortedHalf = split(/*copy second half here*/);
    return merge(leftSortedHalf, rightSortedHalf);
}