1

我在我的算法书（Intro to algorithms 3rd edition Cormen）中阅读了合并排序（就地），我决定用 Python 实现它。问题是我找不到我做错了什么......我在 C++ 中看到了一些代码，但即使这样我也无法修复它。

这是我的代码：

def MERGE(A,start,mid,end):
    L=[0]*(mid - start + 1)
    for i in range(len(L) - 1):
        L[i] = A[start+i]
    L[len(L) - 1] = 100000 # centinel, (fix)
    R=[0]*(end - mid + 2)
    for j in range(len(R) - 1):
        R[j] = A[mid+j]

    R[len(R) - 1] = 100000
    i = 0
    j = 0
    k = start
    for l in range(k,end):
        if(L[i] < R[j]):
            A[l] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1   

def mergeSort(A,p,r):
    if p < r:
        mid = int((p+r)/2)
        mergeSort(A,p,mid)
        mergeSort(A,mid+1,r)
        MERGE(A,p,mid,r) 

A  = [20, 30, 15, 21, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)]

当我运行代码时，我遇到了一些索引问题：

File "myrealmerge.py", line 9, in MERGE
R[j] = A[mid+j]
IndexError: list index out of range

我知道这是一个“愚蠢的问题”，并且有一些相关的帖子，但我尝试了那里的建议，它对我不起作用......

谁能帮我？谢谢！

4

3 回答 3

7

此代码工作正常：

def MERGE(A,start,mid,end):
    L = A[start:mid]
    R = A[mid:end]
    i = 0
    j = 0
    k = start
    for l in range(k,end):
        if j >= len(R) or (i < len(L) and L[i] < R[j]):
            A[l] = L[i]
            i = i + 1
        else:
            A[l] = R[j]
            j = j + 1  

def mergeSort(A,p,r):
    if r - p > 1:
        mid = int((p+r)/2)
        mergeSort(A,p,mid)
        mergeSort(A,mid,r)
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))
print A

我试图最小化您的代码的更改。

祝你好运！

（添加）

您可以使用此代码检查分割过程。

def MERGE(A,start,mid,end):
    # Do nothing
    pass

def mergeSort(A,p,r):
    if r - p > 1:
        mid = int((p+r)/2)
        print A[p:mid],A[mid:r]
        mergeSort(A,p,mid)
        mergeSort(A,mid,r)
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))

结果如下：

[20, 30, 21, 15] [42, 45, 31, 0, 9]
[20, 30] [21, 15]
[20] [30]
[21] [15]
[42, 45] [31, 0, 9]
[42] [45]
[31] [0, 9]
[0] [9]

这就是我们想要的。但是，'mid+1' 会产生无效结果。这是测试代码：

def MERGE(A,start,mid,end):
    # Do nothing
    pass

def mergeSort(A,p,r):
    if r - p > 1:
        mid = int((p+r)/2)
        print A[p:mid],A[mid+1:r]    # Changed
        mergeSort(A,p,mid)
        mergeSort(A,mid+1,r)         # Changed
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))

结果：

[20, 30, 21, 15] [45, 31, 0, 9]
[20, 30] [15]
[20] []
[45, 31] [9]
[45] []

（添加）

这是使用“mid+1”的代码：

# New indexing function that includes the right index.
def get_partial_list(origin_list, left_index, right_index): # Added
    return origin_list[left_index:right_index+1]


def MERGE(A,start,mid,end):
    L = get_partial_list(A,start,mid)
    R = get_partial_list(A,mid+1,end)
    i = 0
    j = 0
    k = start
    for l in range(k,end+1):            # changed
        if j >= len(R) or (i < len(L) and L[i] < R[j]):
            A[l] = L[i]
            i = i + 1
        else:
            A[l] = R[j]
            j = j + 1  

def mergeSort(A,p,r):
    if r - p > 0:                          # changed
        mid = int((p+r)/2)
        mergeSort(A,p,mid)
        mergeSort(A,mid+1,r)             # changed
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)-1)                 # changed
print A

我添加了新的索引功能。这是您期望的代码吗？

于 2013-09-30T03:33:53.957 回答
1

lancif 和 krishna Prasad 提供的解决方案没有空间复杂度 O(1)。

这是 Py3 的就地合并排序算法，空间复杂度为 O(1)。主要功能sort_imerge使用 2 个辅助功能wmerge和wsort.

该解决方案基于讨论过的 C 代码： 其他 SO 主题和良好的 C 实现 您还可以 在此处找到带有文档测试的完整 Python 代码

def sort_imerge(Seq, l=0, u=None):
    """ Merge sorting, mutable input. 
    Input sequence changed in place. 

    Time: O(n * log n)
        log n -- levels
        n -- elements on each level must be merged

    Space (additional): O(1) 
        input changed in place

    Returns None

    """
    u = len(Seq) if u is None else u
    if  u - l > 1:
        m = l + (u - l) // 2
        w = l + u - m  
        wsort(Seq, l, m, w)
        while w - l > 2:
            n = w
            w = l + (n - l + 1) // 2
            wsort(Seq, w, n, l)
            wmerge(Seq, l, l + n - w, n, u, w)
        n = w
        while n > l: # fallback to insert sort
            for m in range(n, u):
                if Seq[m-1] > Seq[m]:
                    Seq[m-1], Seq[m] = Seq[m], Seq[m-1]
            n -= 1

def wmerge(Seq, i, m, j, n, w):
    """Merge subarrays [i, m) and [j, n) into work area w.
    All indexes point into Seq.
    The space after w must be enough to fit both subarrays.
    """
    while i < m and j < n:
        if Seq[i] < Seq[j]:
            Seq[i], Seq[w] = Seq[w], Seq[i]
            i += 1
        else:
            Seq[j], Seq[w] = Seq[w], Seq[j]
            j += 1
        w += 1
    while i < m:
        Seq[i], Seq[w] = Seq[w], Seq[i]
        i += 1
        w += 1
    while j < n:
        Seq[j], Seq[w] = Seq[w], Seq[j]
        j += 1
        w += 1

def wsort(Seq, l, u, w):
    """Sort subarray [l, u) and put reuslt into work area w.
    All indexes point into Seq.
    """
    if  u - l > 1:
        m = l + (u - l) // 2
        sort_imerge(Seq, l, m)
        sort_imerge(Seq, m, u)
        wmerge(Seq, l, m, m, u, w)
    else:
        while l < u:
            Seq[l], Seq[w] = Seq[w], Seq[l]
            l +=1
            w +=1
于 2019-06-16T15:21:05.827 回答
0

递归地将数组拆分为左右部分，然后根据您的要求将其合并，即ASC或DESC，检查以下代码：

def merge_sort(a):
    if len(a) <= 1:
        return a

    left = [];
    right = [];

    mid = len(a)/2

    left = a[0:mid]
    right = a[mid:(len(a))]

    print left
    print right
    #exit()

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    while len(left) > 0 and len(right) > 0:
        lv = left[0]
        rv = right[0]
        if lv <= rv:
            result.append(lv)
            left.pop(0)
        else:
            result.append(rv)
            right.pop(0)
    while len(left) > 0:
        result.append(left.pop(0))

    while len(right) > 0:
        result.append(right.pop(0))

    return result

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]

print A
print merge_sort(A)

为了理解我已经打印了中间分区数组，请查看输出：

[20, 30, 21, 15, 42, 45, 31, 0, 9]
[20, 30, 21, 15]
[42, 45, 31, 0, 9]
[20, 30]
[21, 15]
[20]
[30]
[21]
[15]
[42, 45]
[31, 0, 9]
[42]
[45]
[31]
[0, 9]
[0]
[9]
[0, 9, 15, 20, 21, 30, 31, 42, 45]

希望这将有助于您理解逻辑。

于 2016-07-19T03:09:21.513 回答