java 合并排序交换和比较的计数

gojuced7  于 2023-02-28  发布在  Java
关注(0)|答案(2)|浏览(105)

我有这个现有的代码,我需要添加一个交换和比较计数器。到目前为止,我相信我有正确的计数,但我不能让输出没有显示每个交换的循环。

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);
}
wfveoks0

wfveoks01#

在包含合并和合并排序方法的类中创建一个全局变量或字段。这将允许方法递增到变量。如果在方法中声明,它将保持为局部变量,每个递归调用将生成同名但属于不同递归方法调用的不同局部变量。因此,代码应如下所示:

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);
    }
}
v1l68za4

v1l68za42#

我认为最优雅的解决方案是使用int Package 类来模拟引用传递,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

相关问题