瞭解Java中合併排序算法的關鍵操作計數

Question

我正在評估合併排序算法並計算關鍵操作。雖然從技術上講，這是作業，但它是來自事先的任務，代碼是縮小版本，只顯示有問題的區域。我試圖更好地理解我的問題，並調試我的關鍵操作數量，以便準確描述。

該項目是實施合併排序和評估它。所關注的領域是計算關鍵操作並通過隨機填充10個不同尺寸的陣列來確定計數的偏差，並且每個尺寸運行50次不同的隨機數據（具有不同的隨機數據）。我的發現是，對於每個規模，關鍵操作的數量總是以相同的數量結束（例如，無論數據如何，規模10的數組來自68個關鍵操作），使關鍵操作偏差爲0.

教授指出這是不準確的並且我的程序出了問題，因爲它應該爲每個數組長度的不同數據生成不同的計數。我正在試圖弄清楚我的程序中的哪些內容不準確導致此問題。我已經檢查過每次傳遞產生不同的數組數據，並且這些數據正在傳遞給排序算法並進行正確排序。

下面是我編寫的代碼，不管數據如何，它仍然會產生相同的關鍵操作計數。任何人都可以指出我的問題？無論我對計數做什麼，它總會產生相同的值。

public class MergeSortSingle { 
public static int count = 0; 

private MergeSortSingle() { } 

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { 

    // copy to aux[] 
    for (int k = lo; k <= hi; k++) { 
     count++; 
     aux[k] = a[k]; 
    } 

    // merge back to a[] 
    int i = lo, j = mid+1; 
    for (int k = lo; k <= hi; k++) { 
     if  (i > mid) { 
      count++; 
      a[k] = aux[j++]; 
     } 
     else if (j > hi) { 
      count++; 
      a[k] = aux[i++]; 
     } 
     else if (less(aux[j], aux[i])) { 
      count++; 
      a[k] = aux[j++]; 
     } 
     else  { 
      count++; 
      a[k] = aux[i++]; 
     } 
    } 
} 

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { 
    if (hi <= lo) return; 
    int mid = lo + (hi - lo)/2; 
    sort(a, aux, lo, mid); 
    sort(a, aux, mid + 1, hi); 
    merge(a, aux, lo, mid, hi); 
} 

public static void sort(Comparable[] a) { 
    Comparable[] aux = new Comparable[a.length]; 
    sort(a, aux, 0, a.length-1); 
} 

private static boolean less(Comparable v, Comparable w) { 
    return v.compareTo(w) < 0; 
} 

private static void show(Comparable[] a) { 
    System.out.println("\nAfter Sorting completed:"); 
    System.out.print(Arrays.toString(a)); 
    System.out.println(); 
} 

public static void main(String[] args) { 
    int length = 10; 
    Comparable[] a = new Comparable[length]; 
    for (int w = 0; w < length; w++) { 
      a[w] = (int) (Math.random() * 10000 + 1); 
     } 
    System.out.println("Before Sorting:"); 
    System.out.print(Arrays.toString(a)); 
    System.out.println(); 
    MergeSortSingle.sort(a); 
    show(a); 
    System.out.println("\nCounter = " + count); 
} 
} 

樣本輸出1：

之前排序： [9661，4831，4865，3383，1451，3029，5258，4788，9463，8971]

排序完成後： [ 1451，3029，3383，4788，4831，4865，5258，8971，9463，9661]

計數器= 68

樣本輸出2：

之前排序： [9446，230，9089，7865，5829，2589，4068，5608，6138，372]

排序完成後： [230，372，2589，4068，5608，5829 ，6138，7865，9089，9446]

計數器= 68

合併排序的代碼是從利用： http://algs4.cs.princeton.edu/22mergesort/Merge.java.html

Answer 1

你只在合併子陣計數 - 您使用複製計數器Ť他排列號aux - 這將始終是相同數量的操作，然後在for循環中再次使用它 - 您有4個路徑，並且每個都增加計數器 - 再次固定次數。
你必須計算comarasions以及在sort - if (hi <= lo) - 它的一個操作。如果失敗 - 這是另一項操作。