Mergesort递推

Question

有人能看一下下面的递归合并排序，并告诉我是否有任何改进吗？我主要感兴趣的要么是提高代码速度，要么是缩短代码。

def mergesort(alist):
    if len(alist) > 1:
        mid = len(alist)/2
        left = alist[:mid]
        right = alist[mid:]

        mergesort(left)
        mergesort(right)

        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] > right[j]:
                alist[k] = right[j]
                j = j + 1

            elif left[i] < right[j]:
                alist[k] = left[i]
                i = i + 1

            k = k + 1

        while i < len(left):
            alist[k] = left[i]
            i = i + 1
            k = k + 1

        while j < len(right):
            alist[k] = right[j]
            j = j + 1
            k = k + 1


A = [4, 3, 1, 2, 6, 8, 10]

mergesort(A)
print(A)

Answer 1

将一份清单切成一份副本，例如：

>>> a = list(range(10))
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> b = a[:5]
>>> b
[0, 1, 2, 3, 4]
>>> b[2] = 0
>>> b
[0, 1, 0, 3, 4]
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

因此，每次递归调用都是在传递列表之前创建一半的列表副本，这不是最好的时间利用。我认为传递整个列表是一种更好的方法，它只是传递对整个列表的引用，不涉及副本，并且有几个索引标记了您想要处理的范围：

def mergesort(alist, lo=0, hi=None):
    if hi is None:
        hi = len(alist)
    if hi - lo <= 1:
        return
    mid = lo + (hi - lo) // 2  # mid = (lo + hi) // 2 can overflow
    mergesort(alist, lo=lo, hi=mid)
    mergesort(alist, lo=mid, hi=hi)
    # Copy out the left side, which may be overwritten by the merge
    temp = alist[lo:mid]
    read_left = 0  # index into temp, copy of left subarray
    read_right = mid  # index into alist's right subarray
    write = lo  # index into alist
    while read_left < len(temp) and read_right < hi:
        if alist[read_right] < temp[read_left]:
            alist[write] = alist[read_right]
            read_right += 1
        else:
            alist[write] = temp[read_left]
            read_left += 1
        write += 1
    # Copy any unprocessed items in temp back to alist
    alist[write:write+len(temp)-read_left] = temp[read_left:]
    # Any unprocessed items in right subarray are already in place!
    # Nothing returned: the list gets sorted in-place

Answer 2

为什么不改变

while i < len(left) and j < len(right):
    if left[i] > right[j]:
        alist[k] = right[j]
        j = j + 1

    elif left[i] < right[j]:
        alist[k] = left[i]
        i = i + 1

    k = k + 1

至

while i < len(left) and j < len(right):
    if left[i] > right[j]:
        alist[k] = right[j]
        j = j + 1

    else:  // !! Note the 'else'
        alist[k] = left[i]
        i = i + 1

    k = k + 1

这样，您就不会“跳过”(可能)相同的元素。

编辑:更糟糕的是，如果在输入数组中添加任何重复元素，则实现将永远循环。