1

私はこの非常に奇妙な問題を抱えていましたが、その理由はわかりません。

public class QuickSort
{
  private int pivLocation;
  private void quickSort(Integer[] input, int low, int high)
  {
    if(low < high)
    {
      this.pivLocation = partition(input, low, high);
      quickSort(input, low, pivLocation-1);
      quickSort(input, pivLocation+1, high);
      Inversions.comparisons += high - low;
    }
  }
}

private int partition(Integer[] input, int low, int high)
{

        int arrLength = high - low;

        if(arrLength%2 == 0){

            int pivot = input[low];
        }
        else
        {
            int pivot = 1;
        }
    int i = low+1;
    for(int j=low+1; j<= high; j++ )
    {

        if(input[j]< pivot)
        {

            swap(input, j, i);
            i++;
        }
    }
    swap(input, low, i-1);

    return i-1;


}

これにより、まったく同じコードを作成する場合とは異なる比較カウントが得られますが、フィールド変数を使用する代わりに、pivLocationをローカル変数に変更します。

int pivLocation = partition(input, low, high);

理由がわかりません。

4

2 に答える 2

3

再帰のため。ローカル変数は、メソッドが呼び出されるたびに初期化されます。

あなたが持っているとき：

int var;
void mymethod() {
   mymethod();
}

var一度だけ初期化されます。

Wtih

void mymethod() {
   int var;
   mymethod();
}

varmymethod()変数スコープがメソッド内で制限されているため、が呼び出されるたびにが初期化（ゼロに設定）されます。

于 2013-02-17T13:52:15.793 に答える
3

クラス変数を使用する場合は、次の点を考慮してください。

pivLocation = partition(input,low,high);
// pivLocation changes in this function (specifically to a lower value)
quickSort(input, low, pivLocation-1);
// pivLocation is now lower than expected
quickSort(input, pivLocation+1, high);

したがって、2 番目quickSortは、既にソートされている要素を含む可能性のあるインデックスで呼び出されます。したがって、比較の数は必要以上に多くなります。

ローカル変数を使用する場合、再帰呼び出しごとに独自のpivLocation変数があるため、この問題は発生しません。

于 2013-02-17T13:54:21.923 に答える