C++中将多个排序序列合并为一个排序序列的算法
我正在寻找一种算法来合并多个排序的序列，假设 X 排序的具有 n 个元素的序列在 C++ 中合并为一个排序的序列，您能提供一些示例吗?
I am looking for an algorithm to merge multiple sorted sequences, lets say X sorted sequences with n elements, into one sorted sequence in c++ , can you provide some examples?
注意:我不想使用任何库
note: I do not want to use any library
推荐答案
有三种方法可以进行合并:-
There are three methods that do the merging :-
假设您将 m 个列表与 n 个元素每个
算法 1 :-
合并一次列出两个.使用像合并例程一样的合并排序在列表排序时进行合并.这很容易实现，无需任何库.但是需要时间 O(m^2*n) 如果 m 不大，这已经足够小了.
Merge lists two at a time. Use merge sort like merge routine to merge as the lists are sorted. This is very simple to implement without any libraries. But takes time O(m^2*n) which is small enough if m is not large.
算法 2:-
这是对 1. 的改进，我们总是合并剩余列表中最小的两个列表.使用 priority queue 来做到这一点并选择最小的两个列表并将它们合并并将新列表添加到队列中.这样做直到只剩下 1 个列表，这将是您的答案.该技术用于huffman coding 并产生最佳合并模式.这需要O(m*n*logm).此外，对于类似大小的列表，它可以parallel，因为我们可以选择一对列表并并行合并.假设您有 m 个处理器，那么理想情况下该算法可以在 O(n*logm) 而不是 O(m*n*logm)
This is an improvement over 1. where we always merge list which are the smallest two in the remaining list. Use a priority queue to do that and select smallest two list and merge them and add new list to queue. Do this till only 1 list is left which would be your answer. This technique is used in huffman coding and produces optimal merge pattern. This takes O(m*n*logm). Moreover for similar sized lists it can be made parallel as we can select a pair of list and merge in parallel. Assuming you have m processors then the algorithm can ideally run in O(n*logm) instead of O(m*n*logm)
算法 3:-
这是最有效的算法，您可以为所有列表的第一个元素维护一个 priority queue 并提取 min 以获取新元素，同时维护 min 元素所属的列表的索引，以便您可以添加该列表中的下一个元素.这需要 O(s*logm)，其中 s 是所有列表中的总元素.
This is most efficient algorithm where you maintain a priority queue for first elements of all lists and extract min to get new element also maintain index of the list min element belongs to so that you can add the next element from that list. This take O(s*logm) where s is total elements in all lists.
相关文章