1. 基本概念

希爾排序又叫遞減增量排序算法，它是在直接插入排序算法的基礎上進行改進而來的，綜合來說它的效率肯定是要高于直接插入排序算法的；希爾排序是一種不穩定的排序算法。

希爾排序由唐納德·希爾（Donald Shell）發明并于1959年公布，因此得名希爾排序。

我們之前講過直接插入排序，它的算法復雜度為O(n^2)，整體來說它的效率很低；在后面第3小節中我們將簡短地回憶一下它的工作方式。但是在兩種情況下它表現得很好，我們這里將這兩種情況歸納為直接插入排序的兩種性質：

1. 當待排序的原序列中大多數元素都已有序的情況下，此時進行的元素比較和移動的次數較少；

2. 當原序列的長度很小時，即便它的所有元素都是無序的，此時進行的元素比較和移動的次數還是很少。

希爾排序正是利用了直接插入排序算法的這兩個性質，它首先將待排序的原序列劃分成很多小的序列，稱為子序列。然后對這些子序列進行直接插入排序，因為每個子序列中的元素較少，所以在它們上面應用直接插入排序效率較高（利用了上面的性質2）。這樣的過程可能會進行很多次，每一次都稱為一趟，每一趟都將前一趟得到的整個序列劃分為不同的子序列，并再次對這些子序列進行直接插入排序。最后由這些子序列組成的整個序列中的所有元素就基本有序了，此時再在整個序列上進行最后一次的直接插入排序（利用了上面的性質1），此后整個序列的排序就完成了。

2. 子序列的劃分方式

希爾排序最關鍵的地方就是如何對整個序列進行劃分，理解了這一過程就理解了整個希爾排序。我們最直接的想法可能就是按順序對整個序列進行平均劃分，比如有n個元素的序列，我們要把它劃分成i個子序列，每個子序列有m個元素（假設n = i * m，當n不能被i整除時可以讓最后一個子序列的元素少于其它子序列）。該想法就是讓原序列的第0 ~ m-1個元素為第一個子序列（第一個元素的下標為0），第m ~ 2m-1個元素為第二個子序列，以此類推，最后的第n-m ~ n-1個元素為最后一個子序列。

這樣的劃分雖然簡單但是它卻不適合希爾排序，這樣劃分并對子序列進行直接插入排序后，雖然每個子序列中的元素都是有序的，但整個原序列依舊是很無序的。為了便于理解為什么這種方式不行，我們用圖1來對它進行說明。

圖1 按順序劃分的子序列

在圖1中，原序列有9個元素，我們將它按順序劃分為3個子序列。即最前面的3個元素為第一個子序列，中間3個元素為第二個子序列，最后3個元素為最后一個子序列；圖中我們用不同的顏色表示不同的子序列。

可以看到，對每個子序列應用直接插入排序后，雖然每個子序列都是有序的，但整個序列還是很無序的。此時，在整個序列上進行直接插入排序的效率還是很低。整個序列依舊無序的原因是每個元素只在它所在的子序列中移動，它的新位置離它的最終位置（即整個序列排好序后的位置）還是很遠。

因此，子序列劃分的方法必須保證對子序列進行排序后，每個元素在整個序列中的移動范圍更大。這樣跳躍式的位置移動，才可能讓每個元素離它的最終位置較近，因而整個序列才是比較有序的。

希爾排序采用的是按增量的方式進行子序列劃分，將整個序列中下標值相差固定值（增量）的所有元素劃分到同一個子序列中。比如，整個序列有9個元素，而增量為3，那么第0、3、6個元素屬于第一個子序列，第1、4、7個元素屬于第二個子序列，第2、5、8個元素屬于最后一個子序列。

為了便于理解，我們同樣用圖2來展示這種增量劃分方式。我們同樣用不同的顏色表示屬于不同子序列的元素，并標出了每個子序列的元素的下標值。可以看到，以增量方式劃分的子序列在整個序列中是交錯出現的。

圖2 按增量劃分的子序列

按照增量劃分的時候，假設增量為increment，那么整個序列也將劃分為increment個子序列。可以這樣理解，我們遍歷整個序列中的每個元素，并為每個元素指定它所屬的子序列。首先是下標為0的元素，它屬于第一個子序列；然后是下標為1的元素，它屬于第二個子序列；以此類推，可知前increment個元素（下標為0 ~ increment-1）屬于不同的子序列，共計increment個。從下標為increment的元素開始，每一個元素的下標值減去increment都大于或等于0，即這些元素都屬于一個已存在的子序列。因此，整個序列將被劃分為increment個子序列。

在實際的應用中，待排序的原序列可能有很多個元素，成千上萬甚至上億。此時，為了充分利用希爾排序的效率，應該進行多趟排序，每一趟用不同的（嚴格說是遞減的）增量對整個序列進行劃分。即首先用增量i1對原序列進行劃分，并對每個子序列進行直接插入排序；然后對前一步得到的整個序列用一個新的且較小的增量i2（i2小于i1）進行劃分，并對每個子序列進行直接插入排序；然后又對前一步得到的整個序列用一個更小的增量i3（i3小于i2）進行劃分，并對每個子序列進行直接插入排序。以此類推，直到最后增量為1，此時可以認為整個序列就是一個唯一的子序列，對它進行直接插入排序之后整個原始序列都是有序的了，希爾排序算法結束。

根據這種增量劃分子序列的方式，我們可知希爾排序是不穩定的排序算法。假設原序列中有兩個相同的元素，分別記為a和b，并且a在b的前面。a和b很可能被劃分到不同的子序列中，對子序列分別進行排序后，在整個序列中b可能移到了a的前面。也就是說經過希爾排序后，原序列中原本相同的兩個元素的相對位置在排序后發生了改變（原本是a在b之前，排序后是b在a之前），因此希爾排序是不穩定的排序算法。

圖3展示了一個完整的希爾排序算法過程，該示例中的希爾排序一共進行了3趟，每一趟的增量分別是3、2、1。

圖3 希爾排序完整過程

針對希爾排序，還有一個問題我們沒有解決，那就是每一次希爾排序一共要進行多少趟，并且每一趟的增量是多少？每一趟的增量按照先后次序可以排成一個序列，稱為增量序列。增量序列不但決定了希爾排序的過程，并且也會影響希爾排序的性能。

增量序列的最后一個元素必須是1，即希爾排序的最后一趟必須是在整個序列上進行直接插入排序，這樣才能保證最終的序列是有序的。最后一趟（即增量為1）開始時，整個序列都是大致有序的，因此這一趟只會進行少數元素的比較和移動。

只要增量序列中的所有元素都從大到小排序，并且最后一個元素為1，那么該增量序列就可以用于希爾排序。已經提出很多種增量序列，其中一種常用的增量序列可以根據公式2^(t - k + 1) - 1計算，參數t是一共要進行的趟數而k代表每一趟；1 ≤ k ≤ t，并且t ≤ ⌊log2(n+1)⌋，其中n是原序列的元素總數；該公式產生的增量序列為[... , 15, 7, 3, 1]。

3. 對子序列排序進行并發執行

在希爾排序的每一趟中，我們都需要對屬于該趟的所有子序列進行排序，直到所有的子序列都是有序的。按照我們上面的思路，我們是對所有子序列按串行的方式進行排序的，即先將第一個子序列排好序，然后將第二個子序列排好序，再將第三個子序列排好序。以此類推，直到該趟中所有子序列都分別是有序的。

這樣在子序列之間按嚴格的先后順序進行排序的方式是絕對正確的，也是十分直觀的，它非常便于理解希爾排序的整體思想。按照這樣的方式也很容易用代碼實現希爾排序，但在很多算法書中的實現代碼卻是按照并發的方式對子序列進行排序。為了便于理解，我們假設進行希爾排序的計算機CPU是多核的并且它的核數多于子序列的數量，現在把每個子序列都分配給一個對應的核，并由該核對該子序列進行排序。那么這些核可以同時運行以對所有子序列進行同時排序；這是可行的，因為每個子序列之間的元素都是獨立而無重疊的，每個核之間的工作不會相互影響。這種工作方式也叫做并行。

再考慮單核CPU的情況，它依舊能夠“同時”的執行多個任務，比如早期的分時操作系統就是運行在這樣的環境下。它先執行第一個任務的一部分，然后執行第二個任務的一部分，再執行第三個任務的一部分，等等。某個時刻，它又會回來執行第一個任務的另一部分、然后又執行第二個任務的另一部分，等等。這樣CPU在多個任務之間快速切換，每個任務每次只占用很少的CPU時間；這樣以我們人類的視角來看這些任務就好像是同時執行的，雖然實際上每個時刻只有一個任務在執行。這種工作方式也叫做并發。

只要將對每個子序列進行排序都視為一個單獨的任務，那么很多希爾排序的實現方式都采用了這種并發的方式。之所以這樣做，可能是為了讓實現代碼更緊湊，或者利用按行順序訪問元素的方式減少高速緩存或內存頁不命中的情況。為了方便說明，這里我們假設原序列有n個元素，且某一趟的增量為i，并且n=i*m；那么該趟中整個序列將被劃分為i個子序列且每個子序列有m個元素。

因為對每個子序列都采用直接插入排序算法進行排序，因此這里我們簡單回顧一下它的原理。在直接插入排序中將待排序的序列看作兩部分，前面部分是已排好序的，后面部分是未排序的。在最開始的時候，前面部分只有第一個元素，后面部分包含剩余的所有元素。直接插入排序由多步組成，每一步都將后面部分的第一個元素與前面部分進行比較以找出它應該插入的位置，使插入它之后的新的前面部分依舊是有序的。這樣每一步中，前面部分都增加一個元素而后面部分都減少一個元素，對于一個有m個元素的序列，進行m-1步后該序列就排好序了。

圖4中的例子展示了對子序列排序進行并發執行時，是如何訪問每個子序列中的每個待排序元素的，即按照圖中綠色箭頭指示的順序訪問這些待排序的元素。

圖4 對子序列排序的并發執行

當我們對希爾排序某一趟中的所有子序列進行排序時，先執行第一個子序列的第1步直接插入排序，然后執行第二個子序列的第1步直接插入排序，以此類推，直到執行完最后一個（第i個）子序列的第1步直接插入排序。然后我們又回到第一個子序列，對它進行第2步的直接插入排序；然后執行第二個子序列的第2步直接插入排序，一直到最后一個子序列的第2步直接插入排序完成。然后又回到第一個子序列，執行它的第3步直接插入排序，等等。這一過程重復執行直到最后一個子序列的第m-1步直接插入排序完成，此時所有的子序列都各自是有序的了。

第一個子序列的第1步直接插入排序是對它的第二個元素進行排序（第一個元素不需要排序，因為單個元素被認為是有序的），注意該元素在整個序列中的下標為i；第二個子序列的第1步直接插入排序也是對它的第二個元素進行排序，該元素在整個序列中的下標為i+1；第三個子序列的第1步直接插入排序也是對它的第二個元素進行排序，該元素在整個序列中的下標為i+2；最后一個子序列的第1步直接插入排序同樣是對它的第二個元素進行排序，該元素在整個序列中的下標為i+i-1（2i-1）。

然后，第一個子序列的第2步直接插入排序是對它的第三個元素進行排序，該元素在整個序列中的下標為2i；第二個子序列的第2步直接插入排序也是對它的第三個元素進行排序，該元素在整個序列中的下標為2i+1；最后一個子序列的第2步直接插入排序同樣是對它的第三個元素進行排序，該元素在整個序列中的下標為2i+i-1（3i-1）。

因為每一個子序列的元素都是獨立而不重疊的，互相之間不會干擾。所以這樣并發執行的結果和串行執行的結果是相同的，這就證明了這樣并發執行的正確性。

按照這樣的并發方式，一趟中所有待排序的元素（它們屬于不同的子序列）其實是按它們在整個序列中的順序訪問的。我們從整個序列的第i個（它的下標為i）元素開始，一次向后遍歷一個元素，每遍歷到一個元素就在它所在的子序列中對它進行直接插入排序，整個序列中屬于同一子序列的所有元素的下標值相差i。當整個序列中的最后一個元素被遍歷到且排序后，整個序列在該趟中的所有子序列都已排好序了。此時，就可以進入希爾排序的下一趟了。

4. 代碼實現

這里我們用C語言來實現希爾排序，代碼很簡單，即便不精通C語言也能看懂，代碼中我們也給出了詳細的注釋。我們定義了一個輔助函數incrementValue()，它接收兩個參數，總的趟數t和當前趟數k，然后用公式2^(t - k + 1) - 1計算并返回當前趟應該采用的增量值。

#include <math.h>

/*
 * Function: incrementValue
 * Description: 根據希爾排序總的趟數和當前趟生成增量，
                計算公式為：2^(t - k + 1) - 1。
 * param: t 總的趟數
 * param: k 當前趟數
 * return: 當前趟對應的增量
 */
int incrementValue(int t, int k) {
    int power = t - k + 1;
    int value = pow(2, power) - 1;
    return value;
}

/*
 * Function: shellSort
 * Description: 希爾排序的實現
 * param: array 待排序的序列（數組）
 * param: n 序列中的元素數量
 * param: t 總的趟數，它將用于生成增量序列
 */
void shellSort(int array[], int n, int t) {
    /*
     * i、j、k作為循環控制變量，
     * temp用于移動元素，
     * increment用于記錄當前趟的增量。
     */
    int i;
    int j;
    int k;
    int temp;
    int increment;

    // 外層循環，用于控制第1至第t趟排序，每一趟都對應一個不同的增量；
    for(i = 1; i <= t; i++) {
        // 根據總的趟數和當前趟，獲取當前的增量
        increment = incrementValue(t, i);

        /*
         * 中間層循環，順序遍歷整個序列中需要排序的每一個元素；
         * 這些元素在整個序列中的下標從increment開始，直到最
         * 后一個元素。每遍歷到一個元素就在它所有在的子序列中
         * 對它進行直接插入排序，同一子序列中的相鄰元素的下標
         * 相差increment。
         */
        for(j = increment; j < n; j++) {

            /*
             * 內層循環，對當前元素進行直接插入排序，注意同一子序列中
             * 的相鄰元素的下標相差increment。如果當前元素大于或等于
             * 它所在子序列的前一個元素，那么它當前就已經排好序了。
             * 否則，需要在它所在的子序列中查找它應該插入的位置，并將
             * 大于它的所有元素在該子序列中向后移動一個位置。
             */
            if(array[j] < array[j - increment]) {
                temp = array[j];
                for(k = j - increment; k >= 0 && array[k] > temp; k -= increment) {
                    array[k + increment] = array[k];
                }
                array[k + increment] = temp;
            }
        }
    }
}

5. 復雜度分析

希爾排序的平均時間復雜度和執行它所選擇的增量序列有關，按照我們實現中采用的增量序列，它的平均時間復雜度可以達到O(n^(3/2))，即n的3/2次方。那么哪一種增量序列是最好的呢？還沒有人知道這一問題的答案。

從我們以上的實現代碼中可以看出，希爾排序只需要幾個固定的額外存儲空間，分別用于存儲變量i、j、k、temp、increment，這和它的待排序序列的大小無關。所以，它的空間復雜度為O(1)。

（完）