algorithm - 对图书馆中几乎已排序的书籍进行排序的最佳算法是什么

Question

如果有一个图书馆，所有的书都已经整理好了，只有一本书没有放在应该放的地方。我应该使用哪种算法以最短的时间花费来对这个库进行排序？目前我认为它将与 O(nlogn) 合并排序。还有比这更快的算法吗？

Answer 1

1. 找到书的位置(一个索引 i)- 线性扫描
2. 将索引为j>i的所有书籍向右筛选一位
3. 将书放在新的空闲空间

这是在 O(n) 中完成的，仅对数据传递了 2 次，并且可以通过将步骤 (1) 和 (2) 组合在一起来优化为仅一次传递完成。

另请注意:

这基本上是对两个数组进行归并排序，(但是这个变体有 O(1) 的额外空间):

1. 原始(排序数组)
2. 新书(也是排序数组，大小为1)

由于array(1)-Original已经排好序，可以跳过其中的递归调用，直接进入mergesort的合并步骤。