图书馆排序

图书馆排序
概况
類別	排序算法
資料結構	数组
复杂度
平均時間複雜度	${\displaystyle O(n\log n)}$
最坏时间复杂度	${\displaystyle O(n^{2})}$
最优时间复杂度	${\displaystyle O(n)}$
空間複雜度	${\displaystyle O(n)}$
相关变量的定义

图书馆排序（英語：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(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（页面存档备份，存于互联网档案馆）