Python 中的合并排序 - `int` 对象不可迭代

Question

这是 Python 中的合并排序实现。调用 merge_arrays() 函数时出现错误 int object is not iterable。任何建议将不胜感激。

arr = [1,5,4,7,6,8,3,2,9]

def merge_arrays(_arr_left, _arr_right):
    sorted_arr = []
    left, right = 0, 0

    for i in range(0, len(arr)):
        if (_arr_left[left] < _arr_right[right]):
            sorted_arr.extend(_arr_left[left])
            left += 1
        else:
            print _arr_right[right], right
            sorted_arr.extend(_arr_right[right])
            right += 1

    return sorted_arr

def merge_sort(_arr):
    if (len(_arr) <= 1):
        return _arr

    _arr_left = merge_sort(_arr[:len(_arr)/2])
    _arr_right = merge_sort(_arr[(len(_arr)/2):])

    return merge_arrays(_arr_left, _arr_right)

try:
    merge = merge_sort(arr)
    print merge
except Exception as e:
    print e

Answer 1

那个特定的错误是因为你说的是 sorted_array.extend(_arr_left[left])。您要求 sorted_array 将 "iterable" _arr_left[left] 的每个元素附加到它。但是 _arr_left[left] 并不是真正可迭代的，它只是 _arr_left.

中索引 left 处的任何 int

如果您不 try 然后 except 并打印 Exception，您将看到一个完整的堆栈跟踪，它会告诉您哪一行是错误的。

  File "merge.py", line 27, in <module>
    merge = merge_sort(arr)
  File "merge.py", line 22, in merge_sort
    _arr_left = merge_sort(_arr[:len(_arr)/2])
  File "merge.py", line 22, in merge_sort
    _arr_left = merge_sort(_arr[:len(_arr)/2])
  File "merge.py", line 25, in merge_sort
    return merge_arrays(_arr_left, _arr_right)
  File "merge.py", line 9, in merge_arrays
    sorted_arr.extend(_arr_left[left])
TypeError: 'int' object is not iterable

所以你可以看到问题从第 9 行开始。你也可以在你认为异常出现到运行到 python debugger 之前插入 import pdb; pdb.set_trace() 并逐步完成你的程序的进展查看异常出现的位置。

Answer 2

在你的第 9 行中：

sorted_arr.extend(_arr_left[left])

sorted_arr 是一个 list
_arr_left 是一个 list
left 是一个 int

所以，问题是：

>>> a = [1,2,3,4]
>>> a.extend(5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'int' object is not iterable
>>>

解决方案：

您可以使用 list.append() 代替 extend()。

>>> a = [1,2,3,4]
>>> a.append(5)
>>> a
[1, 2, 3, 4, 5]
>>>

PS:您的代码可能还有其他问题。

Answer 3

正如其他答案提到的，您需要将 extent 更改为 append。但是，正如您在评论中所说，您收到 list index out of range 错误，因为您正在迭代 arr 的 size，即 9，但子数组的长度要短得多。尝试将合并两个数组的代码更改为以下内容。

while (len(_arr_left) > left) or (len(_arr_right) > right):
        if (len(_arr_left) > left) and (len(_arr_right) > right):
            if (_arr_left[left] < _arr_right[right]):
                sorted_arr.append(_arr_left[left])
                left += 1
            else:
                sorted_arr.append(_arr_right[right])
                right += 1
        elif (len(_arr_left) > left):
            sorted_arr.append(_arr_left[left])
            left += 1
        else:
            sorted_arr.append(_arr_right[right])
            right += 1

正如您在上面的代码中看到的，我们必须测试各种条件。如果两个子数组都包含元素，那么我们将它们相互比较，并根据值评估将 append 与 sorted_arr 进行比较。如果不是，那么我们 append 来自个人 sub-arrays 的值。如果您不使用 left 和 right，而是使用 pop 会更容易，这样您就不必一直跟踪 left 和 right

最后，here 是您代码的工作版本。你还需要修改 return merge_sort(...) 到 sorted_arr = merge_sort(...) return sorted_arr 所以它不会每次都打印 returns sorted_arr

Python 中的合并排序 - `int` 对象不可迭代

Merge sort in Python - `int` object is not iterable

python

algorithm

mergesort

所以，问题是：

解决方案：