在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 的意思是什么，以及如何得到相同的结果（这也是个不错的练习！）。