例如,给定一个整数数组及其两个连续序列的起始位置'b1'和'b2',还提供了位置'last',表示第二序列的结束位置.从阵列[B1]到阵列[B2-1]和从阵列[B2]与阵列[最后]都在单独订购,如何将它们合并在适当位置用O(n)的时间和O(1)空间成本？
Raf*_*ird 25
Kronrod的合并是第一个发布的算法.它大致如下:
将数组的两个部分拆分为大小为k = sqrt(n)的块.使用第一个元素作为比较基础对块进行排序.这可以通过选择排序在sqrt(n)^ 2 = O(n)中完成.这里选择排序的关键属性是每个块有不断的移动,所以只有#comparisons是正方形.
在此阶段之后,对于A[i]数组中的每个元素,其k-1下面至多有"错误排序"的元素,即位置j< i这样的元素A[j]>A[i].这些(可能)位于其下方最靠近其他合并部分的区块中.请注意,块的第一个元素(以及它下面的所有其他块)已经相对于正确排序,A[i]因为块在其第一个元素上排序.这就是第二阶段工作的原因,即实现完全排序的数组:
现在将第一个块与第二个块合并,然后将第二个块与第三个块合并,等等,使用最后2个块作为合并输出的临时空间.这将扰乱最后两个块的内容,但是在最后阶段,它们(与前一个块一起)可以通过sqrt(n)^ 2 = O(n)时间中的选择排序进行排序.
Dav*_*vid 23
这绝不是一个简单的问题它是可能的,但很少在实践中完成,因为它比使用N-scratch空间的标准合并复杂得多.Huang和Langston的论文自80年代末以来一直存在,尽管实际的实现直到后来才真正实现.早些时候,L.Trabb-Prado在1977年的论文明显早于黄和兰斯顿,但我很想找到纸的确切文本; 只有参考文献比比皆是
Geert,Katajainenb和Pasanen的一个优秀的后期出版物" 渐近有效的就地合并"(1995)是对多种算法的良好报道,并且引用了Trabb-Prado对该主题的贡献.
mcd*_*lla 10
有真正的就地合并这样的东西,但它们并不简单,以至于任何人都不会在面试过程中独立地重新发明它们 - 已有多篇论文描述了一系列相当复杂的算法.一个是1988年3月CACM的Huang和Langston的实际就地合并.最初的想法是将长度为n的数据划分为大小为sqrt(n)的块,并使用一个块,填充最大的元素数据,提供用于合并其他数据的缓冲区空间.该论文的介绍说
"给定两个长度总和为n的排序列表,在O(n)步骤中合并的明显方法也需要线性数量的额外内存.另一方面,只使用恒定量的内容很容易合并到位.通过堆排序的额外空间,但代价是O(n log n)时间"
因此,我声称可以实现真正的合并,但不是很明显.