Python 按索引递归归并排序

Question

我有一个关于 Python 版本的递归合并排序的问题。我完成了基本版本，仅由数组引用，现在正在研究索引版本。我会陷入无限循环，却又不知道自己哪里做错了。您介意分享一些想法吗？先感谢您。

成功和非索引版本：

def mergesort(x):

    # The base case is when the array contains less than 1 observation. 

    length = len(x)

    if length < 2:

        return x

    else:

        # Recursive case:merge sort on the lower subarray, and the upper subarray. 

        mid = (length) // 2

        lower = mergesort(x[:mid])

        upper = mergesort(x[mid:])

        # merge two subarrays.

        x_sorted = merge(lower, upper)

        return (x_sorted)

def merge(lower, upper):

    nlower = len(lower)

    nupper = len(upper)

    i, j, k = 0, 0, 0

    # create a temp array to store the sorted results

    temp = [0] * (nlower + nupper)

    # as the lower and upper are sorted, since the base case is the single observation. 

    # now we compare the smallest element in each sorted array, and store the smaller one to the temp array

    # repeat this process until one array is completed moved to the temp array 

    # store the other array to the end of the temp array 

    while i < nlower and j < nupper:

        if lower[i] <= upper[j]:

            temp[k] = lower[i]

            i += 1

            k += 1

        else:

            temp[k] = upper[j]

            j += 1

            k += 1

    if i == nlower:

        temp[i+j:] = upper[j:]

    else:

        temp[i+j:] = lower[i:]

    return temp 

预期结果：

x = random.sample(range(0, 30), 15)

mergesort(x)

[0, 1, 3, 6, 9, 10, 11, 13, 14, 17, 18, 20, 25, 27, 29]

但我会陷入索引版本的无限循环：

def ms(x, left, right):

    # the base case: right == left as a single-element array

    if left < right:

        mid = (left + right) // 2

        ms(x, left, mid)

        ms(x, mid, right + 1)

        m(x, left, mid, right)

    return m

def m(x, left, mid, right):

    nlower = mid - left

    nupper = right - mid + 1

    temp = [0] * (nlower + nupper)

    ilower, iupper, k = left, mid, 0

Answer 1

您的索引版本使用了令人困惑的约定，其中left是切片中第一个元素的索引，right也是最后一个元素的索引。这个约定需要容易出错+1/-1调整。你的问题是这样的：mid计算出来的是左半部分最后一个元素的索引，但你认为它mid是右半部分的第一个元素：2个元素的切片被分成一个带有0的元素和一个带有2的元素，因此无限递归。您可以通过更改ms(x, mid, right+1)为ms(x, mid+1, right)等来解决此问题。此外，m从功能中恢复ms是没有意义的。x如果有什么的话你应该回来。right将索引设置为最后一个元素之后的索引更不容易出错，就像 Python 中的范围说明符一样。这样就不会有混乱+1/-1调整。这是修改后的版本：def ms(x, left, right):&nbsp; &nbsp; # the base case: right - left as a single-element array&nbsp; &nbsp; if right - left >= 2:&nbsp; &nbsp; &nbsp; &nbsp; mid = (left + right) // 2&nbsp; # index of the first element of the right half&nbsp; &nbsp; &nbsp; &nbsp; ms(x, left, mid)&nbsp; &nbsp; &nbsp; &nbsp; ms(x, mid, right)&nbsp; &nbsp; &nbsp; &nbsp; m(x, left, mid, right)&nbsp; &nbsp; return xdef m(x, left, mid, right):&nbsp; &nbsp; nlower = mid - left&nbsp; &nbsp; nupper = right - mid&nbsp; &nbsp; temp = [0] * (nlower + nupper)&nbsp; &nbsp; ilower, iupper, k = left, mid, 0&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; while ilower < mid and iupper < right:&nbsp; &nbsp; &nbsp; &nbsp; if x[ilower] <= x[iupper]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp[k] = x[ilower]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ilower += 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; k += 1&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp[k] = x[iupper]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; iupper += 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; k += 1&nbsp; &nbsp; if ilower == mid:&nbsp; &nbsp; &nbsp; &nbsp; temp[k:] = x[iupper:right]&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; temp[k:] = x[ilower:mid]&nbsp; &nbsp; x[left:right] = temp&nbsp; &nbsp; return x您将调用为：x = random.sample(range(0, 30), 15)ms(x, 0, len(x))