java - 字段变量产生与递归局部变量不同的结果

Question

我遇到了这个非常奇怪的问题，我不确定为什么。

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);

我不明白为什么。

Answer 1

使用类变量时，请考虑以下事项:

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);

因此，第二个 quickSort 被调用，其索引可能包含已排序的元素。因此比较的次数会比要求的多。

当您使用局部变量时，每个递归调用都有它自己的 pivLocation 变量，因此您不会遇到这个问题。