合并排序 python IndexError

Question

在我使用 python 的合并排序实现中，运行发生错误的时间为

IndexError: list assignment index out of range

代码如下：

#merge
def merge(array, low, mid, high):
   n1 = mid - low + 1
   n2 = high - mid
   ll = [] * n1
   rr = [] * n2
   for i in range(n1):
      ll[i] = array[low + i]
   for j in range(n2):
      rr[j] = array[mid + 1 + j]

   (i, j) = (0, 0)
   k = low

   while i < n1 and j < n2:
      if ll[i] <= rr[j]:
         array[k] = ll[i]
         i = i + 1
      else:
         array[k] = rr[j]
         j = j + 1
   k = k + 1
   #for remaining members of the lists
   while i < n1:
      array[k] = ll[i]
      i = i + 1
      k = k + 1                

   while i < n2:
      array[k] = rr[j]
      j = j + 1
      k = k + 1

归并排序方法

def mergesort(array, low, high):
   if low < high:
      mid = low + (high - low) // 2

      #recurrence
      mergesort(array, low, mid)
      mergesort(array, mid + 1, high)
      merge(array, low, mid, high)

driver

array = [ 74, 32, 89, 55, 21, 64 ]
mergesort(array, 0, len(array))

虽然运行正在使用代码，但我收到一个错误 IndexError: list assignment index out of range

Answer 1

您的代码中有一些错误，修复后的版本如下所示（固定行已注释）：

合并

def merge(array, low, mid, high):
    n1 = mid - low + 1
    n2 = high - mid
    ll = [0] * n1  # here
    rr = [0] * n2  # here

    for i in range(n1):
        ll[i] = array[low + i]
    for j in range(n2):
        rr[j] = array[mid + 1 + j]

    i, j = 0, 0
    k = low

    while i < n1 and j < n2 :
        if ll[i] <= rr[j]:
           array[k] = ll[i]
           i += 1
        else:
           array[k] = rr[j]
           j += 1
        k += 1
    while i < n1:
       array[k] = ll[i]
       i += 1
       k += 1

    while j < n2:  # here
      array[k] = rr[j]
      j += 1
      k += 1

合并排序

def mergesort(array, low, high):
   if low < high:
        mid = (low + (high - 1)) // 2  # here

        mergesort(array, low, mid)
        mergesort(array, mid + 1, high)
        merge(array, low, mid, high)

最后的函数调用：

array = [74 , 32 , 89 , 55 , 21 , 64]
mergesort(array , 0 , len(array) - 1)  # here

Answer 2

您将数组的长度作为第二个参数传递给 merge，但 merge 函数似乎期望要排序的范围中最后一个元素的索引。

这个 API 很经典，但选择不当，因为你不能指定一个空范围，而且它不太规则，需要一些额外的调整（+ 1 和 - 1 子数组大小等。 ).您应该修改代码，使 high 成为第一个元素的索引在要排序的范围之后。

merge函数还有其他问题：

子数组大小的计算不正确
你在 while 循环外递增 k：k = k + 1 应该递增到更深的层次。
最后一个循环应该使用 j 而不是 i 作为索引。
此实现使用递归，而不是递归

这是修改后的版本：

def merge(array, low, mid, high):
   n1 = mid - low
   n2 = high - mid
   ll = [] * n1
   rr = [] * n2
   for i in range(n1):
      ll[i] = array[low + i]
   for j in range(n2):
      rr[j] = array[mid + j]

   i = 0
   j = 0
   k = low

   while i < n1 and j < n2:
      if ll[i] <= rr[j]:
         array[k] = ll[i]
         i = i + 1
      else:
         array[k] = rr[j]
         j = j + 1
      k = k + 1

   #copy the remaining members of the lists
   while i < n1:
      array[k] = ll[i]
      i = i + 1
      k = k + 1                

   while j < n2:
      array[k] = rr[j]
      j = j + 1
      k = k + 1  

def mergesort(array, low, high):
   if high - low > 1:
      mid = low + (high - low) // 2

      #recursion
      mergesort(array, low, mid)
      mergesort(array, mid, high)
      merge(array, low, mid, high)

合并排序 python IndexError

merge sort in python IndexError

python

mergesort

index-error