近排序数组的插入排序最坏时间复杂度？

Question

我有一个 n 元素数组。除了4?n它们之外的所有元素都被排序。我们不知道这些错位元素的位置。对此列表进行排序的最有效方法是什么？

有没有 O(n) 的方法来做到这一点？

更新 1：

的时间复杂度？对于几乎排序的数据，插入排序是 O(n)（在最坏的情况下是真的吗？）？

Answer 1

有一种对几乎已排序的数组进行排序的快速通用方法：

1. 从头到尾扫描原始数组。如果您发现两个项目的顺序不正确，请将它们移到第二个数组中，然后从第一个数组中删除它们。当心; 例如，如果您删除 x2 和 x3，那么您需要再次检查 x1 ? x2。这是在 O(n) 时间内完成的。在您的情况下，新数组的大小最多为 8sqrt(n)。

2. 对第二个数组进行排序，然后合并两个数组。由于第二个数组的项数较少，任何合理的排序算法都会在O(n)中对较小的第二个数组进行排序，合并又需要O(n)，所以总时间为O(n)。

如果使用 O(n log n) 算法对第二个数组进行排序，那么只要错误位置的项数最多为 O(n / log n)，排序就是 O(n)。