合并排序 Python 编码问题

Question

def merge(array1: list, array2: list) -> list:
    result = []

    i = j = 0
    while i < len(array1) and j < len(array2):
        if array1[i] < array2[j]:
            result.append(array1[i])
            i += 1
        else:
            result.append(array2[j])
            j += 1

    # When we run out of elements in either L or M,
    # pick up the remaining elements and put in A[p..r]
    if i < len(array1):
        result += array1[i:]
    if j < len(array2):
        result += array2[j:]

    return result


def merge_sort(array: list) -> None:
    # if hi > lo
    if len(array) > 1:
        mid = (len(array)) // 2
        l = array[:mid]
        r = array[mid:]
        merge_sort(l)
        merge_sort(r)
        array[:] = merge(l, r)
        
        print(array)

我的问题：首先是关于如果我更改 array[:] = merge(l, r) -> array = merge(l,r) 那么结果将一团糟。

array = merge(l,r)

另一个问题是为什么我不能直接使用代码（下面）。我必须要参考一些东西。

merge_sort(array[:mid])
merge_sort(array[mid:])
array[:] = merge(array[:mid], array[mid:])

Answer 1

对于第一个问题，将合并后的结果直接赋值给array只会使it指向新的列表。让我们做一个小实验来观察这个现象：

>>> ar = list(range(10))
>>> same_ar = ar
>>> ar = []       # make `ar` point to a new list
>>> same_ar       # not change
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> ar = same_ar
>>> ar[:] = []    # modify `ar` in place
>>> same_ar       # change
[]

对于第二个问题，你应该知道，在解决第一个问题的前提下，你的merge_sort函数是修改传入的列表，但是每次使用切片，你都会得到一份列表，这会导致函数对副本而不是原始列表进行排序。同样以小实验为例：

>>> ar = list(range(10, -1, -1))
>>> ar
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> half = ar[:5]     # a copy of first half of `ar`
>>> half
[10, 9, 8, 7, 6]
>>> half.sort()       # modify `half` in place
>>> half
[6, 7, 8, 9, 10]
>>> ar                # not change
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

合并排序 Python 编码问题

Merge Sort Python Coding issues

python

mergesort