在c++中合并8个排序列表，我应该使用哪种算法

Question

我有 8 个排序列表，需要将其合并为 1 个排序列表。 我不知道最好的方法来做到这一点。 我在想以下问题：

void merge_lists_inplace(list<int>& l1, const list<int>& l2)
{
    list<int>::iterator end_it = l1.end();
    --end_it;
    copy(l2.begin(), l2.end(), back_inserter(l1));
    ++end_it;
    inplace_merge(l1.begin(), end_it, l1.end());
}

list<int> merge_8_lists(list<int>[8] lists)
{
    merge_lists_inplace(lists[0], lists[1]);
    merge_lists_inplace(lists[2], lists[3]);
    merge_lists_inplace(lists[4], lists[5]);
    merge_lists_inplace(lists[6], lists[7]);

    merge_lists_inplace(lists[0], lists[2]);
    merge_lists_inplace(lists[4], lists[6]);

    merge_lists_inplace(lists[0], lists[4]);

    return lists[0];
}

但是最后再担心排序会不会更好？

list<int> merge_8_lists(list<int>[8] lists)
{
    for (int i = 1; i < 8; ++i)
        copy(lists[i].begin(), lists[i].end(), back_inserter(lists[0]));        
    lists[0].sort();
    return lists[0];
}

旁注：我不在乎列表是否被修改。

Answer 1

合并排序合并阶段的简单扩展可以在 O(n lg m) 时间内完成此操作（其中 n = 项目总数，m = 列表数量），使用 优先级队列（例如，堆）。 伪代码：

Let P = a priority queue of the sorted lists, sorted by the smallest element in each list
Let O = an empty output list
While P is not empty:
  Let L = remove the minimum element from P
  Remove the first element from L and add it to O
  If L is not empty, add L to P

以及 C++ 中的简单（未经测试！）具体实现：

#include <list>
#include <set>

template<typename T>
struct cmp_list {
    bool operator()(const std::list<T> *a, const std::list<T> *b) const {
        return a->front() < b->front();
    }
};

template<typename T>
void merge_sorted_lists(std::list<T> &output, std::list<std::list<T> > &input)
{
    // Use a std::set as our priority queue. This has the same complexity analysis as
    // a heap, but has a higher constant factor.
    // Implementing a min-heap is left as an exercise for the reader,
    // as is a non-mutating version
    std::set<std::list<T> *, cmp_list<T> > pq;

    for ( typename std::list<std::list<T> >::iterator it = input.begin();
            it != input.end(); it++)
    {
        if (it->empty())
            continue;
        pq.insert(&*it);
    }

    while (!pq.empty()) {
        std::list<T> *p = *pq.begin();
        pq.erase(pq.begin());

        output.push_back(p->front());
        p->pop_front();

        if (!p->empty())
            pq.insert(p);
    }
}

Answer 2

您可以尝试一次对每个列表应用合并排序：

http://en.wikipedia .org/wiki/Merge_sort

这里有合并排序的算法。 本质上，您将使用列表 1 和 2 并对它们进行合并排序。 然后，您将采用新的组合列表并使用列表 3 进行排序，如此继续下去，直到获得一个完全排序的列表。

编辑：

实际上，因为您的列表已经排序，所以只需要合并排序的最后一部分。 我会迭代地将列表组合成越来越大的部分，同时对每个较大的列表进行排序，直到获得完整的列表，这本质上就是合并排序在完成分而治之方法后所做的事情。

Answer 3

如果性能不是问题，我会最后对列表进行排序。 代码更具可读性、更短，并且不太可能被将来重新访问代码的人搞砸。

Answer 4

这是标准（尽管是 8 路）合并排序。

基本上，您“打开”八个排序列表，然后开始处理它们，每次提取最低值，例如

# Open all lists.

open newlist for write
for i = 1 to 8:
    open list(i) for read
end for

：

# Process forever (break inside loop).

while true:
    # Indicate that there's no lowest value.

    smallidx = -1

    # Find lowest value input list.

    for i = 1 to 8:
        # Ignore lists that are empty.

        if not list(i).empty:
            # Choose this input list if it's the first or smaller
            #  than the current smallest.

            if smallidx = 1:
                smallidx = i
                smallval = list(i).peek()
            else:
                if list(i).peek() < smallval:
                    smallidx = i
                    smallval = list(i).peek()
                end if
            end if
        end if
    end for

 

    # No values left means stop processing.

    if smallidx = -1:
        exit while
    end if

    # Transfer smallest value then continue.

    smallval = list(smallidx).get()
    newlist.put(smallval)
end while

Answer 5

基本上你正在做多路合并排序的一部分，除了你的东西已经排序了......

http://lcm.csa.iisc.ernet.in/dsa/node211.html

只需找到每个数组中最低的（几乎用作堆栈）并将其放入输出中，直到所有堆栈为空...

Answer 6

您需要合并排序。 您的列表已经拆分，但并未一直拆分到最小级别。 您可能想要这样做：

unsorted_list = concatenate(list[0], list[1], list[2], ... , list[7]);
sorted_list = merge_sort(unsorted_list);

这不应该是一个耗时/内存消耗的操作，因为串联应该添加从列表中的最后一个节点到下一个列表的第一个元素的链接。