按字符串长度排序的归并排序实现 - python

Question

我在Python中实现了一个我认为是归并排序的算法。之前我从来没有用过Python，所以我查阅了很多资料，使用了一些对我来说比较陌生的命令，以便更好地理解这个过程。

不过，我其实也从来没有实现过归并排序，所以我不确定自己是否真的做对了。如果有人能给我一些指导、建议或者纠正我的错误，我会非常感激。

这是我的合并方法：

def merge(left, right):
    result = []
    i, j = 0, 0
    while(i < len(left) and j< len(right)):
        if(len(left[i]) <= len(right[j])): 
            print(i)
            result.append(left[i])
            i=i+1
        else:
            result.append(right[j])
            j=j+1

    result += left[i:]
    result += right[j:]
    return result

同时，这是我的归并排序方法：

def mergesort(list):
    if len(list) < 2:
        return list
    else:
        middle = len(list) / 2
        left = mergesort(list[:middle])
        right = mergesort(list[middle:])
        return merge(left, right)

谢谢大家的帮助！ :)

Answer 1

你可以试试用 sorted() 这个函数，方法是这样的：

def len_cmp(x, y):
    return len(x) - len(y)

my_strings = ["hello", "foo", "bar", "spam"]
print sorted(my_strings, len_cmp)

Answer 2

不要把变量命名为“list”。这是Python中数组类型的名字，使用相同的名字会让人感到困惑。

当你在条件语句中返回值时，不需要把函数的其余部分放在一个else块里。

def mergesort(list):
    if len(list) < 2:
        return list
    middle = len(list) / 2
    left = mergesort(list[:middle])
    right = mergesort(list[middle:])
    return merge(left, right)

总体来说，这看起来还不错。

当然，除了练习之外，你应该使用list.sort或sorted()来排序。

a = ["abc", "de", "f", "ghijkl"]
print sorted(a, lambda a,b: cmp(len(a), len(b)))