归并排序问题 - Python

Question

我的代码哪里出问题了？它只打印了部分向量的值。看起来在某个地方，while循环就停止了。我不明白为什么会这样。

def print_list(vect):
    for i in range(0, len(vect)):
        print(vect[i])

def merge_sort(vect):
    left = []
    right = []    
    result = []

    for i in range(0, int(len(vect)/2)):
        left.append(vect[i])
    for i in range(int(len(vect)/2), len(vect)):
        right.append(vect[i])

    left.sort()
    right.sort()
    i = 0
    j = 0

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

    print(len(result))
    return result

vect = [3, 1, 5, 7, 10, 2, 0]

vect = merge_sort(vect)

Answer 1

当左边或右边的列表中的元素用完时，while循环就会停止。这会导致未用完的列表中的所有元素没有被合并。

把你的代码改成这样：

def print_list(vect):
    for i in range(0, len(vect)):
        print(vect[i])

def merge_sort(vect):
    left = []
    right = []

    result = []
    for i in range(0, int(len(vect)/2)):
        left.append(vect[i])
    for i in range(int(len(vect)/2), len(vect)):
        right.append(vect[i])

    left.sort();
    right.sort();
    i = 0
    j = 0

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

    if i < len(left):
        result.extend(left[i:])
    else:
        result.extend(right[j:])

    print(len(result))
    return result

vect = [3, 1, 5, 7, 10, 2, 0]

vect = merge_sort(vect)
print vect

如果你在左边和右边的列表上使用排序方法，我有点困惑，为什么不直接在整个列表上使用呢？不过我想你有你的理由。:)

补充说明：我把整个代码块放在这里，方便你查看。当我运行这个代码时，它会输出[0, 1, 2, 3, 5, 7, 10]，这是正确的结果。

Answer 2

好吧，你的错误在于在你的 while 循环之后

while i < len(left) and j < len(right):
  ...

可能会出现（而且很可能会出现）i < len(left) 或者 j < len(right)，所以你需要把相应部分的后缀添加到结果中。这很简单，可以通过

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

解释：

想象一下合并的过程：一开始你有 i 和 j 都是 0，然后每一步你都会把其中一个向前移动。当你会停止呢？当其中一个到达末尾时。假设 i 到达了末尾。这样你就把整个左边的部分加到了结果里，但右边在 j 和 len(right) 之间还有一些元素，所以你也得把它们加到答案里。

题外话：

你正在实现归并排序，所以请使用

left = merge_sort( left )
right = merge_sort( right )

而不是

left.sort()
right.sort()

注意：你必须在合并函数的开头添加以下检查，以避免无限递归：

if len( vect ) == 1:
   return vect

另外在你的 print_list 函数中，你可以直接使用

print vect

或者至少

for x in vect
print x