1

以下合并排序来自数据结构和算法分析(Weiss)。我想知道的是for合并步骤的最后一个循环。我知道我们必须复制tmpArray回array，但我不明白为什么我们这样做 from rightend，以及为什么我们没有igo from 0to tmpArray.size。有人可以解释一下吗？

public static void mergeSort( Comparable [ ] a )
{
  Comparable [ ] tmpArray = new Comparable[ a.length ];
  mergesort( a, tmpArray, 0, a.length - 1 );
}

public static void mergesort( Comparable [ ] a, Comparable [ ] tmpArray,
int left, int right )
{
  if( left < right ) {
    int center = ( left + right ) / 2;
    mergesort( a, tmpArray, left, center );
    mergesort( a, tmpArray, center + 1, right );
    merge( a, tmpArray, left, center + 1, right );
  }
}

public static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
int leftPos, int rightPos, int rightEnd )
{

  int leftEnd = rightPos - 1;
  int tmpPos = leftPos;
  int numElements = rightEnd - leftPos + 1;

  while( leftPos <= leftEnd && rightPos <= rightEnd )
    if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
      tmpArray[ tmpPos++ ] = a[ leftPos++ ];
    else
      tmpArray[ tmpPos++ ] = a[ rightPos++ ];

  while( leftPos <= leftEnd ) // Copy rest of first half
    tmpArray[ tmpPos++ ] = a[ leftPos++ ];

  while( rightPos <= rightEnd ) // Copy rest of right half
    tmpArray[ tmpPos++ ] = a[ rightPos++ ];

  for( int i = 0; i < numElements; i++, rightEnd-- )
    a[ rightEnd ] = tmpArray[ rightEnd ]; // Copy tmpArray back
}
4

1 回答 1

1

我认为这样做的主要原因是因为 的值rightPos，即子数组开始的位置，已被内部循环破坏性地修改（注意使用rightPos++。因此，为了正确写回该值，最后一个循环倒数到rightPos原来的位置。如果它只是开始rightPos并向前计数，它将写入错误的索引。

也就是说，我认为没有任何理由这样做。只声明新变量并修改这些值会更容易，而不是破坏输入并做额外的体操来恢复原始值。

希望这可以帮助！

于 2012-05-07T18:12:46.560 回答