字段變量產生與局部變量遞歸不同的結果

我有這個非常奇怪的問題，我不知道爲什麼。字段變量產生與局部變量遞歸不同的結果

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

我不明白爲什麼。

來源

2013-02-17 idipous

當使用類變量，考慮以下：

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-17 13:54:21 Dukeling

然而奇怪的是，排序正確完成。只有比較是錯誤的。如果pivotlocation不正確，排序也會失敗。不應該嗎？ – idipous 2013-02-17 14:03:19

@idipous從第一次遞歸調用中，'pivLocation'只能得到一個較小的值（從簡單的分析中很容易看到）。這意味着您將爲包含一些已排序數據的索引調用'quickSort'。因此排序應該是成功的。交換兩個遞歸調用應該導致排序失敗。 – Dukeling 2013-02-17 14:22:17

嗯，即使交換遞歸調用，它也不會失敗。它仍然正確排序。唯一錯誤的是比較。我的理解是，當你正確地說pivotlocation在第一次遞歸調用中發生了變化，但是當我調用第二個遞歸函數時，它被-1改變了，我加了1，並且因爲我實現了分區的方式，它不會使一個區別。 – idipous 2013-02-17 14:40:18

由於遞歸。每次調用方法時，局部變量都會被初始化。

當你有：

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

var只初始化一次。

Wtih

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

var被初始化（設置爲零），每個時間mymethod()被調用時，由於這樣的事實，該可變範圍的方法內的限制。

來源

2013-02-17 13:52:15 user000001

字段變量產生與局部變量遞歸不同的結果

回答

相關問題