Mergesort Python实现 [英] Mergesort Python implementation

问题描述

我见过很多Mergesort Python实现，我编写了以下代码。总体逻辑运行良好，但没有返回正确的结果。我如何修复它？

编码：

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

def mergesort(data):
    if len(data) < 2:
        return
    left = data[:len(data)//2]
    print(left)
    right = data[len(data)//2:]
    print(right)
    print("left only now")
    mergesort(left)
    print("right now")
    mergesort(right)
    return merge(left, right)

data = mergesort([1, 20, 30, 25, 8, 7, 9])

在主合并排序函数中，我认为最后一行不正确。

推荐答案

您调用的合并函数不修改其参数。相反，它返回一个新的排序列表。

简单的解决方法是：

def mergesort(data):
    if len(data) < 2:
        return data              # Fix1
    left = data[:len(data)//2]
    print(left)
    right = data[len(data)//2:]
    print(right)
    print("left only now")
    left = mergesort(left)       # Fix2
    print("right now")
    right = mergesort(right)     # Fix3
    return merge(left,right)

data = mergesort([1,20, 30, 25, 8, 7, 9])

这篇关于Mergesort Python实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！