如何计算快速排序中的比较次数

Question

所以我有一个完整的编写和工作代码可以快速排序，但是我没有返回排序列表，而是试图让它返回比较次数。我不确定应该在哪里计算比较的次数。任何帮助是极大的赞赏！

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark   #returns the sorted list

Answer 1

这两个循环是您实际比较数组值的唯一位置：

       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

因此您应该在两个循环中添加counter += 1。请记住将计数器初始化为0并将其声明为全局。

BTW，leftmark = leftmark + 1可以写为leftmark += 1这部分：

           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

不需要临时变量：

           alist[rightmark],alist[leftmark] = alist[leftmark],alist[rightmark]

Answer 2

我真的对代码感到困惑，因为对于一个简单的操作来说，这似乎很漫长。也许我听不懂，但这是一种简单的列表排序方式：

def sort_list(alist,start=None,end=None):
    if start and end:
        lst = list(alist[start:end])
    else:
        lst = list(alist)
    order = list(set(l))
    for i in lst:
        while lst.count(i) > 1:
            order.insert(order.index(i), i)
            lst.pop(lst.index(i,lst.index(i)+1))
    return order

# EXAMPLE
l = [5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5]

sort_list(l)          # returns [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
sort_list(l,3,len(l)) # returns [0, 1, 1, 2, 2, 3, 4, 5]

而且，您的函数似乎更适合于一类。如果您仍然需要一种方法来计算从初始清单到订购清单的变化，请发表评论。祝你好运