排序d排序数组的算法

请帮忙了解下列算法的运行时间
我已经有d个已经排序的数组（每个数组有超过1个元素），总共有n个元素。
我想有大小的一个排序数组n
如果我没有错误插入排序是在部分地排序的阵列线性运行
如果我将串联此d阵列成一个n元件阵列，并用插入排序排序它
是不是一个部分排序的数组和排序在这个数组不会是O（n）？排序d排序数组的算法

来源

2013-02-25 MAB

插入排序对于小的N值是相当（相对）线性的。

我相信，如果N足够大，那么子阵列不会排序，这相当有帮助。

Timsor T是部分分类阵列

来源

2013-02-25 12:30:07

不是插入排序在部分排序的数组线性的时间？如果我连接这个数组不会部分排序？ – MAB 2013-02-25 12:34:21

是的，但在你的情况下，整个数组不是部分排序，只是“子”部分。换句话说，如果只有几个条目不合适，那么插入排序是正确的 - 但在您的情况下，您有部分已排序 - 但“整体”仍然相对未排序。 – 2013-02-25 12:36:33

我认为这：http://www.sorting-algorithms.com/是非常有教育意义的（对我来说无论如何:-)） – 2013-02-25 12:37:18

不，这将需要二次的时间一个很好的候选人。如果每个元素距离它在一个排序数组中的位置最多有一个恒定的距离，那么插入排序只是线性的，在这种情况下，它需要O（和）时间 - 这就是部分排序的含义。你没有这个保证。

只有在子阵列的数量保证为小常数的假设下，才能在线性时间内完成此操作。在这种情况下，您可以使用k-way merge。

来源

2013-02-25 12:30:53

什么意思呢？ – MAB 2013-02-25 12:32:56

@MAB：没关系，我犯了一个错误。请参阅最新的答案。 – 2013-02-25 12:38:26

插入排序为O（n²），即使原始数组是串联的几个预分类数组。您可能需要使用mergesort将几个已排序的数组合并到一个已排序的数组中。这会给你O（n·ln（d））性能

来源

2013-02-25 12:32:40

如果数组已知被排序，那么将每个数组视为一个队列，排序“头”，选择最小的头放入新的数组中，然后从数组中“弹出”选定的值。

如果D很小，那么一个简单的气泡排序对于排序头部效果很好，否则你应该使用某种插入排序，因为只有一个元素需要放入顺序中。

我相信这基本上是一个“合并排序”。当要排序的列表超出工作存储空间时非常有用，因为您可以先排序较小的列表，而不会发生颠簸，然后使用非常少的工作存储进行组合。

来源

2013-02-25 12:35:26

排序d排序数组的算法

回答

相关问题