跳转至

希爾排序

本頁面將簡要介紹希爾排序。

定義

希爾排序（英語：Shell sort），也稱為縮小增量排序法，是 插入排序 的一種改進版本。希爾排序以它的發明者希爾（英語：Donald Shell）命名。

過程

排序對不相鄰的記錄進行比較和移動：

  1. 將待排序序列分為若干子序列（每個子序列的元素在原始數組中間距相同）；
  2. 對這些子序列進行插入排序；
  3. 減小每個子序列中元素之間的間距，重複上述過程直至間距減少為 \(1\)。

性質

穩定性

希爾排序是一種不穩定的排序算法。

時間複雜度

希爾排序的最優時間複雜度為 \(O(n)\)。

希爾排序的平均時間複雜度和最壞時間複雜度與間距序列的選取有關。設間距序列為 \(H\)，下面給出 \(H\) 的兩種經典選取方式，這兩種選取方式均使得排序算法的複雜度降為 \(o(n^2)\) 級別。

命題 \(1\)：若間距序列為 \(H= \{ 2^k-1\mid k=1,2,\ldots,\lfloor\log_2 n\rfloor \}\)（從大到小），則希爾排序算法的時間複雜度為 \(O(n^{3/2})\)。

命題 \(2\)：若間距序列為 \(H= \{ k=2^p\cdot 3^q\mid p,q\in \mathbb N,k\le n \}\)（從大到小），則希爾排序算法的時間複雜度為 \(O(n\log^2 n)\)。

為證明這兩個命題，我們先給出一個重要的定理並證明它，這個定理反應了希爾排序的最主要特徵。

定理 \(1\)：只要程序執行了一次 \(\text{InsertionSort}(h)\)，不管之後怎樣調用 \(\text{InsertionSort}\) 函數，\(A\) 數組怎樣變換，下列性質均會被一直保持：

\[ \begin{array}{c} A_1,A_{1+h},A_{1+2h},\ldots \\ A_2,A_{2+h},A_{2+2h},\ldots \\ \vdots \\ A_h,A_{h+h},A_{h+2h},\ldots \end{array} \]

證明：

我們先證明一個引理：

引理 \(1\)：對於整數 \(n,m\)、正整數 \(l\) 與兩個數組 \(X(x_1,x_2,\ldots,x_{n+l}),Y(y_1,y_2,\ldots,y_{m+l})\)，滿足如下要求：

\[ y_1 \le x_{n+1},y_2 \le x_{n+2},\ldots,y_l \le x_{n+l} \]

則我們將兩個數組分別升序排序後，上述要求依然成立。

證明：

設數組 \(X\) 排序完為數組 \(X'(x'_1,\ldots,x'_{n+l})\)，數組 \(Y\) 排序完為數組 \(Y'(y'_1,\ldots,y'_{m+l})\)。

對於任何 \(1\le i\le l\)，\(x'_{n+i}\) 小等於數組 \(X'\) 中的 \(l-i\) 個元素，也小等於數組 \(X\) 中的 \(l-i\) 個元素（這是因為 \(X\) 與 \(X'\) 的元素可重集合是相同的）。

那麼在可重集合 \(\{x_{n+1},\ldots,x_{n+l} \} \subset X\) 中，大等於 \(x'_{n+i}\) 的元素個數不超過 \(l-i\) 個。

進而小於 \(x'_{n+i}\) 的元素個數至少有 \(i\) 個，取出其中的 \(i\) 個，設它們為 \(x_{n+k_1},x_{n+k_2},\ldots,x_{n+k_i}\)。於是有：

\[ y_{k_1}\le x_{n+k_1}\le x'_{n+i},y_{k_2}\le x_{n+k_2}\le x'_{n+i},\ldots,y_{k_i}\le x_{n+k_i}\le x'_{n+i} \]

所以 \(x'_{n+i}\) 至少大等於 \(Y\) 也即 \(Y'\) 中的 \(i\) 個元素，那麼自然有 \(y'_i\le x'_{n+i}\,(1\le i\le l)\)。

證畢

再回到原命題的證明：

我們實際上只需要證明調用完 \(\text{InsertionSort}(h)\) 的緊接着下一次調用 \(\text{InsertionSort}(k)\) 後，\(h\) 個子列仍有序即可，之後容易用歸納法得出。下面只考慮下一個調用：

執行完 \(\text{InsertionSort}(h)\) 後，如下組已經完成排序：

\[ \begin{array}{c} A_1,A_{1+h},A_{1+2h},\ldots \\ A_2,A_{2+h},A_{2+2h},\ldots \\ \vdots \\ A_h,A_{h+h},A_{h+2h},\ldots \end{array} \]

而之後執行 \(\text{InsertionSort}(k)\)，則會將如下組排序：

\[ \begin{array}{c} A_1,A_{1+k},A_{1+2k},\ldots \\ A_2,A_{2+k},A_{2+2k}, \ldots \\ \vdots \\ A_k,A_{k+k},A_{k+2k},\ldots \end{array} \]

對於每個 \(i\) \((1\le i\le \min(h,k))\)，考慮如下兩個組：

\[ \begin{array}{c} A_i,A_{i+k},A_{i+2k},\ldots \\ \ldots,A_{i+h},A_{i+h+k},A_{i+h+2k},\ldots \end{array} \]

第二個組前面也加上“\(\ldots\)”的原因是可能 \(i+h\ge k\) 從而前面也有元素。

則第二個組就是引理 \(1\) 中的 \(X\) 數組，第一個組就是 \(Y\) 數組，\(l\) 就是第二個組從 \(i+h\) 之後頂到末尾的長度，\(n\) 是第二個組中前面那個“\(\ldots\)”的長度，\(m\) 是第一個組去掉前 \(l\) 個後剩下的個數。

又因為有：

\[ A_i\le A_{i+h},A_{i+k}\le A_{i+h+k},\ldots \]

所以由引理 \(1\) 可得執行 \(\text{InsertionSort}(k)\) 將兩個組分別排序後，這個關係依然滿足，即依然有 \(A_i\le A_{i+h}\,(1\le i\le \min(h,k))\)。

若有 \(i>\min(h,k)\)，容易發現取正整數 \(w\) \((1\le w\le \min(h,k))\) 再加上若干個 \(k\) 即可得到 \(i\)，則之前的情況已經藴含了此情況的證明。

綜合以上論述便有：執行完 \(\text{InsertionSort}(k)\) 依然有 \(A_i\le A_{i+h}\,(1\le i\le n-h)\)。

得證。

證畢

這個定理揭示了希爾排序在特定集合 \(H\) 下可以優化複雜度的關鍵，因為在整個過程中，它可以一致保持前面的成果不被摧毀（即 \(h\) 個子列分別有序），從而使後面的調用中，指針 \(i\) 的移動次數大大減少。

接下來我們單拎出來一個數論引理進行證明。這個定理在 OI 界因 小凱的疑惑 一題而大為出名。而在希爾排序複雜度的證明中，它也使得定理 \(1\) 得到了很大的擴展。

引理 \(2\)：若 \(a,b\) 均為正整數且互素，則不在集合 \(\{ax+by\mid x,y\in \mathbb N \}\) 中的最大正整數為 \(ab-a-b\)。

證明：

分兩步證明：

  • 先證明方程 \(ax+by=ab-a-b\) 沒有 \(x,y\) 均為非負整數的解：

    若無非負整數的限制，容易得到兩組解 \((b-1,-1),(-1,a-1)\)。

    通過其通解形式 \(x=x_0+tb,y=y_0-ta\)，容易得到上面兩組解是“相鄰”的（因為 \(b-1-b=-1\)）。

    當 \(t\) 遞增時，\(x\) 遞增，\(y\) 遞減，所以如果方程有非負整數解，必然會夾在這兩組解中間，但這兩組解“相鄰”，中間沒有別的解。

    故不可能有非負整數解。 - 再證明對任意整數 \(c > ab-a-b\)，方程 \(ax+by=c\) 有非負整數解：

    我們找一組解 \((x_0,y_0)\) 滿足 \(0\le x_0 < b\)（由通解的表達式，這可以做到）。

    則有：

    \[ by_0=c-ax_0\ge c-a(b-1)>ab-a-b-ab+a=-b \]

    所以 \(b(y_0+1) > 0\)，又因為 \(b>0\)，所以 \(y_0+1>0\)，所以 \(y_0\ge 0\)。

    所以 \((x_0,y_0)\) 為一組非負整數解。

綜上得證。

證畢

而下面這個定理則揭示了引理 \(2\) 是如何擴展定理 \(1\) 的。

定理 \(2\)：如果 \(\gcd(h_{t+1},h_t)=1\)，則程序先執行完 \(\text{InsertionSort}(h_{t+1})\) 與 \(\text{InsertionSort}(h_t)\) 後，執行 \(\text{InsertionSort}(h_{t-1})\) 的時間複雜度為 \(O\left(\dfrac{nh_{t+1}h_t}{h_{t-1}} \right)\)，且對於每個 \(j\)，其 \(i\) 的移動次數是 \(O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)\) 級別的。

證明：

對於 \(j\le h_{t+1}h_t\) 的部分，\(i\) 的移動次數顯然是是 \(O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)\) 級別的。

故以下假設 \(j>h_{t+1}h_t\)。

對於任意的正整數 \(k\) 滿足 \(1\le k\le j-h_{t+1}h_t\)，注意到：\(h_{t+1}h_t-h_{t+1}-h_t<h_{t+1}h_t\le j-k\le j-1\)

又因為 \(\gcd(h_{t+1},h_t)=1\)，故由引理 \(2\)，得存在非負整數 \(a,b\)，使得：\(ah_{t+1}+bh_t=j-k\)。

即得：

\[ k=j-ah_{t+1}-bh_t \]

由定理 \(1\)，得：

\[ A_{j-bh_t}\le A_{j-(b-1)h_t}\le \ldots\le A_{j-h_t}\le A_j \]

與

\[ A_{j-bh_t-ah_{t+1}}\le A_{j-bh_t-(a-1)h_{t+1}}\le \ldots\le A_{j-bh_t-h_{t+1}}\le A_{j-bh_t} \]

綜合以上既有：\(A_k=A_{j-ah_{t+1}-bh_t}\le A_j\)。

所以對於任何 \(1\le k\le j-h_{t+1}h_t\)，有 \(A_k\le A_j\)。

在 Shell-Sort 偽代碼中 \(i\) 指針每次減 \(h_{t-1}\)，減 \(O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)\) 次，即可使得 \(i\le j-h_{t+1}h_t\)，進而有 \(A_i\le A_j\)，不滿足 while 循環的條件退出。

證明完對於每個 \(j\) 的移動複雜度後，即可得到總的時間複雜度：

\[ \sum_{j=h_{t-1}+1}^n{O\left(\frac{h_{t+1}h_t}{h_{t-1}} \right)}=O\left(\frac{nh_{t+1}h_t}{h_{t-1}}\right) \]

得證。

證畢

認真觀察定理 \(2\) 的證明過程，可以發現：定理 1 可以進行“線性組合”，即 \(A\) 以 \(h\) 為間隔有序，以 \(k\) 為間隔亦有序，則以 \(h\) 和 \(k\) 的非負係數線性組合仍是有序的。而這種“線性性”即是由引理 \(2\) 保證的。

有了這兩個定理，我們可以命題 \(1\) 與 \(2\)。

先證明命題 \(1\)：

證明：

將 \(H\) 寫為序列的形式：

\[ H(h_1=1,h_2=3,h_3=7,\ldots,h_{\lfloor \log_2 n\rfloor}=2^{\lfloor \log_2 n\rfloor}-1) \]

Shell-Sort 執行順序為：\(\text{InsertionSort}(h_{\lfloor \log_2 n\rfloor}),\text{InsertionSort}(h_{\lfloor \log_2 n\rfloor-1}),\ldots,\text{InsertionSort}(h_2),\text{InsertionSort}(h_1)\).

分兩部分去分析複雜度：

  • 對於前面的若干個滿足 \(h_t\ge \sqrt{n}\) 的 \(h_t\)，顯然有 \(\text{InsertionSort}(h_t)\) 的時間複雜度為 \(O\left(\dfrac{n^2}{h_t} \right)\)。

    考慮對最接近 \(\sqrt{n}\) 的項 \(h_k\)，有：

    \[ O\left(\frac{n^2}{h_t} \right)=O(n^{3/2}) \]

    而對於 \(i> k\) 的 \(h_i\)，因為有 \(2h_i< h_{i+1}\)，所以可得：

    \[ O\left(\frac{n^2}{h_i} \right)=O(n^{3/2}/2^{i-k})\,(i>k) \]

    所以大等於 \(\sqrt n\) 部分的總時間複雜度為：

    \[ \sum_{i=k}^{\lfloor \log_2 n\rfloor}{O(n^{3/2}/2^{i-k})}=O(n^{3/2}) \]

  • 對於後面剩下的滿足 \(h_t< \sqrt{n}\) 的項，前兩項的複雜度還是 \(O(n^{3/2})\)，而對於後面的項 \(h_t\)，有定理 \(2\) 可得時間複雜度為：

    \[ O\left(\frac{nh_{t+2}h_{t+1}}{h_t} \right)=O\left(\frac{nh_{t+2}\cdot h_{t+2}/2}{h_{t+2}/4} \right)=O(nh_{t+2}) \]

    再次利用 \(2h_i < h_{i+1}\) 性質可得此部分總時間複雜度為（下式中 \(k\) 沿用了上一種情況中的含義）：

    \[ 2O(n^{3/2})+\sum_{i=1}^{k-3}{O(nh_{i+1})}=O(n^{3/2})+\sum_{i=1}^{k-3}{O(nh_{k-1}/2^{k-i-3})}=O(n^{3/2})+O(nh_{k-1})=O(n^{3/2}) \]

綜上可得總時間複雜度即為 \(O(n^{3/2})\)。

證畢

再證明命題 \(2\)：

證明：

注意到一個事實：如果已經執行過了 \(\text{InsertionSort}(2)\) 與 \(\text{InsertionSort}(3)\)，那麼因為 \(2\cdot 3-2-3=1\)，所以由定理 \(2\)，每個元素只有與它相鄰的前一個元素可能大於它，之前的元素全部都小於它。於是 \(i\) 指針只需要最多兩次就可以退出 while 循環。也就是説，此時再執行 \(\text{InsertionSort}(1)\)，複雜度降為 \(O(n)\)。

更進一步：如果已經執行過了 \(\text{InsertionSort}(4)\) 與 \(\text{InsertionSort}(6)\)，我們考慮所有的下標為奇數的元素組成的子列與下標為偶數的元素組成的子列。則這相當於把這兩個子列分別執行 \(\text{InsertionSort}(2)\) 與 \(\text{InsertionSort}(3)\)。那麼也是一樣，這時候再執行 \(\text{InsertionSort}(2)\)，相當於對兩個子列分別執行 \(\text{InsertionSort}(1)\)，也只需要兩個序列和的級別，即 \(O(n)\) 的複雜度就可以將數組變為 \(2\) 間隔有序。

不斷歸納，就可以得到：如果已經執行過了 \(\text{InsertionSort}(2h)\) 與 \(\text{InsertionSort}(3h)\)，則執行 \(\text{InsertionSort}(h)\) 的複雜度也只有 \(O(n)\)。

接下來分為兩部分分析複雜度：

  • 對於 \(h_t>n/3\) 的部分，則執行每個 \(\text{InsertionSort}(h_t)\) 的複雜度為 \(O(n^2/h_t)\)。

    而 \(n^2/h_t<3n\)，所以單詞插入排序複雜度為 \(O(n)\)。

    而這一部分元素個數是 \(O(\log^2 n)\) 級別的，所以這一部分時間複雜度為 \(O(n\log^2 n)\)。

  • 對於 \(h_t\le n/3\) 的部分，因為 \(3h_t\le n\)，所以這之前已經執行了 \(\text{InsertionSort}(2h_t)\) 與 \(\text{InsertionSort}(3h_t)\)，於是執行 \(\text{InsertionSort}(h_t)\) 的時間複雜度是 \(O(n)\)。

    還是一樣的，這一部分元素個數也是 \(O(\log^2 n)\) 級別的，所以這一部分時間複雜度為 \(O(n\log^2 n)\)。

綜上可得總時間複雜度即為 \(O(n\log^2 n)\)。

證畢

空間複雜度

希爾排序的空間複雜度為 \(O(1)\)。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
template <typename T>
void shell_sort(T array[], int length) {
  int h = 1;
  while (h < length / 3) {
    h = 3 * h + 1;
  }
  while (h >= 1) {
    for (int i = h; i < length; i++) {
      for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
        std::swap(array[j], array[j - h]);
      }
    }
    h = h / 3;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def shell_sort(array, length):
    h = 1
    while h < length / 3:
        h = int(3 * h + 1)
    while h >= 1:
        for i in range(h, length):
            j = i
            while j >= h and array[j] < array[j - h]:
                array[j], array[j - h] = array[j - h], array[j]
                j -= h
        h = int(h / 3)

參考資料與註釋

  1. 希爾排序 - 維基百科，自由的百科全書 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用