Python 中的简单合并排序实现，存在类型问题

Question

我出于学习目的编写了一个简单的合并排序实现，但它不起作用。即使我一步步把代码过一遍，也不知道为什么会出现类型问题。这是我的代码：

def mergesort(seq):
    if len(seq)<2:
        return seq
    else:
        m = len(seq)//2
        return merge(mergesort(seq[:m]), mergesort(seq[m:]))

def merge(low, high):
    res = []
    i, j = 0, 0
    while i<len(low) and j<len(high):
        if low[i] <= high[j]:
            res.append(low[i])
            i = i+1
        else:
            res.append(high[j])
            j = j+1
    res.append(low[i:])
    res.append(high[j:])
    return res

这就是 python-shell returns:

>>> mergesort([5,8,1,3,99,5,2,3,4,9,7,5,8])
Traceback (most recent call last):
  File "<pyshell#22>", line 1, in <module>
    mergesort([5,8,1,3,99,5,2,3,4,9,7,5,8])
  File "D:\Documents\alp2\py2.py", line 6, in mergesort
    return merge(mergesort(seq[:m]), mergesort(seq[m:]))
  File "D:\Documents\alp2\py2.py", line 6, in mergesort
    return merge(mergesort(seq[:m]), mergesort(seq[m:]))
  File "D:\Documents\alp2\py2.py", line 6, in mergesort
    return merge(mergesort(seq[:m]), mergesort(seq[m:]))
  File "D:\Documents\alp2\py2.py", line 12, in merge
    if low[i] <= high[j]:
TypeError: unorderable types: int() <= list()
>>>

Answer 1

这个问题主要是因为行 -

res.append(low[i:])
res.append(high[j:])

此处，切片 returns lists ，然后将这些返回的列表附加到 res 列表中，并返回此 res 列表。因此，有时它会尝试将上面添加的 list 与导致您看到的问题的整数进行比较。

将列表中的元素添加为 res 列表的元素。您应该使用 list.extend() 而不是 .append() 。例子-

res.extend(low[i:])
res.extend(high[j:])

演示 -

>>> def mergesort(seq):
...     if len(seq)<2:
...         return seq
...     else:
...         m = len(seq)//2
...         return merge(mergesort(seq[:m]), mergesort(seq[m:]))
...
>>> def merge(low, high):
...     res = []
...     i, j = 0, 0
...     while i<len(low) and j<len(high):
...         if low[i] <= high[j]:
...             res.append(low[i])
...             i = i+1
...         else:
...             res.append(high[j])
...             j = j+1
...     res.extend(low[i:])
...     res.extend(high[j:])
...     return res
...
>>>
>>> mergesort([10,12,55,22,100])
[10, 12, 22, 55, 100]
>>> mergesort(list(range(100,50,-10)))
[60, 70, 80, 90, 100]

Python 中的简单合并排序实现，存在类型问题

simplest mergesort implementation in Python, having type troubles

python

sorting

mergesort