Skip to main content
 首页 » 编程设计

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

2024年10月24日14mengfanrong

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

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 返回的内容:

>>> 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() 
>>> 

请您参考如下方法:

这个问题主要是因为行-

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

在这里,切片返回 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]