在python中实现归并排序时出现错误

Question

我正在尝试在 python 中实现合并排序，如下所示：

def MergeSortTopdown(list_n):

     #Base condition to stop recursion

    if len(list_n) == 1:

        return list_n

    else:

        mid = int(len(list_n)/2)

        first_half = list_n[:mid]

        second_half = list_n[mid:]

        MergeSortTopdown(first_half)

        MergeSortTopdown(second_half)

        i = 0

        j = 0 

        n = len(list_n)

        for k in range(n):

            if j >= len(first_half) and i < len(second_half):

                list_n[k] = first_half[i]

                i += 1 

            if i >= len(first_half) and j < len(second_half): 

                list_n[k] = second_half[j]

                j += 1

            if i < len(first_half) and j < len(second_half):

                if first_half[i] > second_half[j]:

                    list_n[k] = second_half[j]

                    j += 1   

                elif second_half[j] > first_half[i]:

                    list_n[k] = first_half[i]

                    i += 1

                elif second_half[i] == first_half[j]:

                    list_n[k] = first_half[i]

                    if i>j:

                        i += 1

                    else:

                        j += 1

    return list_n

当我用已经排序的列表进行测试时，这似乎是合理的。但是，当我运行时，会出现此错误：

MergeSortTopdown([3,4,6,7,1,8,56,112,67])

Traceback (most recent call last):

  File "<ipython-input-11-29db640f4fc6>", line 1, in <module>

    MergeSortTopdown([3,4,6,7,1,8,56,112,67])

  File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 13, in MergeSortTopdown

    MergeSortTopdown(second_half)

  File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 13, in MergeSortTopdown

    MergeSortTopdown(second_half)

  File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 19, in MergeSortTopdown

    list_n[k] = first_half[i]

IndexError: list index out of range

你能告诉我我的代码有什么问题吗，有什么办法可以改进我的代码。先感谢您

Answer 1

您试图引用列表末尾之后的元素。我print在您的代码中添加了一些简单的语句：&nbsp; &nbsp;for k in range(n):&nbsp; &nbsp; &nbsp; &nbsp; print("LOOP TOP", k, first_half, second_half, list_n)&nbsp; &nbsp; &nbsp; &nbsp; if j >= len(first_half) and i < len(second_half):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print("TRACE", list_n, k, "\t", first_half, i)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; list_n[k] = first_half[i]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i += 1然后我将输入列表缩短为[8,56,112,3,67].输出：LOOP TOP 0 [8] [56] [8, 56]LOOP TOP 1 [8] [56] [8, 56]LOOP TOP 0 [3] [67] [3, 67]LOOP TOP 1 [3] [67] [3, 67]LOOP TOP 0 [112] [3, 67] [112, 3, 67]LOOP TOP 1 [112] [3, 67] [3, 3, 67]TRACE [3, 3, 67] 1&nbsp; &nbsp;[112] 0LOOP TOP 2 [112] [3, 67] [3, 67, 67]TRACE [3, 67, 67] 2&nbsp; &nbsp; &nbsp; [112] 1接下来是您遇到的崩溃。first_half[1]当只有一个元素 0 时，您尝试获取。分析您有三个连续的if语句来检查列表边界：&nbsp; &nbsp; &nbsp; &nbsp; if j >= len(first_half) and i < len(second_half):&nbsp; &nbsp; &nbsp; &nbsp; if i >= len(first_half) and j < len(second_half):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; if i < len(first_half) and j < len(second_half):你必须i和j在第一检查切换：i是first_half下标。此更改修复了合并：&nbsp; &nbsp; &nbsp; &nbsp; if i < len(first_half) and j >= len(second_half):建议您的部分问题是您的合并逻辑过于复杂。在循环的主要部分，您有一个单一的值检查：将较低的列表头移动到合并的列表中。在两个索引都在范围内时执行此操作。然后，当一个索引到达其列表的末尾时，退出循环并添加另一个列表的剩余元素。使用extend方法。所以 ...while i < len(first_half) and j < len(second_half):&nbsp; &nbsp; if first_half[i] < second_half[j]:&nbsp; &nbsp; &nbsp; &nbsp; # move smaller element to list_n;&nbsp; &nbsp; &nbsp; &nbsp; # increment i or j as needed&nbsp; &nbsp; k += 1# One of these will be an empty operation.list_n.extend(first_half[i:])list_n.extend(second_half[j:])

Answer 2

要解决IndexError：您在合并排序的“合并步骤”中检查的第一种情况——如果您已经合并了列表中的所有元素second_half——具有两个列表的名称first_half并second_half切换。取而代之的是：if j >= len(first_half) and i < len(second_half):&nbsp; &nbsp; list_n[k] = first_half[i]&nbsp; &nbsp; i += 1&nbsp;你应该有这个：if j >= len(second_half) and i < len(first_half):&nbsp; &nbsp; list_n[k] = first_half[i]&nbsp; &nbsp; i += 1这将正确检查上面指定的条件。为什么会这样：您收到 an 的原因IndexError是因为您在尝试调用first_half[i]之前没有正确确认这i是列表中的有效索引first_half。