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