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

问题描述 投票:1回答:1
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                               
    for i in range(n - 1, -1, -1):
        A[0], A[i] = A[i], A[0]
        n -= 1
        k = 0
        while 2 * k + 1 < n:
            left, right = 2 * k + 1, 2 * k + 2
            if left < n and A[left] > A[k]:
                m = left
                Hc += 1
            else:
                m = k
                Hc += 1
            if right < n and A[right] > A[m]:
                m = right
                Hc += 1
            if m != k:
                A[k], A[m] = A[m], A[k]
                k = m
                Hs += 1
            else:
                break

#

def check_sorted(A):
    for i in range(n-1):
        if A[i] > A[i+1]: return False
    return True

#

#

Qc, Qs, Mc, Ms, Hc, Hs = 0, 0, 0, 0, 0, 0

n = int(input())
random.seed()
A = []
for i in range(n):
    A.append(random.randint(-1000,1000))
B = A[:]
C = A[:]

print("")
print("Quick sort:")
print("time =", timeit.timeit("quick_sort(A, 0, n-1)", globals=globals(), number=1))
print("  comparisons = {:10d}, swaps = {:10d}\n".format(Qc, Qs))
print("Merge sort:")
print("time =", timeit.timeit("merge_sort(B, 0, n-1)", globals=globals(), number=1))
print("  comparisons = {:10d}, swaps = {:10d}\n".format(Mc, Ms))

print("Heap sort:")
print("time =", timeit.timeit("heap_sort(C)", globals=globals(), number=1))
print("  comparisons = {:10d}, swaps = {:10d}\n".format(Hc, Hs))


assert(check_sorted(A))
assert(check_sorted(B))
assert(check_sorted(C))

我编写了代码,以3种排序方式告诉我们对列表大小n(数字输入)进行排序需要花费多少时间。但是,我发现我的结果出乎意料。

Quick sort:
time = 0.0001289689971599728
  comparisons =        474, swaps =        168

Merge sort:
time = 0.00027709499408956617
  comparisons =        541, swaps =         80

Heap sort:
time = 0.0002578190033091232
  comparisons =        744, swaps =        478

Quick sort:
time = 1.1767549149953993
  comparisons =    3489112, swaps =     352047

Merge sort:
time = 0.9040642600011779
  comparisons =    1536584, swaps =      77011

Heap sort:
time = 1.665754442990874
  comparisons =    2227949, swaps =    1474542

Quick sort:
time = 4.749891302999458
  comparisons =   11884246, swaps =     709221

Merge sort:
time = 3.1966246420051903
  comparisons =    3272492, swaps =     154723

Heap sort:
time = 6.2041203819972
  comparisons =    4754829, swaps =    3148479

如您所见,我的结果与我所学到的完全不同。您能告诉我为什么快速排序不是我的代码中最快的吗?以及为什么合并是最快的。

python sorting
1个回答
0
投票
[您看到的,如果枢轴是Aray的最小值或最大值,或接近于思维/最大值的某处,则在这种情况下(最坏的情况),快速排序的运行时间将为O(n ^ 2)。这是因为在每次迭代中,您都是通过仅分割一个元素来对arry进行分区。

为了获得O(n log n)的最佳快速排序性能,您的数据透视图应尽可能接近中值。为了增加这种情况的可能性,请考虑首先从数组中随机选择3个值,然后使用中位数作为枢轴。显然,您从初始选择中位数的值越多,数据透视越有效的可能性就越大,但是您要通过选择这些值开始来增加额外的移动,因此这是一个折衷。我想人们甚至可以准确地计算出应该选择多少个元素(相对于数组的大小)以达到最佳性能。

另一方面,与输入无关,合并排序始终具有O(n log n)顺序的复杂度,这就是为什么您在不同样本上获得一致结果的原因。

TL:DR我的猜测是输入数组的第一个元素非常接近该数组的最小值或最大值,并且最终成为您的快速排序算法的关键。

© www.soinside.com 2019 - 2024. All rights reserved.