我正在阅读关于合并排序的以下链接
http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx
Merge sort的成名理由是它可以很容易地修改来处理
序列数据,如来自流或生成器的序列数据又一个巨大的
好处是,当仔细编写时,合并排序不需要
所有物品都在现场它可以对未知数量的项目进行排序
从流或生成器传入,这是一个非常有用的属性。
我的问题是
1.我的理解是合并排序需要完整的数组,因为我们必须在数组之间进行划分,然后独立排序,然后合并。如果不是所有项都存在,合并排序算法如何工作?
简单地给出一个算法,如何对来自流的项使用合并排序算法?

最佳答案

对1和2的回答有些关联。
您仍然可以对不完整的数组执行mergesort,这样会留下一个已排序的、部分完整的数组。运行时间仍然是O(n lg n)。至于插入剩余的项,您可以将部分数组与新项合并,或者一次插入一个新项,下面的q.v.第2部分如果原始数组几乎已完成,则一次插入一个剩余项最有效。
假设您是从一个排序的数字数组开始的,因为新的数字一个接一个地从流中传入,您就不必运行另一个mergesort。相反,您只需在O(n)时间内遍历排序数组,然后插入来自流的每个新项。

09-25 22:30
查看更多