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)。

（完）