python中合并排序、插入排序和递归插入排序的运行时比较

Question

def merge_sort(unorderedList):
    if len(unorderedList) > 1:
        mid = len(unorderedList) // 2 
        left = unorderedList[:mid]
        right = unorderedList[mid:]
        merge_sort(left)
        merge_sort(right)
        i = 0
        j = 0
        k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                unorderedList[k] = left[i]
                i += 1
            else:
                unorderedList[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            unorderedList[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            unorderedList[k] = right[j]
            j += 1
            k += 1

def insertion_sort(list1):
    for i in range(1, len(list1)):
        key = list1[i]
        j = i - 1 
        while j >= 0 and list1[j] > key:
            list1[j + 1] = list1[j]
            j -= 1
        list1[j + 1] = key

def recursive_insertion_sort(arr, n):
    if n <= 1:
        return

    recursive_insertion_sort(arr, n-1)
    last = arr[n-1]
    j = n-2
     
    while j >= 0 and arr[j] > last:
        arr[j + 1] = arr[j]
        j -= 1
 
    arr[j + 1] = last

import time
import random
t0 = time.time()
insertion_sort([random.randint(-10000, 10000) for i in range(50000)])
t1 = time.time()
recursive_insertion_sort([random.randint(-10000, 10000) for i in range(50000)])
t2 = time.time()
merge_sort([random.randint(-10000, 10000) for i in range(50000)])
t3 = time.time()

print("insertion sort timer : ", t1 - t0)
print("recursive insertion sort timer : ", t2 - t1)
print("merge sort timer : ", t3 - t2)

我使用这三个函数来比较它们在5万成员随机列表中的运行时。

我在vscode中用python 3.10获得了这些时间

插入排序定时器: 78.13s

递归插入排序定时器: 0.068s

合并排序定时器:0.209 s

这是正确的吗？如果是的话，你能解释一下吗？

考虑到合并排序的顺序为O(nlogn)，插入排序顺序为O(n^2)，这是如何发生的？

编辑:添加用于时间测试的代码和方法。

Answer 1

由于这些函数正在执行"inplace“排序，因此我怀疑您的度量标准不是从相同的原始列表开始的。

例如，如果您首先在list A上测试A，然后在A上测试insertion_sort，那么第二种排序将得到一个已经排序的列表，该算法应该从中受益。这可能是在“插入排序”度量和“递归插入排序”度量之间发生的情况。

理论上，recursive_insertion_sort函数不应该能够对超过990项的列表进行排序。因此，我猜您更改了最大递归深度限制(如果没有，那么实验中有其他错误)

如果您独立地测试每一种排序(或者在原始列表的副本上)，您应该得到非常不同的结果。