python - python 中合并排序的索引超出范围

Question

我正在开发一个项目，并尝试在 python 中实现合并排序，但我收到索引超出范围错误，因为我是新的 python sp 对 python 语法和内置函数不太了解

     def merge1(a,l,h):
        if l<h:
            mid=int((l+h)/2)
            left=a[:mid]
            right=a[mid:]
            merge1(left,l,mid)
            merge1(right,mid+1,h)
            mergesort(a,l,mid,h)
     def mergesort(a,l,mid,h):    
        i=l
        j=mid+1
        k=l
        b=[]
        while i<=mid and j<=h:
            if a[i]<=a[j]:
                b[k]=a[i]
                i+=1
            else:
                b[k]=a[j]
                j+=1
            k+=1    
        if i>mid:
            for x in mid(j,h):
                b[k]=a[x]
                k=k+1
        else:
            for x in range(i,mid):
                b[k]=a[x]
                i=i+1
        for i in range(0,k):
            a[k]=b[k]
      a=[9,1,45,99,98,56]
      merge1(a,0,len(a)-1)
      print(a)

    <ipython-input-71-e2786b6fbe02> in mergesort(a, l, mid, h)
     15     b=[]
     16     while i<=mid and j<=h:
---> 17         if a[i]<=a[j]:
     18             b[k]=a[i]
     19             i+=1

    IndexError: list index out of range

Answer 1

子数组的 Python 语法是 array[begin, end]，其中索引范围是从 begin 到 end-1(包括 end)(不包括 end)。索引的终止条件应该是 < 而不是 <=，例如 i < mid，而不是 i <= mid。

merge1 和 mergesort 的名称颠倒了。 mergesort()实际上是合并函数，merge1实际上是自上而下的递归合并排序函数。名称应该交换。

合并排序函数应该只创建包含数组和索引范围的调用堆栈。 left 和 right 应在合并函数中从数组“a”创建，然后在合并过程中合并回“a”。

对合并排序函数的初始调用应具有参数 (a, 0, len(a))

<小时/>

示例代码

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

a=[9,1,45,99,98,56]
mergesort(a,0,len(a))
print(a)