圖書館排序

圖書館排序
概況
類別	排序演算法
資料結構	陣列
複雜度
平均時間複雜度	$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（頁面存檔備份，存於網際網路檔案館）