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
    
    while ilower < mid and iupper < right + 1:
        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+1]
    else:
        temp[k:] = x[ilower:mid]
    x[left:right+1] = temp
    return x

测试数据为：

x = random.sample(range(0, 30), 15)
ms(x, 0, 14)
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-59-39859c9eae4a> in <module>
      1 x = random.sample(range(0, 30), 15)
----> 2 ms(x, 0, 14)

... last 2 frames repeated, from the frame below ...

<ipython-input-57-854342dcdefb> in ms(x, left, right)
      3     if left < right:
      4         mid = (left + right)//2
----> 5         ms(x, left, mid)
      6         ms(x, mid, right+1)
      7         m(x, left, mid, right)

RecursionError: maximum recursion depth exceeded in comparison

您介意提供一些见解吗？谢谢。

Answer 1

您的索引版本使用了一个令人困惑的约定，其中 left 是切片中第一个元素的索引，而 right 是最后一个元素的索引。此约定需要 error-prone +1/-1 调整。你的问题是这样的： mid 计算的是左半部分最后一个元素的索引，但你认为 mid 是右半部分的第一个元素：2个元素的切片被分成一个是 0，一个是 2，因此无限递归。您可以通过将 ms(x, mid, right+1) 更改为 ms(x, mid+1, right) 等来解决此问题

此外，从函数 ms 重新调整 m 没有任何意义。如果有的话，你应该 return 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))

Python 递归合并按索引排序

Python recursive Merge Sort by index

python

recursion

mergesort