圖書館排序

图书馆排序，或空位插入排序是一种排序算法 ，它基于插入排序，但在每两个元素之间存在空位，以便于加速随后的插入。这个名字来自一个比喻： 假设一名图书管理员在一个长架上按字母顺序來整理书，从左边A開頭的書，一直到右边Z開頭的書，书本之间没有空格。如果图书管理员有一本開頭為B的新书，当他找到了這本書在B區中的正确位置，他将不得不把從該位置後一直到Z的每一本书向右移动，就只是为了腾出空位放置这本新书。这就是插入排序的原理。但是，如果他在每一字母區後留有額外的空間，只要在B區之后還有空间，他插入书時就只需要移动少数几本书，而不会移动后面所有的书，这是图书馆排序的原理。 此算法由 、和 于2004年提出，并于2006年出版。 图书馆排序像插入排序一样，是稳定的排序算法，并且它是在线排序；然而，它被证明在大部分情况下具有O(n log n)的运行速度（相当于快速排序），而不是插入排序的O(n2)。用于此改进的机制与跳过列表非常相似。本文没有给出完整的实现，也没有重要部分的确切算法，如插入和重新平衡。需要更多的信息来比较图书馆排序的效率与现实中其他排序方法的效率。 相比基本的插入排序，图书馆排序的缺点是需要额外空间。该空间的大小将取决于实作的情況。在本文中，需要的空间为(1+ε)n,，但没有进一步的建议如何选择ε。 插入排序的一个缺点是它可能需要大量的交换操作，并且如果内存写入是昂贵的，则成本很高。图书馆排序可能会在插入步骤中有所改进，因为騰出空間所需移动的次數較少，但也因此在重新平衡步骤中增加了额外的成本。另外，由于随机数据集中的每个插入都可以访问不再处于高速缓存中的内存，特别是对于大型数据集，因此与归并排序相比，引用的局部性将变差。