合併和插入排序的經驗分析 - 困難

Question

我想分析我的實現合併和插入排序的運行時間。我注意到一個奇怪的趨勢，並且我無法通過Google搜索找到任何具有相同問題的人，但我可能使用了錯誤的術語。

排序算法運行的次數似乎與算法完成所花費的時間量成反比。示例如下所示用於插入排序。

4213,2104,8195,9441,4823,925,980,964,911,491,470,482,481 ......（它看中〜490ms）

而且與同類歸併排序行爲，但合併看中〜95MS。

我不知道爲什麼會發生這種情況，我每次都會產生一個隨機數組......即使它不是隨機的，不應該每次都只是採用完全相同的時間（或關閉）嗎？爲什麼它會收斂在一個較小的價值？

只是尋找任何人可能知道爲什麼發生這種事情，因爲它似乎真的很奇怪我......我假設這是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

您將傳遞給插入排序，然後將此傳遞給合併排序。 在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);