合并排序数组算法

Question

我必须创建合并排序数组的算法。这是我所做的：

import sys

lists = [[1,2,3], 
         [-100, 70], 
         [23, 50]]
pivot = [0] * len(lists) # [0, 0, 0]
finalSorted = []


for _ in range(sum(len(x) for x in lists)): # quantity of items in 2D array 
    smallest = sys.maxint
    index_of_smallest = -1      
    for indx, list in enumerate(lists):
        if pivot[indx] < len(list):
            current = list[pivot[indx]]
            if current <= smallest:
                smallest = current
                index_of_smallest = indx

    finalSorted.append(smallest)
    pivot[index_of_smallest] = pivot[index_of_smallest]+1

print(finalSorted) #[-100, 1, 2, 3, 23, 50, 70]

问题：

这是最好的方法吗？
算法复杂度kn^2？其中 'k' 是平均数组长度，n 是数组数量。
是否只适用于 k 比 n 大得多的情况？这样的 k 和 n 在这里有哪个快速排序成为更好的解决方案的重点在哪里？

Answer 1

这是一个流行的编程面试问题。到目前为止我看到的最优雅的解决方案如下：

from Queue import PriorityQueue

def mergeKLists(lists):
    dummy = ListNode(None)
    curr = dummy
    q = PriorityQueue()
    for node in lists:
        if node: q.put((node.val,node))
    while q.qsize()>0:
        curr.next = q.get()[1]
        curr=curr.next
        if curr.next: q.put((curr.next.val, curr.next))
    return dummy.next

全部归功于> https://discuss.leetcode.com/topic/33609/10-line-python-solution-with-priority-queue

Answer 2

这有点快 -- 大约是我实验的 1.5 倍：

from itertools import izip_longest

final = []
second = lambda x: x[1]
while any(lists):
    idx, _ = min(enumerate(next(izip_longest(*lists, fillvalue=sys.maxint))), key=second)
    final.append(lists[idx].pop(0))

编辑：我想如果你更多地是从理论意义上考虑这个问题（即作为面试问题），这不是最好的答案——一个使用和滥用内置 python 功能虽然 :P

Answer 3

leetcode 上有一个非常相似的问题：https://leetcode.com/problems/merge-k-sorted-lists/description/ 合并 k 个排序列表，时间复杂度为 O(Nlogk)，其中 N 是 k 个列表的总数。

该算法的主要方法是构建一个大小为k的最小堆，并向其中添加元素。 leetcode网站上有详细的解释，建议大家看看

Answer 4

Python 自己的标准库提供了一个基于堆的解决方案 heapq.merge，我认为它是 O(kn log n)。我怀疑你能比 O(kn log n) 做得更好。

heapq.merge的source不算太长，想看的话

合并排序数组算法

Merge sorted arrays algorithm

python

language-agnostic

arrays

sorting

algorithm