Python：结合两个排序列表（并保持排序），而不使用内置排序

我发现这种合并排序解决方案在线，我想知道如果while循环是要走的路或如果也有使用2 for循环和比较这些。Python：结合两个排序列表（并保持排序），而不使用内置排序

def merge(l, m): 
    result = [] 
    i = j = 0 
    total = len(l) + len(m) 
    while len(result) != total: 
     if len(l) == i: 
      result += m[j:] 
      break 
     elif len(m) == j: 
      result += l[i:] 
      break 
     elif l[i] < m[j]: 
      result.append(l[i]) 
      i += 1 
     else: 
      result.append(m[j]) 
      j += 1 
    print result

合并（[1,2,6,7]，[1,3,5,9]）

来源

2015-10-04 Intrepid Diamond

您可以轻松地改变，同时为：

def merge_for(l,m): 
    result = [] 
    i = j = 0 
    total = len(l) + len(m) 

    for k in range(total): 

     if len(l) == i: 
      result += m[j:] 
      print("append el {} at index {}".format(m[j], k)) 

      break 
     elif len(m) == j: 
      result += l[i:] 
      break 
     elif l[i] < m[j]: 
      result.append(l[i]) 
      print("append el {} at index {}".format(l[i], k)) 
      i += 1 
     else: 
      result.append(m[j]) 
      print("append el {} at index {}".format(m[j], k)) 
      j += 1 

    print(result) 


print(merge_for([1,2,6,7], [1,3,5,9])) 

append el 1 at index 0 
append el 1 at index 1 
append el 2 at index 2 
append el 3 at index 3 
append el 5 at index 4 
append el 6 at index 5 
append el 7 at index 6 
append el 9 at index 7 

[1, 1, 2, 3, 5, 6, 7, 9]

来源

2015-10-04 23:23:47 LetzerWille

啊，gotchya。所以几乎没有k，你创建自己的“模拟”循环（i + = 1＆j + = 1）？ –

@IntrepidDiamond把k工作，现在它打印出insersion的索引 – LetzerWille

Python的内置sorted实际上会非常高效（因为它使用的TimSort利用了列表子集中的现有排序）。这就是说，有一个内置的是避免了需要甚至可以构造一个新的list像sorted（或解决方案）将：heapq.merge

它正是专门为那些对您的现有各自独立地排序的列表情景。这是一个发生器功能，所以它不需要创建新的list。如果你正在努力学习，尽情享受，但如果这是针对“真实”的代码，请使用随附的电池，并避免重新发明车轮。

来源

2015-10-04 23:56:24 ShadowRanger

使用使用生成的溶液：

from itertools import chain 
def merge(l1,l2): 
    i,j = 0,0 
    try: 
     while True: 
      if l1[i] < l2[j]: 
       yield l1[i] 
       i +=1 
      else: 
       yield l2[j] 
       j+=1 
    except IndexError: 
     for e in chain(l1[i:],l2[j:]): 
      yield e 

[x for x in merge([1,2,6,7], [1,3,5,9])]

[1，1，2，3，5，6，7，9]

来源

2015-10-05 00:13:19 naimetti

heapq.merge答案是正确的。这只是为了好玩和学习。 – naimetti

如果你有一个排序的列表bisect.insort另：

from bisect import insort 

a,b = [1,2,6,7], [1,3,5,9] 

for ele in b: 
    insort(a, ele) 
print(a) 
[1, 1, 2, 3, 5, 6, 7, 9]

来源

2015-10-05 00:36:24

Python：结合两个排序列表（并保持排序），而不使用内置排序

回答

相关问题