algorithm - 我的合并排序代码返回相同的输入数组

Question

以下是将枢轴集作为第一个元素的 Mergesort 代码。此代码为我生成了一个与输入相同的输出数组。

Python3代码:

def mergesort(array):
    length=len(array)
    if(length<=1):
        return (array)
    else:
        mid=length//2
        left=[]
        right=[]
        # print(mid)
        left=mergesort(array[0:mid])
        right=mergesort(array[mid:])
        # print(left, right)
        arr=merge(left,right)
        return (array)

def merge(left,right):

    # print(left, right)
    i=j=0
    # l=len(left+right)
    l1=len(left)
    l2=len(right)
    l=l1+l2
    arr=list()
    for k in range(l):
        if i == l1:
            arr.append(right[j])
            j+=1
        elif j == l2:
            arr.append(left[i])
            i+=1
        elif(left[i] > right[j]):
            arr.append(right[j])
            j=j+1
        elif (left[i] < right[j]):
            arr.append(left[i])
            i=i+1
        # print(array)
    return (arr)

array=list(map(int,input().split()))
# print(array)
print(mergesort(array))

这是我的程序截图:

Answer 1

代码中有两个错误:

首先，你在第 14 行有错别字:

def mergesort(array):
    #....
    arr=merge(left,right)
    return (arr) # Not return (array)

其次，您的代码不适用于特殊输入，因为您没有实现 <=或 >=进行合并操作时的情况。所以你的代码无法排序 2 5 3 5例如。要解决此问题:

def merge(left,right):
    # ...
    elif(left[i] > right[j]):
        arr.append(right[j])
        j=j+1
    elif (left[i] <= right[j]): # instead of <
        arr.append(left[i])
        i=i+1