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只初始化一次。

与

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

var每次mymethod()调用时都会被初始化（设置为零），因为变量范围在方法内是有限的。

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

因此，第二个quickSort被调用的索引可能包括已经排序的元素。因此，比较的次数将高于所需的次数。

当你使用一个局部变量时，每个递归调用都有它自己的pivLocation变量，所以你没有这个问题。

于 2013-02-17T13:54:21.923 回答