合并、堆和快速排序计数未正确显示

Question

import random, timeit

#Qucik sort

def quick_sort(A,first,last):

    global Qs,Qc

    if first>=last: return

    left, right= first+1, last

    pivot = A[first]

    while left <= right:

        while left <=last and A[left]<pivot:

            Qc= Qc+1

            left= left + 1

        while right > first and A[right] >= pivot:

            Qc=Qc+1

            right = right -1

        if left <= right:   

            A[left],A[right]=A[right],A[left]

            Qs = Qs+1

            left= left +1

            right= right-1

    A[first],A[right]=A[right],A[first]

    Qs=Qs+1

    quick_sort(A,first,right-1)

    quick_sort(A,right+1,last)

#Merge sort

def merge_sort(A, first, last): # merge sort A[first] ~ A[last]

    global Ms,Mc

    if first >= last: return

    middle = (first+last)//2

    merge_sort(A, first, middle)

    merge_sort(A, middle+1, last)

    B = []

    i = first

    j = middle+1

    while i <= middle and j <= last:

        Mc=Mc+1

        if A[i] <= A[j]:

            B.append(A[i])

            i += 1

        else:

            B.append(A[j])

            j += 1

    for i in range(i, middle+1): 

        B.append(A[i])

        Ms=Ms+1

    for j in range(j, last+1):

        B.append(A[j])

    for k in range(first, last+1): A[k] = B[k-first]

#Heap sort

def heap_sort(A):

    global Hs, Hc

    n = len(A)

    for i in range(n - 1, -1, -1):

        while 2 * i + 1 < n:

            left, right = 2 * i + 1, 2 * i + 2

            if left < n and A[left] > A[i]:

                m = left

                Hc += 1

            else:

                m = i

                Hc += 1

            if right < n and A[right] > A[m]:

                m = right

                Hc += 1

            if m != i:

                A[i], A[m] = A[m], A[i]

                i = m

                Hs += 1

            else:

                break                               

我编写的代码告诉我们用 3 种排序方式对列表大小 n（数字输入）进行排序需要多长时间。然而，我发现我的结果非常出乎意料。

Answer 1

我可以看到您正在选择数组的第一个元素作为快速排序中的枢轴。现在，考虑未排序数组元素的顺序。是随机的吗？你如何生成输入数组？您会看到，如果枢轴是数组的最小值或最大值，或者接近头脑/最大值的某个地方，那么在这种情况下（最坏情况）快速排序的运行时间将是 O(n^2 ）。这是因为在每次迭代中，您都通过仅断开一个元素来对数组进行分区。为了获得 O(n log n) 的最佳快速排序性能，您的枢轴应尽可能接近中值。为了增加这种情况的可能性，请考虑最初从数组中随机选择 3 个值，并使用中值作为枢轴。显然，您从最初选择中位数的值越多，您的枢轴越有效率的可能性就越大，但是您通过选择这些值开始添加额外的移动，所以这是一个权衡。我想人们甚至可以准确计算出相对于数组大小应该选择多少元素以获得最佳性能。另一方面，无论输入如何，合并排序总是具有 O(n log n) 顺序的复杂性，这就是为什么您在不同样本上得到一致结果的原因。TL：DR 我的猜测是输入数组的第一个元素非常接近该数组的最小值或最大值，它最终成为快速排序算法的关键。