java - 如何计算归并排序中的比较次数？

Question

这是我的算法。我尝试将 numCompares 和 numMoves 放置在许多不同的位置，但我无法将其放在可以看到有效结果的位置。比较 = 2 个整数相互求值move = 元素已从其位置移动。所以交换就是 2 步。

 /**
   * Internal method that merges two sorted halves of a subarray.
   * @param a an array of Comparable items.
   * @param tmpArray an array to place the merged result.
   * @param leftPos the left-most index of the subarray.
   * @param rightPos the index of the start of the second half.
   * @param rightEnd the right-most index of the subarray.
   */
  private static void merge( int[] a, int[ ] tmpArray, int leftPos, int rightPos, int rightEnd )
  {
      int leftEnd = rightPos - 1; //left's last position
      int tmpPos = leftPos; //left-most
      int numElements = rightEnd - leftPos + 1;

      // Main loop
      while( leftPos <= leftEnd && rightPos <= rightEnd ){ //left and right pointers don't meet limit
        //numCompares = numCompares+1; //+2 because of 2 conditions
          if(a[leftPos] <= a[rightPos]){ //if left half element <= right half element
              tmpArray[ tmpPos++ ] = a[ leftPos++ ]; //copy left side elements
            }else{
              tmpArray[ tmpPos++ ] = a[ rightPos++ ]; //copy right side elements
        }
        numMoves++;
        numCompares = numCompares+2;
      }
      while( leftPos <= leftEnd ){    // Copy rest of first half while left is <= left end
          tmpArray[ tmpPos++ ] = a[ leftPos++ ];
          numCompares++;
          numMoves++;
      }
      while( rightPos <= rightEnd ){  // Copy rest of right half while right is < right-most
          tmpArray[ tmpPos++ ] = a[ rightPos++ ];
          numCompares++;
          numMoves++;
      }
      // Copy tmpArray back
      for( int i = 0; i < numElements; i++, rightEnd-- ){
          a[ rightEnd ] = tmpArray[ rightEnd ];
      }
  }

Answer 1

鉴于您想要最大精度，这将是我的方法:

/**
     * Internal method that merges two sorted halves of a subarray.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param leftPos the left-most index of the subarray.
     * @param rightPos the index of the start of the second half.
     * @param rightEnd the right-most index of the subarray.
     */
    private static void merge( int[] a, int[ ] tmpArray, int leftPos, int rightPos, int rightEnd )
    {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        while( leftPos <= leftEnd){
            numCompares++; // this is for leftPos <= leftEnd
            if(rightPos <= rightEnd) {
                numCompares++; // this is for rightPos <= rightEnd
                if (a[leftPos] <= a[rightPos]) { //if left half element <= right half element
                    tmpArray[tmpPos++] = a[leftPos++]; //copy left side elements
                } else {
                    tmpArray[tmpPos++] = a[rightPos++]; //copy right side elements
                }
                numMoves++;
                numCompares++; // this is for a[leftPos] <= a[rightPos]
            } else {
                break;
            }
        }
        numCompares++; //The while loop exited. This has happened because (leftPos <= leftEnd) or (rightPos <= rightEnd) failed.


        while( leftPos <= leftEnd ){    // Copy rest of first half while left is <= left end
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
            numCompares++;
            numMoves++;
        }
        numCompares++; //The while loop exited. This has happened because leftPos <= leftEnd failed.

        while( rightPos <= rightEnd ){  // Copy rest of right half while right is < right-most
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];
            numCompares++;
            numMoves++;
        }
        numCompares++; //The while loop exited. This has happened because rightPos <= rightEnd failed.


        // Copy tmpArray back
        // I assume that you don't want account for this operation in your measurements, since you didn't try to do it yourself?
        for( int i = 0; i < numElements; i++, rightEnd-- ){
            a[ rightEnd ] = tmpArray[ rightEnd ];
            // numCompares++; // This is for (i < numElements)
            // numMoves++;
        }
        // numCompares++; //The for loop exited. This has happened because (i < numElements) failed.
    }

如果您将其与渐近运行时间进行比较，请尝试逐渐增加大小并绘制测量结果。它不太可能适合小样本量。另外作为旁注，此代码计算数组中的写入量。如果您也想考虑读取，则需要在 numMoves 递增的地方添加两个而不是一个。

希望有帮助。祝你好运:)