c - 在 n 个元素的数组中，首先对 n-(root)n 个元素进行排序，我们必须对数组进行排序

Question

我们给出了一个包含 n 个整数的数组，其中前 n-(squareroot)n 个元素已排序(这意味着从最后一个开始的 (root)n 个元素未排序)。我们必须以最小的时间复杂度对整个数组进行排序。复杂性是什么？我们的方法是什么？当我试图解决它时，我的复杂度是 O(n)，首先对剩余数组进行排序并将其合并。有什么算法可以用小于 O(n) 的时间来解决它吗？

Answer 1

如果你的“数组”实际上是一个skip-list , 它可以在 O(log(n)sqrt(n))

中完成

for each element x in reminder:
   remove x from skip list   (O(1))
   find first element smaller then x in sorted part   (O(logn))
   insert x to the found position    (O(1))

复杂度将为 sqrt(n)*log(n)

请注意，如果数据是一个实际的数组，您将需要将所有元素向右移动以进行一次更改(例如，如果提醒中的元素之一是最小的)——这是单独完成的O(n)，所以对于一个数组，你不能比 O(n)

更好