请帮助理解以下算法的运行时间
我已经对总共 n 个元素的数组（每个数组有超过 1 个元素）进行了排序。
如果我没记错的话
，我想要一个大小为 n 的排序数组
如果我将这个 d 数组连接成一个 n 元素数组并用插入排序对其进行排序，那么插入排序在部分排序的数组上线性运行，它
不是部分排序的数组在这个数组上插入排序的运行时间不会是 O(n) 吗？
问问题
265 次
4 回答
3
插入排序是O(n²)，即使原始数组是几个预排序数组的串联。您可能需要使用mergesort将多个排序数组组合成一个排序数组。这将为您提供O(n·ln(d))性能
于 2013-02-25T12:32:40.437 回答
2
不，这将花费二次时间。插入排序只有在每个元素与它在排序数组中的点之间的距离最多为恒定距离d时才是线性的，在这种情况下它需要 O( nd ) 时间——这就是部分排序的含义。你没有那个保证。
只有在子数组的数量保证是一个小常数的假设下，您才能在线性时间内执行此操作。在这种情况下，您可以使用k路合并。
于 2013-02-25T12:30:53.920 回答
1
如果已知数组已排序，则只需将每个数组视为一个队列，对“头”进行排序，选择最小的头放入新数组中，然后从其数组中“弹出”选定的值.
如果 D 很小，那么简单的冒泡排序可以很好地对头部进行排序，否则您应该使用某种插入排序，因为只需将一个元素放入顺序中。
我相信这基本上是一种“合并排序”。当要排序的列表超出工作存储空间时非常有用，因为您可以先对较小的列表进行排序，而无需颠簸，然后使用非常少的工作存储空间进行组合。
于 2013-02-25T12:35:26.473 回答
1
对于较小的 N 值，插入排序是相当（相对）线性的。如果 N 很大，那么您的性能很可能是 N^2。
我相信，如果 N 足够大，子数组排序的事实不会有太大帮助。
Timsor t 是部分排序数组的良好候选者
于 2013-02-25T12:30:07.930 回答