合并和插入排序困难的实证分析

Question

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

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

4213,2104,8195,9441,4823,925,980,964,911,491,470,482,481...(大约490毫秒)

与合并排序有相似的行为，但合并在~95 on上得到解决。

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

我只想找一个知道为什么会发生这种事的人因为我觉得很奇怪.我想这应该是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);