如何通過多個遞歸級別保留一個值？

我已經寫了一個快速排序程序，該程序計算按照升序對數組排序進行的交換次數。在這個程序中，我使用了一個全局變量來計算交換次數，因爲我無法確定如何通過多個遞歸級別保留值。我理解這個概念，即當函數自我摺疊時，通過傳遞多級遞歸來保留該值，但我顯然無法實現它。有人可以建議我這樣做嗎？如何通過多個遞歸級別保留一個值？

import java.util.Scanner; 

public class QuickSort { 

    // global variable for counting the quicksort shifts. 
    private static int swapCount = 0; 

    public static void main(String[] args) { 

     // scanning the values; 
     Scanner scan = new Scanner(System.in); 
     int N = scan.nextInt(); 
     int ar[] = new int[N]; 
     for(int i = 0 ; i < N ; i++){ 
      int value = scan.nextInt(); 
      ar[i] = value; 
     } 

     quickSort(ar, 0, ar.length-1); 
     System.out.println(swapCount); 

    } 

    //quickSort 
    public static void quickSort(int ar[], int start, int end){ 

     if(start<end){ 
      int pIndex = partition(ar, start, end); 
      quickSort(ar,start, pIndex-1); 
      quickSort(ar, pIndex+1, end); 
     } 
    } 

    // partition function 
    public static int partition(int ar[], int start, int end){ 
     int pivot = ar[end]; 
     int pIndex = start; 
     for (int i = start ; i < end ; i++){ 
      if(ar[i] < pivot){ 
       int temp = ar[i]; 
       ar[i] = ar[pIndex]; 
       ar[pIndex] = temp; 
       swapCount++; 
       pIndex++; 
      } 
     } 
     int temp = ar[end]; 
     ar[end] = ar[pIndex]; 
     ar[pIndex] = temp; 
     swapCount++; 
     return pIndex; 
    } 
}

來源

2017-03-08 gallactico

您可以將包含該值的對象傳遞給調用堆棧。這可能是一個專門的類，或者簡單的'int []'。 –

這是靜態（全局）變量可能有意義的一種情況。它允許你在不改變接口的情況下調用代碼（調用參數）。測試完成後，您可以輕鬆地將其刪除。正如所評論的，如果您確實想要將靜態變量作爲參數傳遞，您必須通過引用來傳遞它，而Java不支持基本類型，所以在下面的回答中，您必須創建一個類/對象才能通過引用。 – rcgldr

你所面臨的問題是，在基本類型如int的Java的值時，傳遞給函數，如果你的函數返回後看看他們的價值沒有反映他們提出的函數中的任何改變。解決這個問題的方法，即使它不一定是「好風格」，但是要將一個Class對象傳遞給該函數而不是一個原始對象，然後更改該函數內部的類對象的成員變量稍後在外面反映。

// in main() 
Integer nbrSwaps = new Interger(0); 
quickSort(ar, 0, ar.length-1, nbrSwaps); 

//quickSort 
public static void quickSort(int ar[], int start, int end, Integer swapCount) { 

    if(start<end){ 
    int pIndex = partition(ar, start, end, swapCount); 
    quickSort(ar,start, pIndex-1, swapCount); 
    quickSort(ar, pIndex+1, end, swapCount); 
    } 
} 

// partition function 
public static int partition(int ar[], int start, int end, Integer swapCount) { 
    ... as before ... 
}

來源

2017-03-08 23:08:20 geneSummons

如何通過多個遞歸級別保留一個值？

回答

相關問題