algorithm - 归并与插入排序的实证分析——难点

Question

我正在尝试分析我的合并和插入排序实现的运行时间。我注意到一个奇怪的趋势，我无法通过谷歌搜索找到有同样问题的人，但我可能使用了错误的术语。

排序算法运行的次数似乎与算法完成所需的时间成反比。下面显示了插入排序的示例。

4213,2104,8195,9441,4823,925,980,964,911,491,470,482,481...(稳定在 ~490 毫秒)

和归并排序类似的行为，但归并时间约为 95 毫秒。

我不知道为什么会这样，我每次都生成一个随机数组......即使它不是随机的，它不应该每次(或关闭)都花费完全相同的时间吗？为什么它收敛于一个较小的值？

只是在寻找可能知道为什么会发生这种情况的人，因为这对我来说真的很奇怪......我假设这可能是 Java 在幕后做的事情？任何建议/提示表示赞赏!

我正在运行的所有代码都发布在下面。首先显示测试代码。

public static void tests(int noTests, int arraySize){
    //set up the running totals of the time taken by insertion and merge
    double insertSum = 0;
    double mergeSum = 0;

    for(int i = 0; i < noTests; i++){
        //generate an array of random integers
        Integer[] randInput = generateRandomArray(arraySize);
        Integer[] insertInput = Arrays.copyOf(randInput, randInput.length);
        Integer[] mergeInput = Arrays.copyOf(randInput, randInput.length);
        //start the clock for insertion
        final long insertionStart = System.nanoTime();
        //sort it 
        insertionSort(insertInput);
        //stop the clock for insertion
        final long insertionFinish = System.nanoTime();
        System.out.println("Time taken for insertion: " + (insertionFinish - insertionStart)/1000 + " ms");
        //add it to the running total 
        insertSum += (insertionFinish - insertionStart)/1000;

        //likewise for merge 
        final long mergeStart = System.nanoTime();
        mergeSort(mergeInput);
        final long mergeFinish = System.nanoTime();
        System.out.println("Time taken for merge: " + (mergeFinish - mergeStart)/1000 + " ms");
        mergeSum += (mergeFinish - mergeStart)/1000;
    }
    //Get the average by diving by the number of times it ran 
    System.out.println("-------------------------------------------------------");
    System.out.println("Insert average: " + insertSum/noTests);
    System.out.println("Merge average: " + mergeSum/noTests);
}

//Generate an array of random Integers 
public static Integer[] generateRandomArray(int n){
    Integer[] arr = new Integer[n];
    for(int i = 0; i < n; i++){
        arr[i] = (int) Math.floor(Math.random()*100);
    }
    return arr;
}

public static <T extends Comparable<T>> T[] insertionSort(T[] a){
    for(int i = 1; i < a.length; i++){
        int j = i-1;
        T key = a[i];

        while(j >= 0 && a[j].compareTo(key) > 0){
            a[j+1] = a[j];
            j = j-1;
        }
        a[j+1] = key;
    }
    return a;
}

@SuppressWarnings("rawtypes")
public static Comparable[] mergeSort(Comparable[] input){

    if(input.length<=1){
        return input;
    }

    int middle = Math.floorDiv(input.length, 2);

    Comparable a[] = new Comparable[middle];
    for(int i = 0; i < middle; i++){
        a[i] = input[i];
    }

    Comparable b[] = new Comparable[input.length - middle];
    for(int i = middle; i < input.length; i++){
        b[i-middle] = input[i];
    }

    mergeSort(a);
    mergeSort(b);
    merge(input, a, b);

    return input;
}

@SuppressWarnings({ "rawtypes", "unchecked" })
public static void merge(Comparable[] input, Comparable[] a, Comparable[] b){

    int inputIndex = 0;
    int aIndex = 0;
    int bIndex = 0;

    while(aIndex < a.length && bIndex < b.length){

            if(aIndex < a.length & a[aIndex].compareTo(b[bIndex]) < 0){
                input[inputIndex] = a[aIndex];
                aIndex++;
            } else{
                input[inputIndex] = b[bIndex];
                bIndex++;
            }
            inputIndex++;
    }
}

示例输出:

Time taken for insertion: 8060 ms
Time taken for merge: 1714 ms
Time taken for insertion: 11533 ms
Time taken for merge: 23418 ms
Time taken for insertion: 5674 ms
Time taken for merge: 326 ms
Time taken for insertion: 8235 ms
Time taken for merge: 459 ms
Time taken for insertion: 9737 ms
Time taken for merge: 333 ms
Time taken for insertion: 4756 ms
Time taken for merge: 374 ms
Time taken for insertion: 1088 ms
Time taken for merge: 493 ms
Time taken for insertion: 899 ms
Time taken for merge: 1147 ms
Time taken for insertion: 783 ms
Time taken for merge: 474 ms
Time taken for insertion: 653 ms
Time taken for merge: 252 ms
-------------------------------------------------------
Insert average: 5141.8
Merge average: 2899.0

谢谢!

编辑:更新了按引用传递错误，插入和合并现在都对它们自己的数组进行排序。问题依然存在。更新示例输出，如果给定更多项，插入最终仍会收敛到比开始时低得多的值

Answer 1

您将 randInput 传递给插入排序，然后将其传递给归并排序。在 Java 中，数组通过引用 传递。在 call by reference 中，如果您在方法中更改其数组，则更改后的数组将可用于调用数组。

所以 randInput 在传递给 mergesot 方法时被排序。看这个:

//generate an array of random integers
Integer[] randInput = generateRandomArray(arraySize);
// randInput is random
insertionSort(randInput); 

// randInput is sorted
mergeSort(randInput);