图书馆排序
维基百科,自由的 encyclopedia
图书馆排序(英语:Library sort),或空位插入排序是一种排序算法 ,它基于插入排序,但在每两个元素之间存在空位,以便于加速随后的插入。这个名字来自一个比喻:
假设一名图书管理员在一个长架上按字母顺序来整理书,从左边A开头的书,一直到右边Z开头的书,书本之间没有空格。如果图书管理员有一本开头为B的新书,当他找到了这本书在B区中的正确位置,他将不得不把从该位置后一直到Z的每一本书向右移动,就只是为了腾出空位放置这本新书。这就是插入排序的原理。但是,如果他在每一字母区后留有额外的空间,只要在B区之后还有空间,他插入书时就只需要移动少数几本书,而不会移动后面所有的书,这是图书馆排序的原理。
此算法由迈克尔·A·本德(英语:Michael A. Bender)、马丁·法拉赫-科尔顿(英语:Martin Farach-Colton)和米格尔·莫斯特雷罗(Miguel Mosteiro)于2004年提出[1],并于2006年出版。[2]
图书馆排序像插入排序一样,是稳定的排序算法,并且它是在线排序;然而,它被证明在大部分情况下具有O(n log n)的运行速度(相当于快速排序),而不是插入排序的O(n2)。用于此改进的机制与跳过列表非常相似。本文没有给出完整的实现,也没有重要部分的确切算法,如插入和重新平衡。需要更多的信息来比较图书馆排序的效率与现实中其他排序方法的效率。
相比基本的插入排序,图书馆排序的缺点是需要额外空间。该空间的大小将取决于实作的情况。在本文中,需要的空间为(1+ε)n,,但没有进一步的建议如何选择ε。
插入排序的一个缺点是它可能需要大量的交换操作,并且如果内存写入是昂贵的,则成本很高。图书馆排序可能会在插入步骤中有所改进,因为腾出空间所需移动的次数较少,但也因此在重新平衡步骤中增加了额外的成本。另外,由于随机数据集中的每个插入都可以访问不再处于高速缓存中的内存,特别是对于大型数据集,因此与归并排序相比,引用的局部性将变差。