python - 在 Python 中实现/运行合并排序

Question

我正在用 python 编写一个程序，我正在尝试实现合并排序算法(并使用名为 merge 的函数来处理合并步骤)，但出现以下错误。我将 L = [2, 6, 4, 8, 1] 传递给合并排序的参数:

>>> L = [2, 6, 4, 8, 1]
>>> mergeSort(L)
Traceback (most recent call last):
  File "<pyshell#1>", line 1, in <module>
    mergeSort(L)
  File "H:\CSIS 4014\WinPython-64bit-3.5.3.1Qt5\notebooks\sorts.py", line 19, in mergeSort
    mergeSort(left)
  File "H:\CSIS 4014\WinPython-64bit-3.5.3.1Qt5\notebooks\sorts.py", line 21, in mergeSort
    merge(L, left, right, p, q, r)
  File "H:\CSIS 4014\WinPython-64bit-3.5.3.1Qt5\notebooks\sorts.py", line 24, in merge
    left[len(left)+1] = 999999
IndexError: list assignment index out of range

下面是我的源代码:

def mergeSort(L) :
    p = 0
    r = len(L) - 1
    if p < r :
        q = math.floor((p + r) / 2)
        left = L[:q]
        right = L[q+1:]
        mergeSort(left)
        mergeSort(right)
        merge(L, left, right, p, q, r)

def merge(L, left, right, p, q, r) :
        left[len(left)+1] = 999999
        right[len(right)+1] = 999999
        i = 1
        j = 1
        k = p 
        for k in range(r) :
                if left[i] <= right[j] :
                        L[k] = left[i]
                        i = i + 1
                elif L[k] == right[j] :
                        j = j + 1

我正在尝试对子数组左侧和右侧的变量使用切片，并遵循我的教科书中的伪代码。我将不胜感激任何帮助!

Answer 1

left[len(left)+1] = 999999

这总是会出现错误...您专门尝试写入不存在的元素。列表的最后一个元素位于 left[len(left) - 1]。写入超出此范围的任何索引都是错误。

也许您想追加？

left.append(999999)