python - 在 Python 中实现合并排序时遇到问题

Question

假设：数组的长度是 2 的幂（这里 2^3 = 16）

这是我正在使用的代码”

def merge_sort(arr):
   length = len(arr)
   if length <= 1:
      return arr
   else:
      mid = int(length/2)
      L, R = merge_sort(arr[:mid]), merge_sort(arr[mid:])
      return merge(L,R)

def merge(L,R):
   result = []
   low, high = 0, 2*max(len(L),len(R))
   i = j = 0
   for k in range(low,high):
     if L[i] < R[j]:
        result.append(L[i])
        i = i + 1
     else:
        result.append(R[j])
        j = j + 1
return result
   
>arr = [2, 40, 0, 66, 30, 33, 27, 69, 31, 82, 53, 26, 11, 29, 50, 59]
>merge_sort(arr)
IndexError: list index out of range

merge_sort 函数应该返回数组前半部分和后半部分的排序版本，而不是返回数组第一个元素的列表。不知道我做错了什么，请帮忙！

标签： pythonalgorithmsorting

Answer 1

当数组“L”中的所有元素合并时，索引i尝试访问“超出范围”。

我将您的代码修复如下：

def merge(L, R):
    result = []
    i = j = 0
    lenL, lenR = len(L), len(R)
    while i < lenL or j < lenR:
        if j >= lenR or (i < lenL and L[i] < R[j]):
            result.append(L[i])
            i = i + 1
        else:
            result.append(R[j])
            j = j + 1
    return result

它运作良好。