使用合并排序算法合并和排序一个列表

Question

使用合并排序算法合并和排序一个列表

4

这是我的代码。

def merge_lists(all_lst):
    if len(all_lst) < 2:
        return all_lst[0]   # get rid of the extra [] 
    left = merge_lists(all_lst[:len(all_lst)//2]) #[[2, 7, 10]]  ##[[0, 4, 6]]      
    right = merge_lists(all_lst[len(all_lst)//2:])#[[0, 4, 6], [3, 11]] ##[[3,11]]
    def merge(left,right):
        results = []
        while left and right:
            if left[0] < right[0]:
                results.append(left[0])
                left.remove(left[0])
            else:
                results.append(right[0])
                right.remove(right[0])
        results.extend(left)
        results.extend(right)
        return results
    return merge(left, right)

我能在输入以下内容后得到答案：

all_lst = [[2, 7, 10], [0, 4, 6], [3, 11]]
print(merge_lists(all_lst)) # [0, 2, 3, 4, 6, 7, 10, 11]

但是当我尝试稍作更改时，它已经不能正常工作了。

 all_lst = [[2, 7, 10], [0, 4, 6], [3, 11, 1]]
print(merge_lists(all_lst)) ##[0, 2, 3, 4, 6, 7, 10, 11, 1]

我能知道出了什么问题吗？

- user3398505

2

你意识到在生产代码中可以使用 sorted(itertools.chain.from_iterable(all_lst))，或者如果你的列表都是排序好的，可以使用 list(heapq.merge(*all_lst))。 - Jon Clements

@JonClements 的建议很好，使用 heapq 可以得到一个 O(log k * n) 的算法，其中 k 是列表的数量，n 是元素的总数。 - Niklas B.

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pythoneer · Answer 1

如果您的意思是想对合并后的列表进行排序，那么您可以使用 sum() 函数，然后对其进行排序：

list1 = [[2, 7, 10], [0, 4, 6], [3, 11]]
list2 = [[2, 7, 10], [0, 4, 6], [3, 11, 1]]
list3 = [[10, 567, 34], [-10, -30, -109], [98, 10001, 5]]

def merge_sort(lists, ascending=True):

    if ascending == True: # If in an ascending order
        return sorted(sum(lists,[])) # `sum()` merges and `sorted()` sorts it

    elif ascending == False: # If in a descending order
        return sorted(sum(lists,[]), reverse=True) # `reverse=True` makes it descending

>>> print(merge_sort(list1))
    print(merge_sort(list2))
    print(merge_sort(list3))

[0, 2, 3, 4, 6, 7, 10, 11]
[0, 1, 2, 3, 4, 6, 7, 10, 11]
[-109, -30, -10, 5, 10, 34, 98, 567, 10001]

>>> print(merge_sort(list1, ascending=False))
    print(merge_sort(list2, ascending=False))
    print(merge_sort(list3, ascending=False))

[11, 10, 7, 6, 4, 3, 2, 0]
[11, 10, 7, 6, 4, 3, 2, 1, 0]
[10001, 567, 98, 34, 10, 5, -10, -30, -109]

- zbs · Answer 2

第三个列表没有排序。当您进行最终的扩展时，1会被插入到最终列表的末尾。在调用合并之前，您应该对列表进行排序。

换句话说，您的输入应该是：

 all_lst = [[2, 7, 10], [0, 4, 6], [1, 3, 11]]

合并的方式是假设子列表已经排序。

例如，取这两个列表：

left = [1, 3]
right = [2, 4]
results = []

合并的过程如下：

if left[0] < right[0]:
    results.append(left[0])
    left.remove(left[0])

所以现在

results = [1]
left = [3]
right = [2,4]

但如果你有：

left = [3, 1]
right = [2, 4]
results = []

合并的过程如下：

if left[0] < right[0]: #false
else:
    results.append(right[0])
    right.remove(right[0])

所以现在

results = [2]
left = [3,1]
right = [4]

因此，最终你得到了一个未排序的列表。