将排序数组合并为单个排序数组：Python

Question

我想把两个已经排好序的数组合并成一个。我正在用归并排序来实现这个目的。

错误提示：IndexError: 列表索引超出范围

我手动检查了一下，没发现数组超出范围的地方。如果我错了，请纠正我。

def merging(list1, list2):
    m = len(list1)
    n = len(list2)
    val = m+n
    j, k =  0, 0
    new =[]
    for i in range(val):
        if j<m and k<n:
           if list1[j] < list2[k]:
              new.append(list1[j])
              j += 1
           else:
              new.append(list2[k])     
              k += 1

       elif j==m:
          while i<m+n:
            new.append(list2[k])
            k += 1
            i += 1
       else:
        while i<m+n:
            new.append(list1[j])
            j += 1
            i += 1

print 'sorted array is:', new

if __name__ == '__main__':
    print 'Enter list 1'
    l1 = raw_input()
    list1 = map(int, l1.split())
    print 'Enter list 2'
    l2 = raw_input()
    list2 = map(int, l2.split())
    merging(list1,list2)

补充说明：我不想使用任何内置函数，比如sort()

Answer 1

这里有一个版本，它返回一个生成器，并且可以与所有可迭代的对象一起使用：

def merge(g1, g2):
    i1, i2 = iter(g1), iter(g2)
    e1, e2 = None, None
    try:
        e1 = next(i1)
        e2 = next(i2)
        while True:
            if e1 < e2:
                yield e1
                e1 = None
                e1 = next(i1)
            elif e2 < e1:
                yield e2
                e2 = None
                e2 = next(i2)
            else:
                yield e1
                yield e2
                e1, e2 = None, None
                e1 = next(i1)
                e2 = next(i2)
    except(StopIteration):
        for ix, ex in ((i1, e1), (i2, e2)):
            if ex != None:
                yield ex
                for e in ix:
                    yield e

Answer 2

在编程中，有时候我们会遇到一些问题，可能会让我们感到困惑。比如，有人可能在使用某个工具或库时，发现它的某些功能不太好用，或者在运行代码时出现了错误。这种情况下，很多人会选择去网上寻找解决方案，比如在StackOverflow这样的平台上提问。

在提问时，描述问题的方式非常重要。你需要清楚地说明你遇到的具体情况，比如你使用的是什么工具、你想要实现什么功能、以及你遇到的错误信息。这样，其他人才能更好地理解你的问题，并给出有效的建议。

同时，提供一些相关的代码片段也是很有帮助的。这样可以让别人看到你是如何实现的，可能会更容易发现问题所在。记得在分享代码时，保持格式清晰，这样阅读起来会更方便。

总之，提问时要尽量详细和清晰，这样才能提高得到帮助的机会。

def merging(list1, list2):
    m = len(list1)
    n = len(list2)
    res = []
    a, b = 0, 0
    while a < m and b < n:
        if list1[a] < list2[b]:
            res.append(list1[a])
            a += 1
        else:
            res.append(list2[b])
            b += 1
    if a == m:
        for i in list2[b:]:
            res.append(i)
    else:
         for i in list1[a:]:
             res.append(i)
    return res

if __name__ == '__main__':
    print 'Enter list 1'
    l1 = raw_input()
    list1 = map(int, l1.split())
    print 'Enter list 2'
    l2 = raw_input()
    list2 = map(int, l2.split())
    print merging(list1,list2)

Answer 3

你遇到了两个问题：

1. 当你到达 elif 或 else 的时候，你没有使用 break，所以外层的循环还在继续（而且 for 循环会忽略在内部循环中对 i 的修改）；
2. 你从来没有使用 return new。

最简单的解决办法是：

def merging(list1, list2):
    m = len(list1)
    n = len(list2)
    val = m+n
    j, k =  0, 0
    new =[]
    for i in range(val):
        if j<m and k<n:
             if list1[j] < list2[k]:
                new.append(list1[j])
                j += 1
             else:
                new.append(list2[k])     
                k += 1

        elif j==m:
            while i<m+n:
                new.append(list2[k])
                k += 1
                i += 1
            break # stop for loop here
        else:
            while i<m+n:
                new.append(list1[j])
                j += 1
                i += 1
            break # or here
    return new # and return the output

不过你可以更整洁地应用相同的逻辑：

def merge(l1, l2):
    """Merge the sorted lists into a new, single list."""
    i = j = 0
    out = []
    while True:
        if i == len(l1):
            out.extend(l2[j:])
            break
        elif j == len(l2):
            out.extend(l1[i:])
            break
        elif l1[i] <= l2[j]:
            out.append(l1[i])
            i += 1
        else:
            out.append(l2[j])
            j += 1
    return out

Answer 4

抱歉让你困惑了。

问题在于你不能改变i的值，因为i是在范围(val)内的。

def merging(list1, list2):
    m = len(list1)
    n = len(list2)
    val = m+n
    j, k =  0, 0
    new =[]
    for i in range(val):
        if j<m and k<n:
           if list1[j] < list2[k]:
              new.append(list1[j])
              j += 1
           else:
              new.append(list2[k])     
              k += 1

        elif j==m:
          if k<n:
              new.append(list2[k])
              k += 1
        else:
          if j<m:
                new.append(list1[j])
                j += 1

    print "sorted array is:"
    print new

if __name__ == '__main__':
    print 'Enter list 1'
    l1 = raw_input()
    list1 = map(int, l1.split())
    print 'Enter list 2'
    l2 = raw_input()
    list2 = map(int, l2.split())
    merging(list1,list2)