合併排序計數數量的交換和比較

Question

我有這個現有的代碼，我需要添加交換和比較計數器。到目前爲止，我相信我有正確的計數，但我無法得到輸出不顯示每個交換循環。

public void mergeSort(int[] a, int howMany) { 


    if (a.length >= 2) { 
     // split array into two halves 
     int[] left = Arrays.copyOfRange(a, 0, a.length/2); 
     int[] right = Arrays.copyOfRange(a, a.length/2, a.length); 


     // sort the two halves 
     mergeSort(left,howMany); 
     mergeSort(right, howMany); 

     // merge the sorted halves into a sorted whole 
     merge(a, left, right); 

    } 
} 




// Merges the left/right elements into a sorted result. 
// Precondition: left/right are sorted 
public static void merge(int[] result, int[] left, 
             int[] right) { 
    int i1 = 0; // index into left array 
    int i2 = 0; // index into right array 
    int compCount = 0; 
    int swapCount = 0; 
    for (int i = 0; i < result.length; i++) { 
     compCount++; 
     if (i2 >= right.length || 
      (i1 < left.length && left[i1] <= right[i2])) { 
      result[i] = left[i1]; // take from left 
      i1++; 
      swapCount++; 
     } else { 
      result[i] = right[i2]; // take from right 
      i2++; 
      swapCount++; 
     } 
    } 
    //figure this loop issue out System.out.println("merge sort " + compCount + " " + swapCount); 
} 

Answer 1

在保存合併和合並排序方法的類中創建全局變量或字段。這將允許方法增加到變量。如果在方法內部聲明它將保留爲局部變量，並且每次遞歸調用都將生成具有相同名稱但屬於不同遞歸方法調用的不同局部變量。因此，你的代碼應該是這樣的：

public class ClassWithMergeMethodInside 
{ 
    int swapCount; 
    int compCount; 

    public void mergeSort(int[] a, int howMany) { 
     //Since merge sort begins here you may initiliaze the variables here 
     swapCount = 0; 
     compCount = 0; 
     if (a.length >= 2) { 
      // split array into two halves 
      int[] left = Arrays.copyOfRange(a, 0, a.length/2); 
      int[] right = Arrays.copyOfRange(a, a.length/2, a.length); 


      // sort the two halves 
      mergeSort(left,howMany); 
      mergeSort(right, howMany); 

      // merge the sorted halves into a sorted whole 
      merge(a, left, right); 

     } 
    } 




    // Merges the left/right elements into a sorted result. 
    // Precondition: left/right are sorted 
    public static void merge(int[] result, int[] left, 
              int[] right) { 
     int i1 = 0; // index into left array 
     int i2 = 0; // index into right array 
     //Will not declare counter variables here 
     for (int i = 0; i < result.length; i++) { 
      compCount++; 
      if (i2 >= right.length || 
       (i1 < left.length && left[i1] <= right[i2])) { 
       result[i] = left[i1]; // take from left 
       i1++; 
       swapCount++; 
      } else { 
       result[i] = right[i2]; // take from right 
       i2++; 
       swapCount++; 
      } 
     } 
     //figure this loop issue out System.out.println("merge sort " + compCount + " " + swapCount); 
    } 
} 

Answer 2

我認爲最完美的解決方案是通過使用int包裝類來模擬傳遞的引用。 Java中的所有東西都是按值傳遞的，但如果不更改Object引用指向的引用，則可以模擬遞歸調用的傳遞引用。

下面是一個例子：

import java.util.Arrays; 

public class TestMain 
{ 
    public static void main(String[] args) 
    { 
    int[] array = new int[]{6, 2, 1, 4, 5, 3}; 

    IntWrapper countCompare = new IntWrapper(); 
    IntWrapper countSwap = new IntWrapper(); 



    MergeSort mSort = new MergeSort(); 

    mSort.mergeSort(array, countCompare, countSwap); 

    System.out.println("Compares: " + countCompare.val); 

    System.out.println("Swaps: " + countSwap.val); 

    for (int i = 0; i < array.length; i++){ 
     System.out.print(String.format("%-3d", array[i])); 
    } 
    } 


} 

public class IntWrapper{ 
    int val = 0; 
} 

public class MergeSort 
{ 


    public void mergeSort(int[] a, IntWrapper compares, IntWrapper swaps) { 


     if (a.length >= 2) { 
      // split array into two halves 
      int[] left = Arrays.copyOfRange(a, 0, a.length/2); 
      int[] right = Arrays.copyOfRange(a, a.length/2, a.length); 


      // sort the two halves 
      mergeSort(left, compares, swaps); 
      mergeSort(right, compares, swaps); 

      // merge the sorted halves into a sorted whole 
      merge(a, left, right, compares, swaps); 

     } 
    } 




    // Merges the left/right elements into a sorted result. 
    // Precondition: left/right are sorted 
    public static void merge(int[] result, int[] left, int[] right, IntWrapper compares, IntWrapper swaps) { 
     int i1 = 0; // index into left array 
     int i2 = 0; // index into right array 
    //int compCount = 0; 
    //int swapCount = 0; 
     for (int i = 0; i < result.length; i++) { 
      //compCount++; 
      compares.val++; 
      if (i2 >= right.length || 
      (i1 < left.length && left[i1] <= right[i2])) { 
       result[i] = left[i1]; // take from left 
       i1++; 
      //swapCount++; 
      swaps.val++; 
      } else { 
       result[i] = right[i2]; // take from right 
       i2++; 
      //swapCount++; 
      swaps.val++; 
      } 
     } 
    //figure this loop issue out System.out.println("merge sort " + compCount + " " + swapCount); 
    } 
} 

輸出：

Compares: 16 
Swaps: 16 
1 2 3 4 5 6