计数比较不使用全局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在这种情况下意味着什么，以及如何获得相同的结果（这是一个很好的练习！）。