1

我似乎无法弄清楚在 Merge 类中放置比较计数器的位置。尽管它对数组进行了完美的排序，但它不会计算它进行的交换（或比较）的次数。请帮助这是我最终项目的一部分

      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;
  }
4

1 回答 1

1

在您在这里包含的代码中，您没有显示变量的定义comparisons，但是由于您在没有定义它的情况下使用它，我假设它是您类中的一个字段。如果是这种情况，我认为问题出在以下行Merge：

comparisons = 0;

由于您有一个比较次数的全局计数器，因此该行的存在意味着无论何时调用Merge，您都将比较总数重置为零，即使在执行合并排序过程中您已经进行了一堆比较。

作为快速修复，只需删除此行。但是，我认为您最好通过根本不将其作为字段并使用返回值来传达所进行的比较次数来解决此问题。这是执行此操作的一种方法：

  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;

}

public static int Merge(int[] intArray, int first, int mid, int last) { int comparisons = 0; int first1 = first, last1 = mid; int first2 = mid + 1, last2 = 最后一个；int temp[] = new int[intArray.length]; int 索引 = 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;

}

于 2015-08-26T17:09:38.910 回答