Объединение двух отсортированных списков в Python

Question

У меня есть два списка объектов. Каждый список уже отсортирован по свойству объекта типа datetime. Я хотел бы объединить два списка в один отсортированный список. Это лучший способ просто сделать сортировку или есть более умный способ сделать это в Python?

Answer 1

def merge_sort(a,b):

    pa = 0
    pb = 0
    result = []

    while pa < len(a) and pb < len(b):
        if a[pa] <= b[pb]:
            result.append(a[pa])
            pa += 1
        else:
            result.append(b[pb])
            pb += 1

    remained = a[pa:] + b[pb:]
    result.extend(remained)


return result

Answer 2

Использовали шаг слияния сортировки слияния. Но я использовал генераторы . Сложность времени O (n)

def merge(lst1,lst2):
    len1=len(lst1)
    len2=len(lst2)
    i,j=0,0
    while(i<len1 and j<len2):
        if(lst1[i]<lst2[j]):
                yield lst1[i]
                i+=1
        else:
                yield lst2[j]
                j+=1
    if(i==len1):
        while(j<len2):
                yield lst2[j]
                j+=1
    elif(j==len2):
        while(i<len1):
                yield lst1[i]
                i+=1
l1=[1,3,5,7]
l2=[2,4,6,8,9]
mergelst=(val for val in merge(l1,l2))
print(*mergelst)

Answer 3

import random

    n=int(input("Enter size of table 1")); #size of list 1
    m=int(input("Enter size of table 2")); # size of list 2
    tb1=[random.randrange(1,101,1) for _ in range(n)] # filling the list with random
    tb2=[random.randrange(1,101,1) for _ in range(m)] # numbers between 1 and 100
    tb1.sort(); #sort the list 1 
    tb2.sort(); # sort the list 2
    fus=[]; # creat an empty list
    print(tb1); # print the list 1
    print('------------------------------------');
    print(tb2); # print the list 2
    print('------------------------------------');
    i=0;j=0;  # varialbles to cross the list
    while(i<n and j<m):
        if(tb1[i]<tb2[j]):
            fus.append(tb1[i]); 
            i+=1;
        else:
            fus.append(tb2[j]);
            j+=1;

    if(i<n):
        fus+=tb1[i:n];
    if(j<m):
        fus+=tb2[j:m];

    print(fus);

  # this code is used to merge two sorted lists in one sorted list (FUS) without
  #sorting the (FUS)

Answer 4

Если вы хотите сделать это более согласованным с изучением того, что происходит в итерации, попробуйте это

def merge_arrays(a, b):
    l= []

    while len(a) > 0 and len(b)>0:
        if a[0] < b[0]: l.append(a.pop(0))    
        else:l.append(b.pop(0))

    l.extend(a+b)
    print( l )

Answer 5

Ну, наивный подход (объединить 2 списка в один большой и отсортировать) будет сложностью O (N * log (N)). С другой стороны, если вы реализуете слияние вручную (я не знаю ни о каком готовом коде в библиотеках Python для этого, но я не эксперт), сложность будет O (N), что явно быстрее. Идея очень хорошо описана в посте Барри Келли.

Answer 6

Используйте шаг 'слияния' сортировки слиянием, он выполняется за O (n) раз.

Из википедии (псевдокод):

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    end while
    while length(left) > 0 
        append left to result
    while length(right) > 0 
        append right to result
    return result

Answer 7

Мое мнение об этой проблеме:

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

[i for p in zip(a,b) for i in (p if p[0] <= p[1] else (p[1],p[0]))]

# Output: [1, 2, 3, 5, 6, 7]

Answer 8

Этот код имеет временную сложность O (n) и может объединять списки любого типа данных, учитывая функцию количественного определения в качестве параметра func. Он создает новый объединенный список и не изменяет ни один из списков, переданных в качестве аргументов.

def merge_sorted_lists(listA,listB,func):
    merged = list()
    iA = 0
    iB = 0
    while True:
        hasA = iA < len(listA)
        hasB = iB < len(listB)
        if not hasA and not hasB:
            break
        valA = None if not hasA else listA[iA]
        valB = None if not hasB else listB[iB]
        a = None if not hasA else func(valA)
        b = None if not hasB else func(valB)
        if (not hasB or a<b) and hasA:
            merged.append(valA)
            iA += 1
        elif hasB:
            merged.append(valB)
            iB += 1
    return merged

Answer 9

Надеюсь, это поможет. Довольно просто и прямо:

l1 = [1, 3, 4, 7]

l2 = [0, 2, 5, 6, 8, 9]

l3 = l1 + l2

l3.sort ()

печать (l3)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 10

Это мое решение за линейное время без редактирования l1 и l2:

def merge(l1, l2):
  m, m2 = len(l1), len(l2)
  newList = []
  l, r = 0, 0
  while l < m and r < m2:
    if l1[l] < l2[r]:
      newList.append(l1[l])
      l += 1
    else:
      newList.append(l2[r])
      r += 1
  return newList + l1[l:] + l2[r:]