计数比较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意味着在这种情况下，如何得到相同的结果（这是一个很好的锻炼！）。