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;

比較回数のグローバル カウンターが 1 つあるため、この行が存在するということは、 を呼び出すたびにMerge、比較の合計回数をゼロにリセットしていることを意味します。比較の束。

簡単な修正として、この行を削除してください。ただし、これをフィールドとしてまったく持たず、戻り値を使用して比較の回数を伝えることで、これを修正したほうがよいと思います。これを行う 1 つの方法を次に示します。

  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 比較 = 0; int first1 = 最初、last1 = 中; int first2 = mid + 1, last2 = 最後; int temp[] = 新しい 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 に答える