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 mdef 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):

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

    if right - left >= 2:

        mid = (left + right) // 2  # index of the first element of the right half

        ms(x, left, mid)

        ms(x, mid, right)

        m(x, left, mid, right)

    return x

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

    nlower = mid - left

    nupper = right - mid

    temp = [0] * (nlower + nupper)

    ilower, iupper, k = left, mid, 0

    

    while ilower < mid and iupper < right:

        if x[ilower] <= x[iupper]:

            temp[k] = x[ilower]

            ilower += 1

            k += 1

        else:

            temp[k] = x[iupper]

            iupper += 1

            k += 1

    if ilower == mid:

        temp[k:] = x[iupper:right]

    else:

        temp[k:] = x[ilower:mid]

    x[left:right] = temp

    return x

您将调用为：

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

ms(x, 0, len(x))