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：結合兩個排序列表（並保持排序），而不使用內置排序

回答

相關問題