python - 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)

司机

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

运行代码时出现错误，显示IndexError:列表分配索引超出范围

Answer 1

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

此 API 很经典，但选择不当，因为您无法指定空范围，而且不太规则，需要一些额外的调整(子数组大小的 + 1 和 - 1 ETC。)。您应该修改代码，使 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)