合并排序的 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）。索引的终止条件应该是 < 而不是 <=，例如 i < mid，而不是 i <= mid.

merge1和mergesort的名字颠倒了。 mergesort()其实就是merge函数，而merge1其实就是自上而下递归的mergesort函数。应该交换名称。

合并排序函数应该只创建包含数组和索引范围的调用堆栈。 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)

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

Index out of range in python for mergesort

python

sorting

mergesort

python-3.x

index-error