合併排序比較計數器

Question

我似乎無法弄清楚我的比較計數器放在合併類的位置。雖然它完美地對數組進行排序，但它不會計算它所做交換（或比較）的次數。請幫助，這是我的除了最後的項目

 public static int mergeSort(int[] intArray, int first, int last) { 
     if(first < last) { 
      int mid = (first + last)/2; 
      mergeSort(intArray, first, mid); 
      mergeSort(intArray, mid + 1, last); 
      Merge(intArray, first, mid, last); 

    } 

    return comparisons; 

    } 

    public static int Merge(int[] intArray, int first, int mid, int last) { 

    //int count = 0; 
    comparisons = 0; 
    int first1 = first, last1 = mid; 
    int first2 = mid + 1, last2 = last; 
    int temp[] = new int[intArray.length]; 
    int index = first1; 

    while(first1 <= last1 && first2 <= last2) { 
     if(intArray[first1] < intArray[first2]) { 
      temp[index] = intArray[first1++]; 
      comparisons++; 
     } 
     else 
      temp[index] = intArray[first2++]; 
      index++; 
      comparisons++; 
    } 

    while(first1 <= last1) 
     temp[index++] = intArray[first1++]; 

    while(first2 <= last2) 
     temp[index++] = intArray[first2++]; 

    for(index = first; index <= last; index++) 
     intArray[index] = temp[index]; 


    return comparisons; 
    } 

Answer 1

在你這裏包括，你沒有表現出可變comparisons定義的代碼，但因爲你使用它沒有定義它，我假設這是你班上的一個領域。如果是這樣的話，我認爲這個問題是這一行Merge：

comparisons = 0; 

既然你做比較的數量的一個全局計數器，這條線的存在意味着，只要您撥打Merge，你即使在執行mergesort的過程中，您已經進行了一堆比較，將總數比較重置爲零。

作爲一個快速修復，只需刪除這一行。不過，我認爲你最好是通過不把它作爲一個字段來解決這個問題，並使用返回值來反饋所做比較的次數。下面是做到這一點的一種方法：

public static int mergeSort(int[] intArray, int first, int last) { 
    int compares = 0; 
    if(first < last) { 
     int mid = (first + last)/2; 
     compares += mergeSort(intArray, first, mid); 
     compares += mergeSort(intArray, mid + 1, last); 
     compares += Merge(intArray, first, mid, last); 

} 

return compares; 

}

公共靜態INT合併（INT [] intArray，詮釋第一，詮釋中旬，INT去年）{ INT比較= 0; int first1 = first，last1 = mid; int first2 = mid + 1，last2 = last; int temp [] = new int [intArray.length]; int index = first1;

while(first1 <= last1 && first2 <= last2) { 
    if(intArray[first1] < intArray[first2]) { 
     temp[index] = intArray[first1++]; 
     comparisons++; 
    } 
    else 
     temp[index] = intArray[first2++]; 
     index++; 
     comparisons++; 
} 

while(first1 <= last1) 
    temp[index++] = intArray[first1++]; 

while(first2 <= last2) 
    temp[index++] = intArray[first2++]; 

for(index = first; index <= last; index++) 
    intArray[index] = temp[index]; 


return comparisons; 

}