算法合并多个排序的序列成C一根排序序列++ [英] Algorithm to merge multiple sorted sequences into one sorted sequence in C++

问题描述

我在寻找一种算法来合并多个排序的序列，可以例如x排序的序列与n个元素，融入在C ++中1排序序列中，你能提供一些例子吗？

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 :-

假设你要合并米列表与 n个元素每个

算法1： -

合并列出每次两个。使用归并排序像合并程序合并为列表进行排序。这是很简单的，没有任何库来实现。但需要时间 O（平方公尺* 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.我们始终合并列表，它是最小的两个剩余的列表中显示。使用的优先级队列做到这一点，选择最小的两个列表，并把它们合并，并添加新的列表来排队。做到这一点，直到1只留下这将是你的答案列表。这种技术用在 Huffman编码并产生最优合并方式。这需要 O（M * N * logm）。而且类似大小的列表可以做并行，因为我们可以选择对列表和并行合并。假设你有 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： -

这是最有效的算法，其中你保持一个的优先级队列所有列表的第一要素，并提取分钟获得新的元素也保持了名单的指数分元素所属这样就可以从该列表中添加下一个元素。这取 0（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.

这篇关于算法合并多个排序的序列成C一根排序序列++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！