1

次のマージソートは、Data Structures and Algorithm Analysis (Weiss) からのものです。私が疑問に思っているのはfor、マージ ステップの最後のループです。tmpArrayにコピーして戻さなければならないことは理解していますが、なぜ からコピーしarray、なぜ からにコピーしないのかわかりrightendません。誰か説明してくれませんか？i0tmpArray.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++。したがって、値を適切に書き戻すために、最後のloop はrightPos元の場所まで逆方向にカウントします. 開始しrightPosて順方向にカウントすると、間違ったインデックスに書き込んでしまいます.

そうは言っても、このようにする理由はありません。入力を破棄して元の値を回復するために追加の体操を行うよりも、新しい変数を宣言してそれらの値を変更する方が簡単です。

お役に立てれば！

于 2012-05-07T18:12:46.560 に答える