什么是最好的算法来排序在图书馆几乎排序的书籍

Question

如果有一个图书馆所有书籍已经排序，除了只有一本书没有存储在它应该是的地方。我应该使用哪种算法以最短的时间对这个库进行排序？目前我认为它将与O（nlogn）合并排序。任何比这更快的算法？

Answer 1

1. 找到图书（索引i）的位置 - 线性扫描
2. j>i一个地方筛所有的书与指数权
3. 将书籍在新的自由空间

这是在O（n）中完成的，数据只有2次通过，并且可以通过将步骤（1）和（2）组合在一起完成而优化为仅在一次通过中完成。

还要注意：

这基本上是做归并两个阵列，（但是具有O（1）额外的空间，该变型）：

1. 原件（排序阵列）
2. 新书（也是大小为1的排序阵列）

由于array（1） - Original已经排序，所以可以跳过rec ursive调用它，然后直接进入mergesort的合并步骤。

Answer 2

如果您确定它几乎已排序，那么插入算法甚至泡泡将是最好的......实际上，合并不会是最好的，因为它会进行太多的订单检查。

看看this gif，它可能会帮助你:)