为什么我的mergesort实现比冒泡排序和插入排序慢？

Question

我试图比较不同排序算法的时间（时间执行）的复杂性。我比较冒泡排序，插入排序，快速排序和融合排序（mergesort）。

我知道合并排序和快速排序比其他排序快，但是当我尝试比较这些方法的执行时间时，合并排序总是比其他排序花费更多的时间。我尝试了1000个元素到10,000个元素的列表。谁能告诉我为什么？

这里是我的归并代码：

def inserer(element, ls): 
    if ls==[]: 
     return [element] 
    elif element<= ls[0]: 
     return [element] + ls 
    else: 
     return [ls[0]] + inserer(element, ls[1:len(ls)]) 

def fusion(L1,L2): 
    if L1==[]: 
     return L2 
    elif L2==[]: 
     return L1 
    else: 
     return fusion(L1[1:len(L1)],inserer(L1[0], L2)) 


def triFusion (ls): 
    n=len(ls) 
    if n==0 or n==1: 
     return ls 
    else: 
     return fusion(triFusion(ls[0:n//2]),triFusion(ls[n//2:n])) 

Answer 1

我认为，这里的问题是，您的合并（融合）功能的方式，使得它更比它需要慢得多实施。这是你的代码：

def fusion(L1,L2): 
    if L1==[]: 
     return L2 
    elif L2==[]: 
     return L1 
    else: 
     return fusion(L1[1:len(L1)],inserer(L1[0], L2)) 

您的代码被反复服用L1的第一要素，做线性搜索，然后重复将其插入L2实现。在最坏的情况下，这种方法的时间复杂度为O（n ），因为第一次插入可能必须扫描n个元素以找到元素的正确位置，第二次插入可能必须扫描n + 1，第三个n + 2等等。

这打破了通常用mergesort获得的美好时间界限。通常，执行合并操作需要花费时间O（n）。由于归并排序使得在阵列上半两个递归调用一样大原，然后呼叫合并，归并的正常时间复杂度服从该复发：

T（N）= 2T（N/2）+ O（N ）

其中使用主定理解决O（n log n）。然而，在你的情况下，由于您的合并步骤花费的时间为O（n ），运行时是

T（N）= 2T（N/2）+ O（N ）

大师定理所说的解决O（n ）。换句话说，实现的时间复杂度是二次的，就像冒泡排序和插入排序一样，但由于它会对低效算法进行大量的调用，因此可能具有更高的常数因子。

要解决此问题，请尝试重写您的合并算法以线性时间运行。这可能会让你的代码运行得更快，速度更快。