sorting - 对部分排序的数组进行排序

Question

假设给定一个 n 个元素的排序列表，后跟 f(n) 个随机排序的元素。如果 (i) f(n) = O(logn)，你将如何对列表进行排序。我觉得最好的算法是合并排序，但我不确定由此产生的时间复杂度。

标签： sortingtime-complexitymergesort

Answer 1

您应该首先使用任何排序方法对 f(n) 元素进行排序，然后在最后阶段使用归并排序。时间复杂度将是O(n)，因为与排序部分的线性扫描相比，O(log(n) ² )可以忽略不计。

如果通过列表表示数组，则可以通过使用二进制搜索查找左侧部分的插入点来减少与O(log(n) ² )的比较次数。它仍然需要O(n)复制操作，因此根据复制与比较的相对成本，即使对于中等大的n值，时间也可能保持亚线性。