algorithm - 对已按升序排序的 n 个固定段的列表进行排序

Question

题目如下:

Lists which consist of a small fixed number, n, of segments connected end-to-end, each segment is already in ascending order.

我考虑过使用 mergesort 和 base case 如果等于 n 然后返回并合并它们，因为我们已经知道它们是排序的，但是如果我有 3 个段，它就不会工作，因为我除以 2 和您不能将 3 个段平均分为两部分。

另一种类似于归并排序的方法。所以我为每个段使用 n 个堆栈，我们可以确定是否 L[i] > L[i+1] 因为段是按升序排列的。但是我需要进行 n 次比较才能确定哪个元素先出现，而且我不知道在不使用另一个数据结构来比较堆栈顶部的元素的情况下动态比较 n 个元素的有效方法。此外，您应该使用问题特征、已排序的段来获得比传统算法更好的结果。即复杂度低于 O(nlogn)。

如果您有想法，伪代码会很好。

编辑:

一个例子是 [(14,20,22),(7,8,9),(1,2,3)] 这里我们有 3 个元素的 3 个片段，即使这些片段是排序的，整个列表不是。

附注() 那里只是指出段

Answer 1

我想您可能误解了归并排序。虽然通常你会分成两半并在合并之前对每一半进行排序，但实际上是合并部分构成了算法。您只需要在运行时合并即可。

以你的例子 [(14,20,22),(7,8,9),(1,2,3)]

第一次合并后你有[(7, 8, 9, 14, 20, 22),(1, 2, 3)]

第二次合并后你有[(1, 2, 3, 7, 8, 9, 14, 20, 22)]

l = [14, 20, 22, 7, 8, 9, 1, 2, 3]

rl = [] # run list
sl = [l[0]] # temporary sublist

#split list into list of sorted sublists
for item in l[1:]:
    if item > sl[-1]:
        sl.append(item)
    else:
        rl.append(sl)
        sl = [item]
rl.append(sl)
print(rl)

#function for merging two sorted lists
def merge(l1, l2):
    l = [] #list we add into
    while True:
        if not l1:
            # first list is empty, add second list onto new list
            return l + l2
        if not l2:
            # second list is empty, add first list onto new list 
            return l + l1
        if l1[0] < l2[0]:
            # rather than deleting, you could increment an index
            # which is likely to be faster, or reverse the list
            # and pop off the end, or use a data structure which
            # allows you to pop off the front
            l.append(l1[0])
            del l1[0]
        else:
            l.append(l2[0])
            del l2[0]

# keep mergins sublists until only one remains
while len(rl) > 1:
    rl.append(merge(rl.pop(), rl.pop()))

print(rl)

值得注意的是，除非这只是一个练习，否则您最好使用您选择的语言使用的任何内置排序功能。