我写了一个合并排序，但它最终是一个无限循环

Question

如果第一轮中断规则为真，则程序停止，但当它进入循环时，它永远不会停止

def mSort(liste):
    mSortHelp(liste, 0, len(liste)-1)
return liste

def mSortHelp(liste, first, last):
    if first < last:
        mid = (first+last)//2
        mSortHelp(liste, mid, last)
        mSortHelp(liste, fist, mid)
        merge(liste, first, mid, last)
    return liste

def merge(liste, first, mid, last):
    LeftList = liste[first:mid]
    RightList =lListe[mid:last+1]
    i=j=0
    for k in range (first, last):
        if LeftList[i] <= RightList[j]:
            liste[k] = LeftList[i]
            i+=1
        else:
            liste[k] = RightList[j]
            j+=1
    return liste

print(mSort(liste))

我希望有人可以帮助修复我的无限循环并给出一个排序列表（通过合并排序）。

Answer 1

首先，infinit循环是由if first < last:引起的，例如，如果first = 2，last = 3，它将永远不会突破它，如果你将它改为first < last-1，它将导致另一个问题，两个len列表将保持unsort。所以解决这个问题的最好方法是使最后没有包括，如[first, last)。

并且您的程序中还存在其他问题，例如语法问题，合并中的索引超出范围以及其他问题。我用评论修正了它们：

def mSort(liste):
    # change the last index
    # mSortHelp(liste, 0, len(liste) - 1)
    mSortHelp(liste, 0, len(liste))
    return liste

def mSortHelp(liste, first, last):
    # here is the key point causes infinit loop, such as first=2 last = 3
    # if first < last:
    if first < last - 1:
        mid = (first + last) // 2
        mSortHelp(liste, mid, last)
        mSortHelp(liste, first, mid)
        merge(liste, first, mid, last)
    return liste


def merge(liste, first, mid, last):
    LeftList = liste[first:mid]
    # change the last index
    # RightList = liste[mid:last + 1]
    RightList = liste[mid:last]
    i = j = 0

    print(LeftList, RightList)
    # here should be last, which means [first, last+1)
    for k in range(first, last):
        # here will cause "IndexError: list index out of range", if i or j reach the end
        # if LeftList[i] <= RightList[j]:
        if i < len(LeftList) and j < len(RightList):
            if LeftList[i] <= RightList[j]:
                liste[k] = LeftList[i]
                i += 1
            else:
                liste[k] = RightList[j]
                j += 1
        # when one list reach the end  
        else:
            if i < len(LeftList):
                liste[k] = LeftList[i]
                i += 1
            else:
                liste[k] = RightList[j]
                j += 1
    print(liste[first: last])
    # return is not necessary here, has been changed by parameter reference
    # return liste

希望对您有所帮助，并在您有其他问题时发表评论。 :)

Answer 2

到达任一子列表末尾的示例代码在主合并循环中处理，然后是中断（而不是在循环之后处理副本）。

def mergesort(a,beg,end):
    if (end-beg) > 1:
        mid=(beg+end)//2
        mergesort(a,beg,mid)
        mergesort(a,mid,end)
        merge(a,beg,mid,end)
def merge(a,beg,mid,end):
    left = a[beg:mid]
    right = a[mid:end]
    i = 0
    j = 0
    k = beg   
    while True:
        if left[i] <= right[j]:
            a[k] = left[i]
            i += 1
            k += 1
            if(i < len(left)):
                continue
            a[k:end] = right[j:len(right)]
            break
        else:
            a[k] = right[j]
            j += 1
            k += 1
            if(j < len(right)):
                continue
            a[k:end] = left[i:len(left)]
            break