計數比較quicksort沒有全局Python

Question

我有一個快速排序和計數比較的代碼，完美的工作。但每次我調用這個函數時，計數都會一次又一次地加起來。有什麼辦法可以避免這種情況？

count = 0 
def quicksort(A, left = None, right =None): 
    global count 
    if left is None: 
     left = 0 
    if right is None: 
     right = len(A) 
    if left >= right: 
     return 
    p =A[left] 

    i = left +1 
    for j in range(left+1,right): 
     if A[j] < p: 
      A[i] , A[j] = A[j], A[i] 
      i = i + 1 
    A[left] , A[i-1] = A[i-1], A[left] 
    quicksort(A,left,i-1) 
    count += i-1-left 
    quicksort(A,i,right) 
    count += right-i-1 

    return A,count+len(A) 

Answer 1

爲了使其與全球count工作，你需要把它遞歸的第一級復位。要做到這一點的方法之一是你實現移動到一個單獨的函數_quicksort自稱遞歸，以及調用之前重置計數器：

def quicksort(A): 
    global count 
    count = 0 
    return _quicksort(A) 

def _quicksort(A, left=None, right=None): 
    global count 
    ... 
    _quicksort(A,left,i-1) 
    ... 

此外，這簡化了您的主函數簽名爲quicksort最終用戶不真的需要知道left和right。現在

，最好不要使用全局變量，就好象它是一個不好的做法。然後，您需要以某種方式將上下文傳遞給_quicksort函數，以便知道要處理哪個計數器。所以，你就需要通過一些作爲一個參數：

def _quicksort(context, A, left=None, right=None): 
    ... 
    _quicksort(context, ...) 

例如，這context也能像{'count': 0}一本字典，然後可以爲context['count']訪問，也可以是一個對象使用context.count。請注意，在這種情況下，這是變得非常接近的類，其中的背景是對象本身和_quicksort將是一個類方法：

class _Quicksort(object): 
    count = 0 
    def _quicksort(self, A, left=None, right=None): 
     ... 
     self._quicksort(A, ...) 
     self.count += ... 

最後，對付上下文中遞歸函數的另一種常用的方法是傳遞和返回變量「按值」，如：

def _quicksort(count, other_context, A, left=None, right=None): 
    ... 
    count1, other_context1 = _quicksort(count, other_context, A, left, right) 
    ... 
    return count + count1, other_context 

但你最終會得到一個混亂的方法簽名，就必須搞清楚什麼count意味着在這種情況下，如何得到相同的結果（這是一個很好的鍛鍊！）。