实现归并排序算法

Question

def merge(arr,l,m,h):
    lis = []
    l1 = arr[l:m]
    l2 = arr[m+1:h]
    while((len(l1) and len(l2)) is not 0):
        if l1[0]<=l2[0]:
            x = l1.pop(0)
        else:
        x = l2.pop(0)
        lis.append(x)
    return lis

def merge_sort(arr,l,h): generating them
    if l<h:
        mid  = (l+h)//2
        merge_sort(arr,l,mid)
        merge_sort(arr,mid+1,h)
        arr = merge(arr,l,mid,h)
    return arr

arr = [9,3,7,5,6,4,8,2]
print(merge_sort(arr,0,7))

谁能告诉我我的方法哪里出了问题？我只得到 [6,4,8] 作为答案。我试图理解算法并以我自己的方式实现逻辑。请帮忙。

Answer 1

几个问题：

当你认为 h 是子列表的 last 索引时，然后意识到在对列表进行切片时，第二个索引是一个在预期范围内。所以改变这个：

Wrong Right

l1 = arr[l:m] l1 = arr[l:m+1]

l2 = arr[m+1:h] l2 = arr[m+1:h+1]
作为 merge returns sub 列表的结果，您不应将其分配给 arr。 arr 应该是总列表，所以你应该只替换其中的一部分：
```
arr[l:h+1] = merge(arr,l,mid,h)
```
由于while循环要求两个列表都不为空，你仍然应该考虑after循环其中一个列表的情况仍然不为空：它的元素应该添加到合并结果中。所以将 return 语句替换为：
```
return lis + l1 + l2
```
不建议在 while 条件下将整数与 is 或 is not 进行比较。事实上，这个条件可以简化为：
```
while l1 and l2:
```

通过这些更改（以及正确的缩进），它将起作用。

进一步说明：

这个实现效率不高。 pop(0) 的时间复杂度为 O(n)。使用您在循环期间更新的索引，而不是真正从列表中提取值。

让 h 和 m 成为索引在它们关闭的范围之后而不是它们的索引更符合 pythonic它们关闭的范围内的最后一个元素。所以如果你那样做，那么上面的一些点将得到不同的解决。

更正实施

这是使用上述所有评论改编的代码：

def merge(arr, l, m, h):
    lis = []
    i = l
    j = m
    while i < m and j < h:
        if arr[i] <= arr[j]:
            x = arr[i]
            i += 1
        else:
            x = arr[j]
            j += 1
        lis.append(x)
    return lis + arr[i:m] + arr[j:h]

def merge_sort(arr, l, h):
    if l < h - 1:
        mid  = (l + h) // 2
        merge_sort(arr, l, mid)
        merge_sort(arr, mid, h)
        arr[l:h] = merge(arr, l, mid, h)
    return arr


arr = [9, 3, 7, 5, 6, 4, 8, 2]
print(merge_sort(arr,0,len(arr)))

实现归并排序算法

Implementing Merge Sort algorithm

python

sorting

algorithm

mergesort

进一步说明：

更正实施

Wrong	Right
`l1 = arr[l:m]`	`l1 = arr[l:m+1]`
`l2 = arr[m+1:h]`	`l2 = arr[m+1:h+1]`