MergeSort

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]，而是 "value"，这是 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

您正在使用整数数组 intArr，它在整个程序中具有固定长度。因此，每次执行 runtime = runtime + arr.length; 时，都会添加数组的初始长度。但是，它需要添加您正在处理的当前 "range" 以获得正确的数字。

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

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

MergeSort - 如何总结所有递归数组调用？

MergeSort - how do I sum up all recursive array calls?

java

recursion

random

runtime