在c ++中合并8个排序列表,我应该使用哪个算法 [英] Merging 8 sorted lists in c++, which algorithm should I use
本文介绍了在c ++中合并8个排序列表,我应该使用哪个算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有8个排序列表,我需要合并成1个排序列表。我不知道最好的方法做到这一点。我在想以下:
I have 8 sorted lists that I need to merge into 1 sorted list. I don't know the best way to do this. I was thinking of the following:
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];
}
但最好只是担心排序最后? >
But would it be better to just worry about the sorting last?
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];
}
注意:我不在意列表是否被修改。 p>
Side note: I don't care that the lists are modified.
推荐答案
合并排序的合并阶段的简单扩展可以在O(n lg m)和m =列表数量),使用优先级队列(例如,堆)。伪代码:
A simple extension of merge sort's merge phase can do this in O(n lg m) time (where n = total number of items and m = number of lists), using a priority queue (eg, a heap). Pseudocode:
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 ++中一个简单的(未经测试的)具体实现: / p>
And a simple (untested!) concrete implementation in 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);
}
}
这篇关于在c ++中合并8个排序列表,我应该使用哪个算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文