python - 在 Python 中查找合并和选择排序的交叉点

Question

对于作业，我必须在 Python 中实现合并和插入排序（此代码已提供给我们）。

但是，然后我必须使用该函数“运行实验”timeit来测试两种算法的运行时间，然后制作一个图表来确定它们的交叉点，或者当输入越过合并变得比插入更好的阈值时（提示中说明的内容的问题）。

这是我的代码：

import random
import timeit
import array

# Insertion sort routine
def insertion_sort(A):
    for k in range (1, len(A)): #from 1 to n-1
        curr = A[k] #currently inserting element
        j = k #find correct index j for current
        while j > 0 and A[j - 1] > curr:
            A[j] = A[j - 1]
            j -= 1
            A[j] = curr


# Merge sort routines
def merge(S1, S2, S):
    i = j = 0

    while i + j < len(S):
        if j == len(S2) or (i < len(S1) and S1[i] < S2[j]):
            S[i + j] = S1[i]
            i += 1
        else:
            S[i + j] = S2[j]
            j += 1

def merge_sort(S):
    n = len(S)
    if n < 2:
        return

    mid = n // 2

    S1 = S[0:mid]
    S2 = S[mid:n]

    merge_sort(S1)
    merge_sort(S2)
    merge(S1, S2, S)

# Benchmark code
S = array.array('B',(0,)*300)
A = array.array('b', (0,)*300)
print(timeit.timeit("merge_sort(S)", setup = "from __main__ import merge_sort, S", number = 1))
print(timeit.timeit("insertion_sort(A)", setup = "from __main__ import insertion_sort, A", number = 1))      

对于长度为 300 的数组。无论我将数组更改为什么大小，合并总是比插入好。

我在这里想念什么？我怎样才能解决这个问题？

标签： pythonarrayssortingmergesortinsertion-sort