Python中的快速排序比较计数器

Question

我有一个完全可以运行的快速排序分区算法，现在我想在每次比较的时候加一个计数器。这个过程让我有点困惑。有没有什么建议可以告诉我应该把这个计数器放在哪里呢？

def partition(mylist, start, end):
    pos = start
    for i in range(start, end):
        if mylist[i] < mylist[end]:
            mylist[i],mylist[pos] = mylist[pos],mylist[i]
            pos += 1
    mylist[pos],mylist[end] = mylist[end],mylist[pos]
    return pos

def quicksort(mylist, start, end, c):
    if start < end:
        pos = partition(mylist, start, end)
        c= c+ (len(mylist) -1    )   
        quicksort(mylist, start, pos - 1, c)
        c= c+ (len(mylist) -1    )       
        quicksort(mylist, pos + 1, end, c)
        c= c+ (len(mylist) -1    )


count = (0)
quicksort(x, 0, len(x)-1, count)

这里的x指的是一个整数列表。

Answer 1

你只有两个地方需要明确比较，都是用if语句，你可以在这些行之前加一个计数器，比如：

counter = 0 # the global variable

def myfunc1():
    global counter
    counter = counter + 1
    if my < comparison:
         pass

def myfunc2():
    global counter
    counter = counter + 1
    if my < comparison:
         pass

print(counter)

这里没有算上for循环机制中的隐式比较，但我觉得这不是你想要做的。

这里有另一种有趣的方法，可以传递计数器信息，并避免使用全局变量：

def myfunc1():
    myfunc1.counter += 1
    if 2 < 1:
         pass

def myfunc2():
    myfunc2.counter += 1
    if 1 < 2:
         pass

myfunc1.counter = 0
myfunc2.counter = 0

for f in (myfunc1, myfunc2):
    print("{} had {} comparisons".format(f.__name__, f.counter))

编辑/备注：这里的一些答案使用了传递参数到每个函数中来跟踪计数器。这也是一种有效的方法，但我们其实需要一种更通用的方法（否则你会在很多情况下不停地传递计数器，这样很麻烦）。总结一下：

• 全局变量（不太好）
• 函数属性（不太好）
• 传递额外参数并返回额外参数（麻烦，但总体上更好）
• 实例变量，且你的函数是类的成员（但如果你不想使用对象呢？）
• 也许有一种更通用的方法，下面有工作示例：

注意，这里使用了装饰器，意味着你可以添加任意数量的像less_than这样的函数，而不需要让它们理解计数的要求。

def count(func):
    def inner(*args):
        inner.counter += 1
        return func(*args)
    inner.counter = 0
    return inner

@count
def less_than(op1, op2):
    return op1 < op2

def partition(mylist, start, end):
    pos = start
    for i in range(start, end):
        if less_than(mylist[i], mylist[end]):
            mylist[i],mylist[pos] = mylist[pos],mylist[i]
            pos += 1
    mylist[pos],mylist[end] = mylist[end],mylist[pos]
    return pos

def quicksort(mylist, start, end):
    if less_than(start, end):
        pos = partition(mylist, start, end)
        quicksort(mylist, start, pos - 1)
        quicksort(mylist, pos + 1, end)


x = [3, 2, 5, 1, 0]
quicksort(x, 0, len(x)-1)
print(x)
print(less_than.counter)

你还可以通过创建一个计数器类来进一步组织，这个类可以跟踪任意数量的函数及它们被调用的次数，并去掉函数属性，把数据存储在比如字典中。

Answer 2

def partition(mylist, start, end, count):
    pos = start
    for i in range(start, end):
        count += 1
        if mylist[i] < mylist[end]:
            mylist[i],mylist[pos] = mylist[pos],mylist[i]
            pos += 1
    mylist[pos],mylist[end] = mylist[end],mylist[pos]
    return pos, count

def quicksort(mylist, start, end, count):
    if start < end:
        pos, count = partition(mylist, start, end, count)        
        count = quicksort(mylist, start, pos - 1, count)
        count = quicksort(mylist, pos + 1, end, count)
    return count


x = [2,3,1]
count = quicksort(x, 0, len(x)-1, 0)
print x, count

当然可以！请把你想要翻译的内容发给我，我会帮你把它变得简单易懂。

Answer 3

为了进一步改进一些已有的答案，除非你想让这个算法变成尾递归（不过对于快速排序来说，这样做也没什么用），其实你不需要传入计数值。你只需要确保每次调用分区函数时，它都会返回它所进行的所有比较的数量，而每次调用快速排序函数时，它都会返回它自己或任何递归调用中进行的所有分区的数量。

另外，我们可以把快速排序的递归实现放到一个辅助函数里，然后再用一个简单的函数把它包裹起来，这样我们只需要传入一个列表，就不需要手动传入开始和结束的索引了。

这样实现后，我们就得到了以下内容：

def _partition(mylist, start, end):
    count = 0
    pos = start
    for i in xrange(start, end):
        count += 1
        if mylist[i] < mylist[end]:
            mylist[i], mylist[pos] = mylist[pos], mylist[i]
            pos += 1
    mylist[pos], mylist[end] = mylist[end], mylist[pos]
    return pos, count

def _quicksort(mylist, start, end):
    count = 0
    if start < end:
        pos, count = _partition(mylist, start, end)        
        count += _quicksort(mylist, start, pos - 1)
        count += _quicksort(mylist, pos + 1, end)
    return count

def quicksort(mylist, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(mylist) - 1
    return _quicksort(mylist, start, end)

x = [2,3,1]
count = quicksort(x)
print x, count