fra*_*nis 6 arrays sorting algorithm complexity-theory data-structures
我有m个数组,每个数组的长度为n.每个数组都已排序.我想创建一个长度为m*n的单个数组,其中包含前面数组的所有值(包括重复值),已排序.我必须合并这些数组..
我认为最佳时间复杂度是m*n*log(m)
这是算法的草图..
我创建了一个lenth m的支持数组H,它包含每个数组的第一个元素的所有值.
然后我对这个数组(m log m)进行排序,并将min值移动到输出数组.
然后我将移动的值替换为下一个移动的值.实际上我不替换它,但我将其插入右侧(已排序)位置.我认为这需要记录.
我对所有m*n值重复这一点......因此m*n*log m
我的问题..你能想到一个更有效的算法吗？如果mnlogm实际上是最佳的,你至少可以想到一个更简单,更优雅的算法吗？
ltj*_*jax 11
复杂性是对的!但是,您的算法思想中存在一个小缺陷:您无法在已排序的数组中插入项目log m.你可以在这种复杂性中使用二进制搜索找到它的位置,但是你可能必须移动元素以实际将它放在那里.要解决此问题,您可以使用堆数据结构!
多路合并(这是您的算法的通用名称)通常使用另一个"合并"数据结构实现:锦标赛树.你可以在Knuth的"计算机编程艺术"(关于排序,iirc的章节)中找到描述.与特定情况下的堆相比,它在理论上和实践中具有较低的常数因子.
如果你想看实现,我很确定GNU C++标准库并行扩展中的并行多路合并是以这种方式实现的.
编辑:我引用了错误的书,现在已修复.