合并排序计算交换次数并进行比较

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 中的所有内容都是按值传递，但如果不更改对象引用指向的引用，则可以模拟递归调用的按引用传递。

这是一个例子：

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