将三个列表合并在一起

为了好玩，我试图实现k路合并排序，其中k = 3。我没有问题递归调用mergesort，但我试图合并三个列表在一起，但我没有得到一个排序列表。基本的想法是，我比较每个列表的第一个元素，如果它是最小的，我将它附加到列表中。我重复所有阵列的过程。将三个列表合并在一起

def three_merge(a,b,c): 
    i =0 
    j =0 
    k=0 
    list = [] 
    while(i < len(a) or j < len(b) or k < len(c)): 
     while(a[i] <= b[j] and a[i] <= c[k]): 
      list.append(a[i]) 
      i=i+1 
      print i 
     while(b[j] <= a[i] and b[j] <= c[k]): 
      list.append(b[j]) 
      j=j+1 
      print j 
     while(c[k] <= a[i] and c[k] <= b[j]): 
      list.append(c[k]) 
      k=k+1 
      print k 
    return list  

a = [1,2] 
b = [-5,10] 
c = [-11, 100] 
print three_merge(a,b,c)

来源

2013-02-08 phil12

你知道，这可能是一个/两个班轮。想到“排序（a + b + c）”。 – Amelia

返回列表应该在你的while循环中还是在它之后？ –

我试图不使用内置函数 – phil12

的问题是，你预先将索引i, j, k为每个追加到排序的列表值，这意味着，该索引是比相应的输入列表中的取列表中的所有元素后的长度大于一个。因此，当您比较不同输入列表中元素的值时，最终会达到您要尝试执行的操作，实际上，a[len(a)]将始终提供索引错误。

来源

2013-02-08 09:22:08

对现有代码进行更改会很繁琐。我可能会重写从这个代码，我会有一堆if语句。 – phil12

@ phil12是的，是吗？您当前的设计不起作用，因此需要进行更改。如果它变得丑陋，也许不同的方法更好。 –

你为什么不考虑三个列表合并为两个列表

def merge(a,b): 
    L = a 
    l = b 
    i = 0 
    j = 0 
    res = [] 
    if (len(b)>len(a)): 
     L=b 
     l=a 
    #print L 
    #print l 
    while (i<len(L)): 
     if(len(l)>0): 
      while (j<len(l)): 
       if (L[i]<=l[j]): 
        res.append(L[i]) 
        del L[i] 
        break 
       else: 
        res.append(l[j]) 
        del l[j] 
     else: 
      #print res 
      res = list(res+L) 
      L=[] 
      break 
    if len(l)>0: 
     res = list(res+l) 
     l=[] 
    return res 

def threeMerge(a,b,c): 
    return merge(merge(a,b),c) 

aa = [1,2] 
bb = [-5,3,20] 
cc= [-11, 23,45] 
print threeMerge(aa,bb,cc)

来源

2013-02-08 09:35:42 Sindico

两个合并的组成下面是n路合并的简单功能。随意问你是否有疑问：

def merge(*args): 
    lst = list(args) 
    idx = [0] * len(lst) 
    out = [] 

    while lst: 
     m = 0 
     for i in range(len(lst)): 
      if lst[i][idx[i]] < lst[m][idx[m]]: 
       m = i 
     out.append(lst[m][idx[m]]) 
     idx[m] += 1 
     if idx[m] >= len(lst[m]): 
      del lst[m] 
      del idx[m] 

    return out 


print merge([1,2,11], [2,9], [8]) # [1, 2, 2, 8, 9, 11]

来源

2013-02-08 11:05:30 georg

将三个列表合并在一起

回答

相关问题