1 
def merge (seq, p, q, r):
    # n1: length of sub-array [p..q]
    n1 = q - p + 1
    # n2: length of sub-array [q+1 ..r]
    n2 = r - q
    # Left and Right arrays
    left_arr = [] 
    right_arr = []
    for i in xrange(0, n1):
        left_arr.append( seq[p+i] )
    for j in xrange(0, n2):
        right_arr.append( seq[q+j+1] )

    j=0
    i=0
    for k in xrange(p,r+1):
        if left_arr[i]<= right_arr[j]:
            seq[k]=left_arr[i]
            i+=1
        else:
            seq[k]=right_arr[j]
            j+=1
    return seq

s = [2,4,5,7,1,2,3,6]
p = 0
q = 3
r = 7
print merge(s,p,q,r)

这个怎么运作：

  1. 采用未排序的序列 s 以及必须合并序列的索引号。（p=初始，r=最终，q=中间）

  2. 现在，left_arr 和 right_arr 分别是 [p,q], [q+1, r]

  3. 我们取 left_arr 和 right_arr 初始值 (i=0, j=0)。我们遍历序列 seq...

  4. 在迭代时，我们将 seq 的值替换为排序后的值......

上面的函数能够排序到最后一个数字“7”..最后，它显示“IndexError”。我可以使用异常处理来捕获并修复它，但我认为......对于合并排序，它太多了......任何人都可以帮助我尽可能简单地修复代码。

我正在学习算法..（以下书籍：Thomas H. Cormen 的算法简介）

4

3 回答 3

1

问题是在最后一次迭代中 i 将等于 4 并且您试图访问不存在的 left_arr[5] 。当 i 或 j 大于相应数组的大小时，您应该添加停止条件，然后将另一个数组中的所有剩余元素添加到 seq。

这是一个有效的代码：

def merge (seq, p, q, r):
    # n1: length of sub-array [p..q]
    n1 = q - p + 1
    # n2: length of sub-array [q+1 ..r]
    n2 = r - q
    # Left and Right arrays
    left_arr = seq[p:n1] #here 
    right_arr = seq[n1:r+1]  #here
    j=0
    i=0
    for k in xrange(p, r+1):
        if left_arr[i]<= right_arr[j]:
            seq[k]=left_arr[i]
            i+=1
            if i > n1-1: #here
                break
        else:
            seq[k]=right_arr[j] #here
            j+=1
            if j > n2-1:
                break
    if i >= len(left_arr): #from here down
        seq[k+1:] = right_arr[j:]
    elif j >= len(right_arr):
        seq[k+1:] = left_arr[i:]

    return seq

s = [2,4,5,7,1,1,1,1]
p = 0
q = 3
r = 7
print merge(s,p,q,r)

我已经用注释标记了我编辑你的代码的地方。

于 2012-09-28T14:38:21.517 回答
1

您的代码的问题在于您正在循环xrange(p, r+1)，因此在某些迭代中的循环期间，iorj的值可能等于len(left)or的值，最终len(right)导致。IndexError

def merge(seq,p,q,r):
    left=seq[p:q+1]       #a better way to fetch the list
    right=seq[q+1:]       
    i=0
    j=0
    #you shuldn't loop over the length of seq as that might make the value of either i or j
    # greater than the length of left or right lists respectively.
    # so you should only loop until one of the lists is fully exhausted

    while i<len(left) and j<len(right):
        if left[i] <= right[j] :
            seq[i+j]=left[i]
            i+=1
        else:
            seq[i+j]=right[j]
            j+=1

    #now the while loop is over so either right or left is fully traversed, which can be
    #find out my matching the value of j and i with lenghts of right and left lists respectively

    if j == len(right):
        seq[i+j:]=left[i:]  #if right is fully traversed then paste the remaining left list into seq
    elif i==len(left):      #this is just vice-versa of the above step
        seq[i+j:]=right[j:] 
    print seq

s = [2,4,5,7,1,2,3,6]
p = 0
q = 3
r = 7
merge(s,p,q,r)

输出：

[1, 2, 2, 3, 4, 5, 6, 7]
于 2012-09-28T15:11:23.833 回答
0

left_arr您在迭代和时没有检查数组索引right_arr。当另一个数组结束时，您应该合并任一数组的左侧部分。

for k in xrange(p,r+1):
    if left_arr[i]<= right_arr[j]:
        seq[k]=left_arr[i]
        i+=1
    else:
        seq[k]=right_arr[j]
        j+=1

    # --------------- add this ----------------
    # if any array ends, merge the left elements of the other array
    if i >= len(left_arr):
        seq[k:] = right_arr[j:]
        break
    elif j >= len(right_arr):
        seq[k:] = left_arr[i:]
        break
    # --------------- end ----------------
return seq
于 2012-09-28T14:49:33.917 回答