图书馆排序

图书馆排序
概况
类别	排序算法
数据结构	数组
复杂度
平均时间复杂度	$O(n\log n)$
最坏时间复杂度	$O(n^{2})$
最优时间复杂度	$O(n)$
空间复杂度	$O(n)$
相关变量的定义

图书馆排序（英语：Library sort），或空位插入排序是一种排序算法 ，它基于插入排序，但在每两个元素之间存在空位，以便于加速随后的插入。这个名字来自一个比喻：

假设一名图书管理员在一个长架上按字母顺序来整理书，从左边A开头的书，一直到右边Z开头的书，书本之间没有空格。如果图书管理员有一本开头为B的新书，当他找到了这本书在B区中的正确位置，他将不得不把从该位置后一直到Z的每一本书向右移动，就只是为了腾出空位放置这本新书。这就是插入排序的原理。但是，如果他在每一字母区后留有额外的空间，只要在B区之后还有空间，他插入书时就只需要移动少数几本书，而不会移动后面所有的书，这是图书馆排序的原理。

此算法由迈克尔·A·本德、马丁·法拉赫-科尔顿和米格尔·莫斯特雷罗（Miguel Mosteiro）于2004年提出，并于2006年出版。

图书馆排序像插入排序一样，是稳定的排序算法，并且它是在线排序；然而，它被证明在大部分情况下具有O(n log n)的运行速度（相当于快速排序），而不是插入排序的O(n²)。用于此改进的机制与跳过列表非常相似。本文没有给出完整的实现，也没有重要部分的确切算法，如插入和重新平衡。需要更多的资讯来比较图书馆排序的效率与现实中其他排序方法的效率。

相比基本的插入排序，图书馆排序的缺点是需要额外空间。该空间的大小将取决于实作的情况。在本文中，需要的空间为(1+ε)n,，但没有进一步的建议如何选择ε。

插入排序的一个缺点是它可能需要大量的交换操作，并且如果内存写入是昂贵的，则成本很高。图书馆排序可能会在插入步骤中有所改进，因为腾出空间所需移动的次数较少，但也因此在重新平衡步骤中增加了额外的成本。另外，由于随机数据集中的每个插入都可以访问不再处于高速缓存中的内存，特别是对于大型数据集，因此与归并排序相比，引用的局部性将变差。

实现

算法

现在我们有大小为n个元素的数组。我们选择每两个元素之间的空位，那么我们将有一个最大的数组（1 +ε）n。该算法在log n轮中工作。我们通过二分查找来找到插入的位置，然后交换后面的元素，直到我们命中一个空格。一旦结束，我们通过在每个元素之间插入空格来重新平衡最终的数组。

算法根据以下三个重要的步骤：

1. 二分查找：我们在已经插入的元素中，二分查找这个元素应该插入的位置。这可以通过线性移动到阵列的左侧或右侧，如果您点击中间元素中的空格。

2. 插入: 将元素插入到正确的位置，并且通过交换把后面的元素向右移动，直到空格。

3. 重新平衡：在数组中的每对元素之间插入空格。这需要线性时间，并且由于算法只运行log n轮，总重新平衡只需要O（n log n）时间。

伪代码

proc rebalance(A, begin, end)
    r ← end
    w ← end * 2
    while r >= begin
        A[w+1] ← gap
        A[w] ← A[r]
        r ← r - 1
        w ← w - 2

proc sort(A)
    n ← length(A)
    S ← new array of n gaps
    for i ← 1 to floor(log2(n) + 1)
        for j ← 2^i to 2^(i+1)
            ins ← binarysearch(A[j], S, 2^(i-1))
            insert A[j] at S[ins]

在这里，binarysearch(A，k)是执行二分查找中的A中的第k个元素，并且跳过空格，找到元素A[j]应该插入的位置。插入应该优于填补元素的空格。

外部链接

• Gapped Insertion Sort（页面存档备份，存于互联网档案馆）